February
2022
MAPF-LNS2: Repairing Multi-Agent Path Finding via Large Neighborhood Search
Authors:
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 LNS2 based on large neighborhood search for solving MAPF efficiently. Starting from a set of paths that contain collisions, 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 LNS2 against a variety of state-of-the-art MAPF algorithms, including Prioritized Planning with random restarts, EECBS, and PPS, and show that LNS2 runs significantly faster than them while still providing near-optimal solutions in most cases. With a runtime limit of just 5 minutes, LNS2 solves 80 percent 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.
copied = false, 2000);
">
@conference{Li-2022-131388,
author = {Jiaoyang Li And Zhe Chen And Daniel Harabor And Peter J. Stuckey And Sven Koenig},
title = {MAPF-LNS2: Repairing Multi-Agent Path Finding via Large Neighborhood Search},
booktitle = {Proceedings of 36th AAAI Conference on Artificial Intelligence (AAAI '22)},
year = {2022},
month = {February},
}
author = {Jiaoyang Li And Zhe Chen And Daniel Harabor And Peter J. Stuckey And Sven Koenig},
title = {MAPF-LNS2: Repairing Multi-Agent Path Finding via Large Neighborhood Search},
booktitle = {Proceedings of 36th AAAI Conference on Artificial Intelligence (AAAI '22)},
year = {2022},
month = {February},
}