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.
Original language | English |
---|---|
Title of host publication | Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence |
Editors | Pascal Van Hentenryck, Zhi-Hua Zhou |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 7643-7650 |
Number of pages | 8 |
ISBN (Electronic) | 9781577358091 |
DOIs | |
Publication status | Published - 2019 |
Event | AAAI Conference on Artificial Intelligence 2019 - Honolulu, United States of America Duration: 27 Jan 2019 → 1 Feb 2019 Conference number: 33rd https://aaai.org/Conferences/AAAI-19/ |
Publication series
Name | Proceedings of the AAAI Conference on Artificial Intelligence |
---|---|
Publisher | AAAI Press |
Number | 1 |
Volume | 33 |
ISSN (Print) | 2159-5399 |
ISSN (Electronic) | 2374-3468 |
Conference
Conference | AAAI Conference on Artificial Intelligence 2019 |
---|---|
Abbreviated title | AAAI 2019 |
Country/Territory | United States of America |
City | Honolulu |
Period | 27/01/19 → 1/02/19 |
Internet address |