# Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 28 Dec 2023.

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

- [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)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Adapting Behaviour for Learning Progress](https://mlsanity.com/paper/1912.06910/) (2019)
- [Online Learning for Scheduling MIP Heuristics](https://mlsanity.com/paper/2304.03755/) (2023)
- [Memory Bounded Open-Loop Planning in Large POMDPs using Thompson Sampling](https://mlsanity.com/paper/1905.04020/) (2019)
- [Adaptive Thompson Sampling Stacks for Memory Bounded Open-Loop Planning](https://mlsanity.com/paper/1907.05861/) (2019)

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

- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.12623/) (2025)
- [Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming](https://mlsanity.com/paper/2405.11305/) (2024)
- [Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic](https://mlsanity.com/paper/2408.02960/) (2024)
- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)
- [Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention](https://mlsanity.com/paper/2605.13296/) (2026)
- [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 large-scale multi-agent systems. State-of-the-art anytime MAPF is based on Large Neighborhood Search (LNS), where a fast initial solution is iteratively optimized by destroying and repairing a fixed number of parts, i.e., the neighborhood, of the solution, using randomized destroy heuristics and prioritized planning. Despite their recent success in various MAPF instances, current LNS-based approaches lack exploration and flexibility due to greedy optimization with a fixed neighborhood size which can lead to low quality solutions in general. So far, these limitations have been addressed with extensive prior effort in tuning or offline machine learning beyond actual planning. In this paper, we focus on online learning in LNS and propose Bandit-based Adaptive LArge Neighborhood search Combined with Exploration (BALANCE). BALANCE uses a bi-level multi-armed bandit scheme to adapt the selection of destroy heuristics and neighborhood sizes on the fly during search. We evaluate BALANCE on multiple maps from the MAPF benchmark set and empirically demonstrate cost improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios. We find that Thompson Sampling performs particularly well compared to alternative multi-armed bandit algorithms.