A review of graph-based multi-agent pathfinding solvers: From classical to beyond classical

Abstract

Multi-agent pathfinding (MAPF) is a well-studied abstract model for navigation in a multi-robot system, where every robot finds the path to its goal position without any collision. Due to its numerous practical applications of multi-robot systems, MAPF has steadily emerged as a research hotspot. The optimal solution for MAPF is NP-hard. In this paper, we offer a comprehensive analysis of different MAPF solvers. First, we review the cutting-edge solvers of classical MAPF, including optimal, bounded sub-optimal, and unbounded sub-optimal. The performance of some representative classical MAPF solvers is quantitatively compared. In the next part, we summarize the beyond classical MAPF solvers, which try to use the classical MAPF solvers in real-world scenarios. Last, we conclude some challenges that MAPF is experiencing in detail, review recent research on these issues, and make some suggestions for further work.