MAPF-LNS2:fast repairing for Multi-Agent Path Finding via large neighborhood search

Sie sind hier: Homepage > Suche

MAPF-LNS2:fast repairing for Multi-Agent Path Finding via large neighborhood search

Freier Zugriff

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

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.

Zugriff

Download

Exportieren, teilen und zitieren

Dokumentinformationen

Titel :

MAPF-LNS2:fast repairing for Multi-Agent Path Finding via large neighborhood search

Beteiligte:

Li, Jiaoyang (Autor:in) / Chen, Zhe (Autor:in) / Harabor, Daniel (Autor:in) / Stuckey, Peter J. (Autor:in) / Koenig, Sven (Autor:in) / Honavar, Vasant / Spaan, Matthijs

Erscheinungsdatum :

2022-01-01

Anmerkungen:

Li , J , Chen , Z , Harabor , D , Stuckey , P J & Koenig , S 2022 , MAPF-LNS2 : fast repairing for Multi-Agent Path Finding via large neighborhood search . in V Honavar & M Spaan (eds) , 36th AAAI Conference on Artificial Intelligence (AAAI-22) . 36th AAAI Conference on Artificial Intelligence (AAAI-22) , no. 9 , vol. 36 , Association for the Advancement of Artificial Intelligence (AAAI) , Palo Alto CA USA , pp. 10256-10265 , AAAI Conference on Artificial Intelligence 2022 , Online , United States of America , 22/02/22 . https://doi.org/10.1609/aaai.v36i9.21266

DOI :

https://doi.org/10.1609/aaai.v36i9.21266

Medientyp :

Aufsatz (Zeitschrift)

Format :

Elektronische Ressource

Sprache :

Englisch

Schlagwörter :

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

Klassifikation :

DDC: