Research map / Learning theory and algorithms / Combinatorial and search optimization
Optimal Makespan in a Minute Timespan! A Scalable Multi-Robot Goal Assignment Algorithm for Minimizing Mission Time
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 OM, a centralized algorithm that finds an optimal-makespan robot-goal assignment by lazily computing obstacle-free path costs only for necessary pairs, using forward resumable A* within a bipartite threshold-matching framework.
Problem
Multi-robot goal assignment minimizing makespan (largest movement cost) in obstacle-laden 2D and 3D workspaces, where computing actual path costs for all robot-goal pairs is computationally expensive and limits scalability.
Approach
Initialize robot-goal costs with Euclidean admissible heuristics and compute true obstacle-free A-costs on demand via Forward Resumable A*, only for pairs needed to guarantee optimality of the bottleneck assignment, adapting the bipartite dual method for linear bottleneck assignment.
Key results
- On random 2D workspaces with 400 robots, OM achieves speedups of about 9-38x over Base-1 and 12-48x over Base-2 in runtime, while computing far fewer A-costs (e.g., 6148 vs 9361 NumExp against Base-2 on a 100x100-style setup).
- Plugging OM into TSWAP for initial goal assignment gives an order-of-magnitude speedup in total AMAPF runtime, e.g., 41.8x overall speedup for 400 robots on the warehouse map.
- OM handles 400 robots on benchmark 2D maps in under 30 s on average, whereas CBM takes about 6500 s for only 100 robots on a 100x100 random workspace.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compute A-costs on demand using admissible heuristic costs rather than precomputing every robot-goal path | OM · Random 2D workspaces | Runtime (s): 4.71±1.38 vs 44.08±1.94; 4.71±1.38 vs 225.30±97.00 | Helped |
| Replace TSWAP Bottleneck Assignment with OM for initial goal assignment | TSWAP · Warehouse, 123×321, R=400 | Total Runtime (s): 720.78±466.72 -> 17.23±5.82 | Helped |
| Replace TSWAP Bottleneck Assignment with OM for initial goal assignment | TSWAP · Warehouse, 123×321, R=400 | Makespan: 39.70±8.89 -> 39.32±8.52 | No clear effect |
| Use OM instead of Base-2 for goal assignment | TSWAP · Mansion, 270×133, R=400 | Total Runtime (s): 559.83±216.86 -> 25.92±6.81 | Helped |
| Use OM instead of Base-2 for goal assignment | TSWAP · Den, 257×256, R=400 | Total Runtime (s): 750.50±441.02 -> 25.67±6.94 | Helped |
Surprising findings
- Base-1 (computing all robot-goal costs) outperforms Base-2 at high robot density in 2D workspaces, because Base-2's repeated matching after each edge addition becomes costly.
Limitations
- Optimal only for goal assignment without accounting for robot-robot collision avoidance; collisions handled by decoupled planner.
- Implemented in Python; worst-case complexity is polynomial but high (e.g., R^4 or R^2 Psi terms).
- Experiments run on a single desktop CPU with each experiment averaged over 20 runs; limited to unit-equal-cardinality or minority-entity assignments as defined.
Experimental setup
Datasets: randomly generated 2D grid workspaces Moving AI benchmark 2D maps (warehouse, mansion, den, sydney, shanghai) Warframe 3D workspace
Benchmarks: randomly generated 2D workspaces Sturtevant 2D benchmark maps Warframe 3D workspace
Metrics: runtime NumExp (number of A-cost computations) NumNodeExp (%) speedup makespan
Baselines: Base-1 (Dijkstra-based full cost computation with dual method) Base-2 (TSWAP bottleneck assignment) CBM
Builds on: Reverse Resumable A* Turpin et al. goal assignment TSWAP Conflict-Based Min-Cost-Flow
Closest papers by meaning
- Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding (AAAI 2024 · similarity 0.83)
- Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions (AAAI 2025 · similarity 0.83)
- Online Guidance Graph Optimization for Lifelong Multi-Agent Path Finding (AAAI 2025 · similarity 0.82)
- Abstract Action Scheduling for Optimal Temporal Planning via OMT (AAAI 2024 · similarity 0.82)
- Temporal Task and Motion Planning with Metric Time for Multiple Object Navigation (AAAI 2025 · similarity 0.82)
- Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning (AAAI 2024 · similarity 0.82)
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.