ST-SPF & STMS: two new algorithms for path finding in robotic mobile fulfillment systems - Barros, Ítalo Renan da Costa (2021)
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.