Searching with Consistent Prioritization for Multi-Agent Path Finding

Authors

  • Hang Ma University of Southern California
  • Daniel Harabor Monash University
  • Peter J. Stuckey The University of Melbourne
  • Jiaoyang Li University of Southern California
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/aaai.v33i01.33017643

Abstract

We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time.

Downloads

Published

2019-07-17

How to Cite

Ma, H., Harabor, D., Stuckey, P. J., Li, J., & Koenig, S. (2019). Searching with Consistent Prioritization for Multi-Agent Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 7643-7650. https://doi.org/10.1609/aaai.v33i01.33017643

Issue

Section

AAAI Technical Track: Planning, Routing, and Scheduling