Symmetry-breaking constraints for grid-based Multi-Agent Path Finding

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

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

Abstract

We describe a new way of reasoning about symmetric collisions for Multi-Agent Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking constraint to resolve these conflicts. This specialized technique allows us to identify and eliminate, in a single step, all permutations of two currently assigned but incompatible paths. Each such permutation has exactly the same cost as a current path, and each one results in a new collision between the same two agents. We show that the addition of symmetry-breaking techniques can lead to an exponential reduction in the size of the search space of CBS, a popular framework for MAPF, and report significant improvements in both runtime and success rate versus CBSH and EPEA* – two recent and state-of-the-art MAPF algorithms.
Original languageEnglish
Title of host publicationProceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence
EditorsPascal Van Hentenryck, Zhi-Hua Zhou
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages6087-6095
Number of pages9
ISBN (Electronic)9781577358091
DOIs
Publication statusPublished - 2019
EventAAAI conference on Artificial Intelligence 2019 - Honolulu, United States of America
Duration: 27 Jan 20191 Feb 2019
Conference number: 33rd
https://aaai.org/Conferences/AAAI-19/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Number1
Volume33
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI conference on Artificial Intelligence 2019
Abbreviated titleAAAI 2019
CountryUnited States of America
CityHonolulu
Period27/01/191/02/19
Internet address

Cite this

Li, J., Harabor, D., Stuckey, P. J., Ma, H., & Koenig, S. (2019). Symmetry-breaking constraints for grid-based Multi-Agent Path Finding. In P. Van Hentenryck, & Z-H. Zhou (Eds.), Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence (pp. 6087-6095). [3877] (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33, No. 1). Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v33i01.33016087