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

October 2020

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

Authors:

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

Abstract:

We consider two new classes 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 in opposite directions. The second, target symmetry, arises when the shortest path of one agent passes through the target location of a second agent after the second agent has already arrived at it. These symmetries can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes even for state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We propose to break these symmetries using new reasoning techniques that: (1) detect each class of symmetry and (2) resolve them by introducing specialized constraints. We experimentally show that our techniques can, in some cases, more than double the success rate of CBS and improve its runtime by one order of magnitude.
@conference{Li-2020-131415,
author = {Jiaoyang Li And Graeme Gange And Daniel Harabor And Peter J. Stuckey And Hang Ma And Sven Koenig},
title = {New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding},
booktitle = {Proceedings of 30th International Conference on Automated Planning and Scheduling (ICAPS '20)},
year = {2020},
month = {October},
volume = {30},
pages = {193 - 201},
}
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.