Multi-Agent Path Finding with Mutex Propagation

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

PosterID: 31 PDF Poster BibTeX

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.

Session Am5: Path & Robot Planning
Canb 10/28/2020, 04:00 – 05:00
10/31/2020, 11:00 – 12:00
Paris 10/27/2020, 18:00 – 19:00
10/31/2020, 01:00 – 02:00
NYC 10/27/2020, 13:00 – 14:00
10/30/2020, 20:00 – 21:00
LA 10/27/2020, 10:00 – 11:00
10/30/2020, 17:00 – 18:00