Hierarchical Token Passing Algorithm for Multi-Agent Pickup and Delivery

The problem of coordinating the movements of a group of agents that perform pickup and delivery operations in a known environment is called Multi-Agent Pickup and Delivery (MAPD). Warehouses, where mobile robots complete transportation tasks composed of pickup and delivery operations, are the typical domain of application of MAPD. Over the years, the number of robots employed in these settings has gradually increased to the order of hundreds, leading to new challenges in the scalability of algorithms. In this paper, we introduce a new algorithm called hierarchical Token Passing (h-TP) to face this problem through a logical segmentation of the environment that enables the parallel computation of agents' paths. We test the performance of h-TP in simulated warehouse environments and compare it against a classical algorithm for solving MAPD problems that does not operate in parallel. The results show a reduction of the total execution time of about 50% at the cost of a small worsening of the solution quality.