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 PaperOther


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 significantly speed up Conflict-Based Search (CBS), a popular framework for MAPF.

Original languageEnglish
Title of host publicationProceedings of the Twelfth International Symposium on Combinatorial Search
EditorsPavel Surynek, William Yeoh
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages2
ISBN (Electronic)9781577358084
Publication statusPublished - 2019
EventInternational Symposium on Combinatorial Search 2019 - Napa, United States of America
Duration: 16 Jul 201917 Jul 2019
Conference number: 12th (Proceedings) (Website)


ConferenceInternational Symposium on Combinatorial Search 2019
Abbreviated titleSoCS 2019
CountryUnited States of America
Internet address

Cite this