Publication

H. Zhang, Y. Li, J. Li, S. Kumar and S. Koenig. Mutex Propagation in Multi-Agent Path Finding for Large Agents. In Proceedings of the Symposium on Combinatorial Search (SoCS), 2022.

Abstract: Mutex propagation and its concomitant symmetry-breaking techniques have proven useful in Multi-Agent Path Finding (MAPF) with point agents. In this paper, we show that they can be easily generalized to richer MAPF problems. In particular, we demonstrate their application to MAPF with 'Large' Agents (LA-MAPF). Here, agents can occupy multiple points at the same time according to their fixed shapes and sizes. While existing rule-based symmetry-breaking techniques are difficult to generalize from point agents to large agents, mutex-based symmetry-breaking techniques can be generalized easily. In a Conflict-Based Search (CBS) framework for LA-MAPF, we also develop a mutex-based conflict-selection strategy to further enhance the efficiency of the search. Through experiments on various maps, we show that our techniques significantly improve MC-CBS, a state-of-theart optimal LA-MAPF algorithm, in terms of both success rate and runtime.

Download the paper in pdf.