Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BALANCE, an LNS framework for anytime multi-agent path finding that uses a bi-level multi-armed bandit (roulette wheel, UCB1, or Thompson Sampling) to adapt destroy heuristics and neighborhood sizes online.
Problem
Anytime multi-agent path finding with LNS relies on a fixed neighborhood size and greedy destroy-heuristic selection (roulette wheel), limiting exploration and flexibility and requiring prior tuning or offline ML.
Approach
A bi-level bandit scheme: a top-level bandit picks a destroy heuristic and a per-heuristic bottom-level bandit picks the neighborhood size exponent, both updated online with the cost improvement as reward, with Thompson Sampling performing best.
Key results
- BALANCE variants significantly outperform MAPF-LNS and MAPF-ML-LNS by at least 50% in sum of delays when the number of agents m >= 350 under a 60-second budget.
- BALANCE (Thompson) slightly outperforms the other BALANCE variants in the random, ost003d, and city maps.
- Roulette and UCB1 strongly prefer the random destroy heuristic, whereas Thompson Sampling keeps exploring and mostly prefers N=32 on ost003d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BALANCE instead of MAPF-LNS or MAPF-ML-LNS | Anytime MAPF · MAPF benchmark maps, m ≥ 350 agents | sum of delays: at least 50% | Helped |
| use Thompson Sampling instead of UCB1 or roulette selection | BALANCE · random, ost003d, and city maps | sum of delays | Helped |
| use a bandit algorithm instead of random uniform selection | BALANCE · random and city maps; 200 and 350 agents | sum of delays | Helped |
| increase neighborhood-size options to E = 3 (ablation) | BALANCE variants · random and city maps; 128-second time budget | sum of delays | Helped |
| increase neighborhood-size options beyond E = 3 (ablation) | BALANCE variants · random and city maps; 128-second time budget | sum of delays | No clear effect |
| use a joint arm space instead of the bi-level bandit scheme | Thompson Sampling MAPF-LNS · random, warehouse, ost003d, den520d, and city maps | sum of delays | Hurt |
| use E = 5 neighborhood-size options with random uniform selection (ablation) | BALANCE (Random) · ost003d | sum of delays | Hurt |
Surprising findings
- The joint arm space Thompson Sampling variant also outperforms the state-of-the-art, though it is consistently outperformed by the bi-level BALANCE variants.
Limitations
- Assumes stationary optimum; non-stationary bandit variants are deferred to future work.
- Performance gains are smaller or absent for small agent counts; joint-arm variant scales quadratically with options.
- Thompson Sampling requires choosing prior parameters, though near-uniform priors were used.
Experimental setup
Datasets: MAPF benchmark maps (random-32-32-10, warehouse-10-20-10-2-1, ost003d, den520d, Paris_1_256)
Benchmarks: MAPF benchmark maps random-32-32-10 warehouse-10-20-10-2-1 ost003d den520d Paris_1_256
Metrics: sum of delays (total cost)
Baselines: MAPF-LNS MAPF-ML-LNS Joint Arm Space (Thompson) BALANCE (Random) Empirically Best Choice
Builds on: MAPF-LNS prioritized planning UCB1 Thompson Sampling
Closest papers by meaning
- Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic (AAAI 2025 · similarity 0.94)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.89)
- LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding (AAAI 2025 · similarity 0.88)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.88)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.87)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.