New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding

Jiaoyang Li, Graeme Gange, Daniel Harabor, Peter J. Stuckey, Hang Ma, Sven Koenig

PosterID: 51 PDF Slides Poster BibTeX

We consider two new types of pairwise path symmetries which appear in the context of Multi-Agent Path Finding (MAPF). The first of them, corridor symmetry, arises when two agents attempt to pass through the same narrow passage but in opposite directions. The second, target symmetry, arises when the individually optimal path of one agent requires the target location of a second agent after the second agent has already arrived. Undetected, these symmetries can produce an exponential blowup in the space of possible conflict resolutions, leading to timeout failure even for state-of-the-art algorithms such as Conflict-Based Search. We propose to break symmetries using new reasoning techniques that: (1) detects each type of situation and; (2) resolves them by introducing specialized constraints. We implement our ideas in the context of Conflict-Based Search where, in a range of experiments, we report up to an order-of-magnitude improvement in runtime performance and, in some cases, more than a doubling in success rate.

Session Aus2: Search
Canb 10/28/2020, 20:00 – 21:00
10/30/2020, 13:00 – 14:00
Paris 10/28/2020, 10:00 – 11:00
10/30/2020, 03:00 – 04:00
NYC 10/28/2020, 05:00 – 06:00
10/29/2020, 22:00 – 23:00
LA 10/28/2020, 02:00 – 03:00
10/29/2020, 19:00 – 20:00