Beyond Pairwise Reasoning in Multi-Agent Path Finding


  • Bojie Shen Monash University
  • Zhe Chen Monash University
  • Jiaoyang Li Carnegie Mellon University
  • Muhammad Aamir Cheema Monash University
  • Daniel D. Harabor Monash University
  • Peter J. Stuckey Monash University



Heuristic search, Multi-agent and distributed planning


In Multi-Agent Path Finding (MAPF), we are asked to plan collision-free paths for teams of moving agents. Among the leading methods for optimal MAPF is Conflict-Based Search (CBS), an algorithmic family which has received intense attention in recent years and for which large advancements in efficiency and effectiveness have been reported. Yet all of the recent CBS gains come from reasoning over pairs of agents only. In this paper, we show how to further improve CBS by reasoning about more than two agents at the same time. Our new cluster reasoning techniques allow us to generate stronger bounds for CBS and to identify more bypasses (alternative cost-equivalent paths), which reduce the number of nodes in the CBS conflict tree.




How to Cite

Shen, B., Chen, Z., Li, J., Cheema, M. A., Harabor, D. D., & Stuckey, P. J. (2023). Beyond Pairwise Reasoning in Multi-Agent Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 384-392.