A distributed solver for multi-agent path finding problems

Abstract

Multi-Agent Path Finding (MAPF) problems are traditionally solved in a centralized manner. There are works focusing on completeness, optimality, performance, or a tradeoff between them. However, there are only a few works based on spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which---besides solving their assigned sub-problems---interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by the Robot Operating System (ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of the asprilo system and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100×100 obstacle-free maps---a problem beyond the capability of a single sub-solver---within 7 minutes on a consumer laptop. We also evaluate ros-dmapf against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work.