Repositório Institucional da UFPB
Use este identificador para citar ou linkar para este item:
https://repositorio.ufpb.br/jspui/handle/123456789/22655| Tipo: | Dissertação |
| Título: | ST-SPF & STMS: two new algorithms for path finding in robotic mobile fulfillment systems |
| Autor(es): | Barros, Ítalo Renan da Costa |
| Primeiro Orientador: | Nascimento, Tiago Pereira do |
| Primeiro Coorientador: | Costa, Luís Peliphe Silva |
| Resumo: | Um 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. |
| Abstract: | 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. |
| Palavras-chave: | RMFS MAPF Path planning Sistemas multi-agentes Warehouses robotizadas Multti-agent systems Robotized warehouses |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Idioma: | por |
| País: | Brasil |
| Editor: | Universidade Federal da Paraíba |
| Sigla da Instituição: | UFPB |
| Departamento: | Informática |
| Programa: | Programa de Pós-Graduação em Informática |
| Tipo de Acesso: | Acesso aberto Attribution-NoDerivs 3.0 Brazil |
| URI: | http://creativecommons.org/licenses/by-nd/3.0/br/ |
| URI: | https://repositorio.ufpb.br/jspui/handle/123456789/22655 |
| Data do documento: | 19-Mar-2021 |
| 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 | Tamanho | Formato | |
|---|---|---|---|---|
| ÍtaloRenanDaCostaBarros_Dissert.pdf | 25,05 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciada sob uma
Licença Creative Commons
