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

4 Citations (Scopus)

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.

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)
Pages193-201
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
https://aaai.org/ojs/index.php/ICAPS/issue/view/263 (Proceedings)
https://icaps20.icaps-conference.org (Website)

Publication series

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

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
CountryFrance
CityNancy
Period26/10/2030/10/20
Internet address

Cite this