Skip navigation
DSpace logo

  1. Repositório Institucional da UFPB
  2. BDTD - UFPB
  3. UFPB - Campus I - João Pessoa
  4. Centro de Informática (CI) - Programa de Pós-Graduação em Informática
Use este identificador para citar ou linkar para este item: https://repositorio.ufpb.br/jspui/handle/123456789/22655
Registro completo de metadados
Campo DCValorIdioma
dc.creatorBarros, Ítalo Renan da Costa-
dc.date.accessioned2022-04-06T15:10:06Z-
dc.date.available2021-10-23-
dc.date.available2022-04-06T15:10:06Z-
dc.date.issued2021-03-19-
dc.identifier.urihttps://repositorio.ufpb.br/jspui/handle/123456789/22655-
dc.description.abstractOne of the main problems faced in Multi-Agent Path Finding (MAPF) applied to Robotic Mobile Fulfillment Systems (RMFS) is how to bring greater scalability as we increase the number of agents in the system. This work aims to propose two new offline algorithms, the Space-Time Swarm Path Finding (ST-SPF) a decentralized algorithm, and the Space-Time Multi-Start (STMS), an centralized algorithm. The algorithms were tested in a simulator developed in the PyGame framework, with up to 250 agents in three different types of warehouses instances) and two types of map representations: Grid-Based and Graph-Based. The results show that the ST-SPF is scalable in complex and populous maps, achieving up to 48% reduction in execution time when compared to the Conflict-based Search (CBS) art study algorithm, while the STMS presented an advantage to CBS since achieves more completeness in small and populous instances. Finally, it was also noted that the use of the Graph-Based representation has a high use of memory for complex instances (above 600 nodes), with the Grid-Based representation being the most efficient.pt_BR
dc.description.provenanceSubmitted by Fernando Augusto Alves Vieira (fernandovieira@biblioteca.ufpb.br) on 2022-03-30T19:07:51Z No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) ÍtaloRenanDaCostaBarros_Dissert.pdf: 25647007 bytes, checksum: 9fa85fefa89008adc659b2d593de3349 (MD5)en
dc.description.provenanceApproved for entry into archive by Biblioteca Digital de Teses e Dissertações BDTD (bdtd@biblioteca.ufpb.br) on 2022-04-06T15:10:06Z (GMT) No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) ÍtaloRenanDaCostaBarros_Dissert.pdf: 25647007 bytes, checksum: 9fa85fefa89008adc659b2d593de3349 (MD5)en
dc.description.provenanceMade available in DSpace on 2022-04-06T15:10:06Z (GMT). No. of bitstreams: 2 license_rdf: 805 bytes, checksum: c4c98de35c20c53220c07884f4def27c (MD5) ÍtaloRenanDaCostaBarros_Dissert.pdf: 25647007 bytes, checksum: 9fa85fefa89008adc659b2d593de3349 (MD5) Previous issue date: 2021-03-19en
dc.description.sponsorshipConselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPqpt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal da Paraíbapt_BR
dc.rightsAcesso abertopt_BR
dc.rightsAttribution-NoDerivs 3.0 Brazil*
dc.rights.urihttp://creativecommons.org/licenses/by-nd/3.0/br/*
dc.subjectRMFSpt_BR
dc.subjectMAPFpt_BR
dc.subjectPath planningpt_BR
dc.subjectSistemas multi-agentespt_BR
dc.subjectWarehouses robotizadaspt_BR
dc.subjectMultti-agent systemspt_BR
dc.subjectRobotized warehousespt_BR
dc.titleST-SPF & STMS: two new algorithms for path finding in robotic mobile fulfillment systemspt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Nascimento, Tiago Pereira do-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/1641673656667170pt_BR
dc.contributor.advisor-co1Costa, Luís Peliphe Silva-
dc.contributor.advisor-co1LattesLattes não recuperado em 30/03/2022pt_BR
dc.creator.Latteshttp://lattes.cnpq.br/8038318614551634pt_BR
dc.description.resumoUm dos principais problemas enfrentado no Multi-Agent Path Finding aplicado a Robotic Mobile Fulfillment Systems é como trazer uma maior escalabilidade ao sistema conforme aumentamos o número de agentes. Este trabalho tem como objetivo propor dois novos algoritmos offline, o algoritmo descentralizado Space-Time Swarm Path Finding (ST-SPF), e o algoritmo centralizado Space-Time Multi-Start (STMS). Os algoritmos foram testados em um simulador desenvolvido no framework PyGame, onde foram realizados experimentos com até 250 agentes em três tipos de warehouses (instâncias) diferentes, e com dois tipos representações do mapa: Grid-Based e Graph-Based. Os resultados demonstram que o ST-SPF é escalável em instâncias grandes e populosas, alcançando até 48% de redução do tempo de execução quando comparado com o algoritmo de estudo da arte Conflict-based Search (CBS), enquanto que o STMS apresentou uma vantagem ao CBS por ser mais completo (completeness) em instâncias pequenas e populosas. Por fim, também foi notado que a utilização da representação Graph-Based possui uma alta utilização de memória para instâncias complexas (acima de 600 nós), sendo a representação Grid-Based mais eficiente.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInformáticapt_BR
dc.publisher.programPrograma de Pós-Graduação em Informáticapt_BR
dc.publisher.initialsUFPBpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
Aparece nas coleções:Centro de Informática (CI) - Programa de Pós-Graduação em Informática

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
ÍtaloRenanDaCostaBarros_Dissert.pdf25,05 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Este item está licenciada sob uma Licença Creative Commons Creative Commons