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

This work has been developed in the RoPeRT and COSMOS research lab from Universidad de Zaragoza.

Authors: Fernando Salanova, Cristian Mahulea and Eduardo Montijano

Publication: The work can be reviewed in here. [arXiv]

Brief Description

This paper presents a scalable framework for Multi-Agent Path Finding (MAPF) designed to coordinate large teams of agents—up to 1,000—with empirically near-linear runtime trends. By moving away from traditional time-expanded models that require strict, centralized synchronization, the proposed method overcomes the computational bottlenecks that limit standard solvers in large or dense environments. Instead of enforcing lockstep coordination at every time step, the approach decouples geometric planning from execution, achieving a 100% success rate on feasible instances and significantly improving solution quality in bottleneck-heavy maps by reducing unnecessary waiting times.

The framework operates in two distinct stages. First, Geometric Conflict Preemption (GCP) plans agent paths sequentially using A* on the original graph, rather than a complex time-expanded graph. It mitigates future congestion by artificially inflating the costs of vertices already utilized by higher-priority agents, encouraging lower-priority agents to take spatial detours instead of waiting. Second, the Decentralized Local Controller (DLC) manages execution using local FIFO (First-In-First-Out) authorization queues at each vertex. Agents move asynchronously and are only forced to wait if they are not at the head of the queue for their next target vertex, effectively resolving vertex and edge-swap conflicts locally without global replanning.

Auxiliary code and models of the project: GitHub repo.

Page updated

Report abuse