RMAPF: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search
Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter Stuckey, Sven Koenig
[AAAI-22] Main Track
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 contains 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. With a time limit of just 5 minutes, MAPF-LNS2 managed to solve 80% of the random-scenario instances on all 33 maps with the largest numbers of agents from the MAPF benchmark, which clearly defines the new state-of-the-art suboptimal MAPF algorithm.
Introduction Video
Sessions where this paper appears
-
Poster Session 4
Red 3
-
Poster Session 8
Red 3
