Searching with consistent prioritization for multi-agent path finding

Hang Ma, Daniel Harabor, Peter J. Stuckey, Jiaoyang Li, Sven Koenig

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

162 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence
EditorsPascal Van Hentenryck, Zhi-Hua Zhou
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages7643-7650
Number of pages8
ISBN (Electronic)9781577358091
DOIs
Publication statusPublished - 2019
EventAAAI Conference on Artificial Intelligence 2019 - Honolulu, United States of America
Duration: 27 Jan 20191 Feb 2019
Conference number: 33rd
https://aaai.org/Conferences/AAAI-19/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Number1
Volume33
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence 2019
Abbreviated titleAAAI 2019
Country/TerritoryUnited States of America
CityHonolulu
Period27/01/191/02/19
Internet address

Cite this