Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

A team of researchers has introduced a novel hybrid framework that fundamentally changes how Multi-Agent Path Finding (MAPF) is approached, enabling coordination for up to 1000 agents. The core innovation is decoupling the problem into two distinct phases. First, a Geometric Conflict Preemption (GCP) stage plans paths sequentially using a modified A* search, where costs are inflated for entering spaces reserved by higher-priority agents. This encourages spatial detours upfront without complex time-based reasoning. Second, a Decentralized Local Controller (DLC) executes these geometric plans using simple per-vertex queues, inserting wait actions only at the last moment to resolve conflicts.

This separation of concerns tackles the primary scalability bottleneck of traditional MAPF solvers, which rely on time-expanded models and centralized conflict resolution. The results are significant: the method demonstrates an empirically near-linear runtime trend and achieves a 100% success rate on standard benchmark maps where geometric solutions are possible. Crucially, on maps with heavy bottlenecks, the GCP stage reduces synchronization-induced waiting, often improving the overall sum-of-costs metric. The decentralized execution layer also makes the system more robust and adaptable to real-world execution variances.