# Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search

arXiv: https://arxiv.org/abs/2402.01961 · HTML: https://mlsanity.com/paper/2402.01961/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2024.

## Built on by (most cited first, 4 of 4)

- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic](https://mlsanity.com/paper/2408.02960/) (2024)
- [Local Guidance for Configuration-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.19072/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for multiple agents in a shared environment while minimizing the sum of travel time. Since solving the MAPF problem optimally is NP-hard, anytime algorithms based on Large Neighborhood Search (LNS) are promising to find good-quality solutions in a scalable way by iteratively destroying and repairing the paths. We propose Destroy-Repair Operation Parallelism for LNS (DROP-LNS), a parallel framework that performs multiple destroy and repair operations concurrently to explore more regions of the search space within a limited time budget. Unlike classic MAPF approaches, DROP-LNS can exploit parallelized hardware to improve the solution quality. We also formulate two variants of parallelism and conduct experimental evaluations. The results show that DROP-LNS significantly outperforms the state-of-the-art and the variants.