Abstract
J. Li, Z. Chen, D. Harabor, P. Stuckey and S. Koenig. MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search. In AAAI Conference on Artificial Intelligence (AAAI), pages 10256-10265, 2022.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.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.