Abstract:
Mutex propagation is a form of efficient constraint propagation popularly used in automated planning to tightly approximate the reachable states from a given state. We investigate the use of this idea in the context of Multi-Agent Path Finding (MAPF). When adapted to MAPF problems, mutex propagation gives us a strong branching rule for Conflict-Based Search (CBS), a popular framework for solving MAPF optimally. This is derived from the strong ability of mutex propagation to identify and reason with symmetries in MAPF instances. 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 us to design symmetry-breaking constraints automatically. Our experimental results show a significant advantage of mutex propagation over CBSH with rectangle reasoning, a state-of-the-art optimal MAPF solver.
