Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic
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 ADDRESS, a single-destroy-heuristic MAPF-LNS variant that uses restricted Thompson Sampling over the top-K most delayed agents to pick seed agents, outperforming MAPF-LNS, MAPF-LNS2, BALANCE and LaCAM* on large-scale instances.
Problem
Anytime multi-agent path finding with LNS is limited by stationary destroy heuristics and the time needed to select good ones; the agent-based heuristic's greedy max-delay seed selection with tabu list is a bottleneck with many agents.
Approach
Replace the adaptive selection among stationary destroy heuristics with a single adaptive destroy heuristic: per-agent Beta success/failure counters, restricted Thompson Sampling over the top-K most delayed agents to choose the seed agent, and binary success rewards from LNS improvements.
Key results
- ADDRESS reduces sum of delays by at least 50% in large-scale scenarios with up to 1000 agents compared with original MAPF-LNS and other state-of-the-art methods.
- On Den520d and City with 700 agents, ADDRESS (Thompson Sampling) achieves lower sum of delays and AUC than the agent-based MAPF-LNS heuristic across time budgets; K=32 works best in all test maps.
- ADDRESS significantly outperforms LaCAM* on all five maps; e.g., Warehouse 3,047.8 vs 70,107.8 sum of delays at 60 seconds, while it does not outperform baselines on the Random map.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ADDRESS instead of LaCAM* | Anytime MAPF · Random-32-32-20 | sum of delays: 3,343.52 ± 120 vs 10,146.4 ± 1399 | Helped |
| Use ADDRESS instead of LaCAM* | Anytime MAPF · Ost003d | sum of delays: 10,788.4 ± 1219 vs 38,632 ± 3925 | Helped |
| Use ADDRESS instead of LaCAM* | Anytime MAPF · Den520d | sum of delays: 2,646.4 ± 433 vs 33,604.4 ± 3823 | Helped |
| Use ADDRESS instead of LaCAM* | Anytime MAPF · Warehouse-20-40-10-2-2 | sum of delays: 3,047.8 ± 2165 vs 70,107.8 ± 911 | Helped |
| Use ADDRESS instead of LaCAM* | Anytime MAPF · Paris_1_256 | sum of delays: 2,645.1 ± 772 vs 48,760.6 ± 614 | Helped |
| Restrict seed selection to the top-K delayed agents (ablation) | ADDRESS with Thompson Sampling · Den520d and City, 700 agents | sum of delays | Helped |
| Vary K with ε-Greedy seed selection (ablation) | ADDRESS · Den520d and City, 700 agents | sum of delays | Mixed |
| Use Thompson Sampling instead of ε-Greedy (ablation) | ADDRESS · Den520d and City, 700 agents | sum of delays | Helped |
| Use ADDRESS instead of the original agent-based destroy heuristic | MAPF-LNS · Den520d and City, 700 agents | sum of delays | Helped |
| Use ADDRESS instead of the original agent-based destroy heuristic | MAPF-LNS · Den520d and City, 700 agents | AUC | Helped |
| Add the ADDRESS heuristic to MAPF-LNS while retaining other destroy heuristics (ablation) | MAPF-LNS · All evaluated maps, time budget below 120 seconds | AUC | Helped |
| Use standalone ADDRESS instead of MAPF-LNS with the ADDRESS heuristic and other destroy heuristics | MAPF-LNS · Den520d, Warehouse, and City, 700 agents | sum of delays | Helped |
Surprising findings
- ADDRESS does not outperform the baselines in the smaller-scale Random map, where sorting and Thompson Sampling overhead outweighs its benefits.
- The map-based heuristic dominates on the Random map, so MAPF-LNS and BALANCE perform better there.
Limitations
- Underperforms baselines on small-scale scenarios such as the Random map due to sorting and sampling overhead.
- Evaluated only on MAPF; applicability to TSP, MILP, VRP is deferred to future work.
- Epsilon-Greedy variant is more sensitive to K than Thompson Sampling.
Experimental setup
Datasets: MAPF benchmark maps (Random-32-32-20, Ost003d, Den520d, Warehouse-20-40-10-2-2, Paris_1_256)
Benchmarks: MAPF benchmark maps Random-32-32-20, Ost003d, Den520d, Warehouse-20-40-10-2-2, Paris_1_256
Metrics: sum of delays area under the curve (AUC)
Baselines: MAPF-LNS MAPF-LNS2 BALANCE LaCAM* epsilon-Greedy ADDRESS
Builds on: MAPF-LNS Thompson Sampling BALANCE prioritized planning
Closest papers by meaning
- Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search (AAAI 2024 · similarity 0.94)
- LNS2+RL: Combining Multi-agent Reinforcement Learning with Large Neighborhood Search in Multi-agent Path Finding (AAAI 2025 · similarity 0.90)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.90)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.89)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.89)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.88)
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.