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 PaperOtherpeer-review

5 Citations (Scopus)

Abstract

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for a cooperative team of moving 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 (including prioritized and rule-based algorithms) that can solve very large practical problems but usually find low-quality solutions. In this paper, we consider a third approach that combines both advantages: anytime algorithms that quickly find an initial solution, including for large problems, and that subsequently improve the solution to near-optimal as time progresses. To improve the solution, we replan subsets of agents using Large Neighborhood Search, a popular meta-heuristic often applied in combinatorial optimization. Empirically, we compare our algorithm MAPF-LNS to the state-of-the-art anytime MAPF algorithm anytime BCBS and report significant gains in scalability, runtime to the first solution, and speed of improving solutions.

Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems
EditorsUlle Endriss, Ann Nowé
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1581-1583
Number of pages3
ISBN (Electronic)9781450383073
DOIs
Publication statusPublished - 2021
EventInternational Conference on Autonomous Agents and Multiagent Systems 2021 - Online, United Kingdom
Duration: 3 May 20217 May 2021
Conference number: 20th
https://dl.acm.org/doi/proceedings/10.5555/3463952 (Proceedings)
https://aamas2021.soton.ac.uk (Website)

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
PublisherAssociation for Computing Machinery (ACM)
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

ConferenceInternational Conference on Autonomous Agents and Multiagent Systems 2021
Abbreviated titleAAMAS 2021
Country/TerritoryUnited Kingdom
Period3/05/217/05/21
Internet address

Keywords

  • Anytime Algorithms
  • Large Neighborhood Search
  • Multi-Agent Path Finding

Cite this