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 PaperOther

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 the Twelfth International Symposium on Combinatorial Search
EditorsPavel Surynek, William Yeoh
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages188-189
Number of pages2
ISBN (Electronic)9781577358084
Publication statusPublished - 2019
EventInternational Symposium on Combinatorial Search 2019 - Napa, United States of America
Duration: 16 Jul 201917 Jul 2019
Conference number: 12th
https://aaai.org/Library/SOCS/socs19contents.php (Proceedings)
http://users.fit.cvut.cz/surynpav/socs2019/main.php?page=introduction (Website)

Conference

ConferenceInternational Symposium on Combinatorial Search 2019
Abbreviated titleSoCS 2019
Country/TerritoryUnited States of America
CityNapa
Period16/07/1917/07/19
Internet address

Cite this