Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Improved Anonymous Multi-Agent Path Finding Algorithm
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 Bulk Search, a search over the flow network used in reduction-based optimal anonymous MAPF that compresses and expands connected sequences of same-vertex states in bulks, yielding a faster makespan-optimal AMAPF solver that solves all MovingAI instances within 30 s.
Problem
Optimal makespan Anonymous Multi-Agent Path Finding (AMAPF) via reduction to maximum flow is bottlenecked by the very large auxiliary flow network searched with Ford-Fulkerson.
Approach
Instead of expanding single network nodes, group same-vertex nodes into connected-sequences linked by wait and restriction edges and expand them as implicit bulks ordered by height, generating only the lowest-height accessible successor per connected sequence.
Key results
- flow-BS solves all instances on all 33 MovingAI maps within the 30 s timeout, while the flow baseline solves only 0% to 100% depending on map (e.g., 3% on maze-128-128-1, 0% on orz900d).
- flow-BS solves the hardest instance (orz900d, scenario 20, 256 agents) in 17 s.
- Expansions of flow-BS grow far less with the makespan bound T than flow, which expands an increasing number of nodes as T grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · maze-128-128-1 | success rate: 3% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · maze-128-128-2 | success rate: 4% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · maze-128-128-10 | success rate: 17% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · ost003d | success rate: 57% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · lak303d | success rate: 44% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · den520d | success rate: 16% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · w_woundedcoast | success rate: 1% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · warehouse-20-40-10-2-2 | success rate: 8% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · brc202d | success rate: 1% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · Paris_1_256 | success rate: 5% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · Berlin_1_256 | success rate: 6% -> 100% | Helped |
| Use Bulk Search instead of standard Ford-Fulkerson path search | AMAPF solver · Boston_0_256 | success rate: 4% -> 100% | Helped |
Limitations
- Current algorithm handles only unit-cost explicit flow networks; extension to costs (min-cost max-flow) left to future work.
- Theoretical reduction bound depends on number of connected sequences; in practice few states per sequence are expanded individually, so performance relies on that assumption.
- Evaluation is restricted to makespan-optimal AMAPF on MAPF benchmark maps with a single 30 s timeout.
Experimental setup
Datasets: MovingAI MAPF benchmark
Benchmarks: MovingAI MAPF benchmark (33 maps, 25 random scenarios) Iron Harvest benchmark
Metrics: success rate within 30 s timeout number of expansions runtime per expansion
Baselines: flow (Ford-Fulkerson-based AMAPF solver)
Builds on: Ford-Fulkerson algorithm AMAPF-to-maximum-flow reduction
Closest papers by meaning
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.88)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.86)
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.86)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.86)
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.86)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.86)
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.