Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding
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.
Cite
Text
Li et al. "Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33016087Markdown
[Li et al. "Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/li2019aaai-symmetry/) doi:10.1609/AAAI.V33I01.33016087BibTeX
@inproceedings{li2019aaai-symmetry,
title = {{Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding}},
author = {Li, Jiaoyang and Harabor, Daniel and Stuckey, Peter J. and Ma, Hang and Koenig, Sven},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {6087-6095},
doi = {10.1609/AAAI.V33I01.33016087},
url = {https://mlanthology.org/aaai/2019/li2019aaai-symmetry/}
}