ST-SPF & STMS: two new algorithms for path finding in robotic mobile fulfillment systems

Detalhes bibliográficos
Ano de defesa: 2021
Autor(a) principal: Barros, Ítalo Renan da Costa
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal da Paraíba
Brasil
Informática
Programa de Pós-Graduação em Informática
UFPB
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufpb.br/jspui/handle/123456789/22655
Resumo: One 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.