New techniques for pairwise symmetry breaking in Multi-Agent Path Finding

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

25 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Conference on Automated Planning and Scheduling
EditorsJ. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781577358244
Publication statusPublished - 1 Jun 2020
EventInternational Conference on Automated Planning and Scheduling 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020
Conference number: 30th (Proceedings) (Website)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherThe AAAI Press
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843


ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
Internet address

Cite this