Anytime Multi-Agent Path Finding via Large Neighborhood Search

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, Sven Koenig

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

Abstract

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Joint Conference on Artificial Intelligence
EditorsZhi-Hua Zhou
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages4127-4135
Number of pages9
ISBN (Electronic)9780999241196
DOIs
Publication statusPublished - 2021
EventInternational Joint Conference on Artificial Intelligence 2021 - Virtual, Montreal, Canada
Duration: 19 Aug 202127 Aug 2021
Conference number: 30th
https://www.ijcai.org/proceedings/2021/ (Proceedings)
https://ijcai-21.org (Website)

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2021
Abbreviated titleIJCAI 2021
Country/TerritoryCanada
CityMontreal
Period19/08/2127/08/21
Internet address

Keywords

  • Planning and Scheduling
  • Search in Planning and Scheduling
  • Agent-based and Multi-agent Systems
  • Multi-agent Planning
  • Robotics
  • Motion and Path Planning

Cite this