Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges


  • Ariel Felner Ben-Gurion University of the Negev
  • Roni Stern Ben-Gurion University of the Negev
  • Solomon Shimony Ben-Gurion University of the Negev
  • Eli Boyarski Bar-Ilan University
  • Meir Goldenberg The Jerusalem College of Technology
  • Guni Sharon The University of Texas at Austin
  • Nathan Sturtevant The University of Denver
  • Glenn Wagner Carnegie Mellon University
  • Pavel Surynek National Institute of Advanced Industrial Science and Technology



Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.