Multi-Agent Path Finding with Mutex Propagation

October 2020

Multi-Agent Path Finding with Mutex Propagation

Authors:

Han Zhang, Jiaoyang Li, Pavel Surynek, Sven Koenig, and T. K. Satish Kumar

Abstract:

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.
@conference{Zhang-2020-131417,
author = {Han Zhang And Jiaoyang Li And Pavel Surynek And Sven Koenig And T. K. Satish Kumar},
title = {Multi-Agent Path Finding with Mutex Propagation},
booktitle = {Proceedings of 30th International Conference on Automated Planning and Scheduling (ICAPS '20)},
year = {2020},
month = {October},
pages = {323 - 332},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.