Beyond Pairwise Reasoning in Multi-Agent Path Finding

Authors

  • 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

DOI:

https://doi.org/10.1609/icaps.v33i1.27217

Keywords:

Heuristic search, Multi-agent and distributed planning

Abstract

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.
ICAPS-23 Proceedings Cover

Downloads

Published

2023-07-01

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. https://doi.org/10.1609/icaps.v33i1.27217

Issue

Vol. 33 (2023): Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling

Section

Main Track