# Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 31 references that are in the map.
- First posted on arXiv 6 Aug 2024.

## Builds on (most cited first, 9 of 9)

- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [Adapting Behaviour for Learning Progress](https://mlsanity.com/paper/1912.06910/) (2019)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [Online Learning for Scheduling MIP Heuristics](https://mlsanity.com/paper/2304.03755/) (2023)
- [Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search](https://mlsanity.com/paper/2402.01961/) (2024)
- [Confidence-Based Curriculum Learning for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.05860/) (2024)

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

- [Multi UAVs Preflight Planning in a Shared and Dynamic Airspace](https://mlsanity.com/paper/2602.12055/) (2026)

## Abstract (arXiv)

Anytime multi-agent path finding (MAPF) is a promising approach to scalable path optimization in multi-agent systems. MAPF-LNS, based on Large Neighborhood Search (LNS), is the current state-of-the-art approach where a fast initial solution is iteratively optimized by destroying and repairing selected paths of the solution. Current MAPF-LNS variants commonly use an adaptive selection mechanism to choose among multiple destroy heuristics. However, to determine promising destroy heuristics, MAPF-LNS requires a considerable amount of exploration time. As common destroy heuristics are non-adaptive, any performance bottleneck caused by these heuristics cannot be overcome via adaptive heuristic selection alone, thus limiting the overall effectiveness of MAPF-LNS in terms of solution cost. In this paper, we propose Adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-Learning (ADDRESS) as a single-destroy-heuristic variant of MAPF-LNS. ADDRESS applies restricted Thompson Sampling to the top-K set of the most delayed agents to select a seed agent for adaptive LNS neighborhood generation. We evaluate ADDRESS in multiple maps from the MAPF benchmark set and demonstrate cost improvements by at least 50% in large-scale scenarios with up to a thousand agents, compared with the original MAPF-LNS and other state-of-the-art methods.