Projects per year
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 language | English |
---|---|
Title of host publication | 36th AAAI Conference on Artificial Intelligence (AAAI-22) |
Editors | Vasant Honavar, Matthijs Spaan |
Place of Publication | Palo Alto CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 10256-10265 |
Number of pages | 10 |
ISBN (Electronic) | 1577358767, 9781577358763 |
DOIs | |
Publication status | Published - 2022 |
Event | AAAI Conference on Artificial Intelligence 2022 - Online, United States of America Duration: 22 Feb 2022 → 1 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
Name | 36th AAAI Conference on Artificial Intelligence (AAAI-22) |
---|---|
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Number | 9 |
Volume | 36 |
ISSN (Print) | 2159-5399 |
ISSN (Electronic) | 2374-3468 |
Conference
Conference | AAAI Conference on Artificial Intelligence 2022 |
---|---|
Abbreviated title | AAAI 2022 |
Country/Territory | United States of America |
City | Online |
Period | 22/02/22 → 1/03/22 |
Internet address |
Keywords
- Search And Optimization (SO)
- Planning
- Routing
- And Scheduling (PRS)
- Multiagent Systems (MAS)
Projects
- 2 Finished
-
Improved Constraint Reasoning for Robust Multi-agent Path Planning
Stuckey, P., Harabor, D., Le Bodic, P., Gange, G. & Koenig, S.
1/01/20 → 31/12/24
Project: Research
-
Personalised Public Transport
Harabor, D., Moser, I. & Ronald, N.
24/06/19 → 31/12/24
Project: Research