Scales multi-agent path finding to 1000 agents with near-linear runtime by decoupling geometric planning from execution-time conflict resolution.
March 31, 2026
Original Paper
Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding
arXiv · 2603.26684
The Takeaway
By replacing centralized, time-expanded models with spatial detours (GCP) and local authorization queues (DLC), it avoids the exponential complexity of traditional MAPF solvers. This enables real-time coordination for massive robot fleets in dense environments like automated warehouses.
From the abstract
Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution. In the first stage, Geometric Conflict Preemptio