Journal article
Pairwise symmetry reasoning for multi-agent path finding search
Jiaoyang Li, Daniel Harabor, Peter J Stuckey, Hang Ma, Graeme Gange, Sven Koenig
ARTIFICIAL INTELLIGENCE | ELSEVIER | Published : 2021
Abstract
Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that asks us to plan collision-free paths for a team of cooperative agents. In this work, we show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry, which occurs when two agents have many different paths to their target locations, all of which appear promising, but every combination of them results in a collision. We identify several classes of pairwise symmetries and show that each one arises commonly in practice and can produce an exponential explosion in the space of possible collision resolutions, leading to unacceptable runtimes for current state-of-the-art (bounded-..
View full abstractGrants
Awarded by Australian Research Council (ARC)
Awarded by National Science Foundation (NSF)
Awarded by Natural Sciences and Engineering Research Council of Canada (NSERC)
Awarded by Australian Research Council
Funding Acknowledgements
The research at Monash University was partially supported by Australian Research Council (ARC) under grant num-bers DP200100025 and DP190100013 as well as a gift from Amazon. The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1409987, 1724392, 1817189, 1837779, and 1935712 as well as a gift from Amazon. The research at Simon Fraser University was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under grant number RGPIN2020-06540. The views and conclusions con-tained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies or the U.S. government.