Multi-Agent Path Finding with Mutex Propagation


  • Han Zhang University of Southern California
  • Jiaoyang Li University of Southern California
  • Pavel Surynek Czech Technical University
  • Sven Koenig University of Southern California
  • T. K. Satish Kumar University of Southern California



Mutex propagation is a form of efficient constraint propagation popularly used in AI planning to tightly approximate the reachable states from a given state. We utilize this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF, mutex propagation provides stronger constraints for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF algorithm, and provides it with the ability to identify and reason with symmetries in MAPF. While existing work identifies a limited form of symmetries using rectangle reasoning and requires the manual design of symmetry-breaking constraints, mutex propagation is more general and allows for the automated design of symmetry-breaking constraints. Our experimental results show that CBS with mutex propagation is capable of outperforming CBSH with rectangle reasoning, a state-of-the-art variant of CBS, with respect to runtime and success rate.




How to Cite

Zhang, H., Li, J., Surynek, P., Koenig, S., & Kumar, T. K. S. (2020). Multi-Agent Path Finding with Mutex Propagation. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1), 323-332.