MAPF-LNS2: fast repairing for 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 problem of planning collision-free paths for multiple agents in a shared environment. In this paper, we propose a novel algorithm MAPF-LNS2 based on large neighborhood search for solving MAPF efficiently. Starting from a set of paths that contain collisions, MAPF-LNS2 repeatedly selects a subset of colliding agents and replans their paths to reduce the number of collisions until the paths become collision-free. We compare MAPF-LNS2 against a variety of state-of-the-art MAPF algorithms, including Prioritized Planning with random restarts, EECBS, and PPS, and show that MAPF-LNS2 runs significantly faster than them while still providing near-optimal solutions in most cases. MAPF-LNS2 solves 80% of the random-scenario instances with the largest number of agents from the MAPF benchmark suite with a runtime limit of just 5 minutes, which, to our knowledge, has not been achieved by any existing algorithms.
Original languageEnglish
Title of host publication36th AAAI Conference on Artificial Intelligence (AAAI-22)
EditorsVasant Honavar, Matthijs Spaan
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages10256-10265
Number of pages10
ISBN (Electronic)1577358767, 9781577358763
DOIs
Publication statusPublished - 2022
EventAAAI Conference on Artificial Intelligence 2022 - Online, United States of America
Duration: 22 Feb 20221 Mar 2022
Conference number: 36th
https://aaai-2022.virtualchair.net/index.html (Website)
https://aaai.org/conference/aaai/aaai-22/
https://ojs.aaai.org/index.php/AAAI/issue/view/510 (Proceedings)

Publication series

Name36th AAAI Conference on Artificial Intelligence (AAAI-22)
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number9
Volume36
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence 2022
Abbreviated titleAAAI 2022
Country/TerritoryUnited States of America
CityOnline
Period22/02/221/03/22
Internet address

Keywords

  • Search And Optimization (SO)
  • Planning
  • Routing
  • And Scheduling (PRS)
  • Multiagent Systems (MAS)

Cite this