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

Fernando Salanova, Cristian Mahulea, Eduardo Montijano · 2026

Read Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding by Fernando Salanova, Cristian Mahulea, Eduardo Montijano (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26684.txt.

Introduction

Salanova, Montijano, and Mahulea split multi-agent path finding into geometric planning and execution-time control. Central solvers with time-expanded models scale poorly when crowds of agents share one graph. Their first stage plans paths one agent at a time with A*, raising costs on vertices that earlier paths already use. A local controller then runs the paths, using per-vertex queues and added waits to dodge clashes. On standard maps with up to 1000 agents, runtime grows near-linearly and every feasible case succeeds.

Catalog record

CREATORFernando Salanova, Cristian Mahulea, Eduardo Montijano
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30042
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26684

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding Thanks: This work has been supported by the ONR Global grant N62909-24-1-2081, Spanish project PID2024-159284NB-I00 funded by MCIN/AEI/10.13039/501100011033, by ERDF A way of making Europe and by the European Union NextGenerationEU/PRTR, and DGA T45-23R and T64-23R. Fernando Salanova, Cristian Mahulea, Eduardo Montijano 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 Preemption (GCP) plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a Decentralized Local Controller (DLC) executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions only when required to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an empirically near-linear runtime trend and attains a 100% success rate on instances satisfying the geometric feasibility assumption. On bottleneck-heavy maps, GCP reduces synchronization-induced waiting and often improves SOC on bottleneck-heavy maps I Introduction Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics, logistics and large-scale system control, including within the Discrete Event Systems (DES). Given multiple agents moving on a shared graph, the goal is to compute collision-free trajectories that avoid (i) vertex conflicts (two agents occupying the same vertex at the same time) and (ii) edge-swap conflicts (two agents traversing the same edge in opposite directions at the same time), while minimizing the sum-of-costs (SOC), i.e., the sum of goal-arrival times. MAPF is NP-hard due to the combinatorial growth of the joint state space, and optimal centralized solvers such as Conflict-Based Search (CBS) [ 1 ] rely on explicit coupling across agents, resulting in prohibitive runtime and memory requirements at scale. From a DES perspective, related multi-robot coordination problems have also been addressed using formal supervisory control (e.g., Petri-net-based resource sharing and mutual exclusion) [ 2 ] . A key limitation of many MAPF formulations is the dependence on time-expanded representations. These approaches discretize time and model each agent as evolving synchronously in discrete steps, so collision-avoidance constraints are enforced at every time index. In practice, this implies step-by-step synchronization: before advancing to the next step, the system must ensure that all agents have reached their intended vertices and that no conflicts (vertex or edge-swap) occur at that time. Such lockstep execution typically requires a centralized coordination layer (or an equivalent global consensus mechanism) because conflict detection and resolution depend on the simultaneous state of all agents. This modeling assumption is often convenient algorithmically, but it becomes increasingly problematic in large-scale robotic teams, where communication delays, asynchronous actuation, and distributed control architectures make frequent global synchronization costly or impractical. This paper adopts an execution viewpoint in which agents progress asynchronously along geometric paths and synchronize only when local contention must be serialized. We introduce a two-stage prioritized framework. First, Geometric Conflict Preemption (GCP) reduces downstream congestion by penalizing entries into vertices already used by higher-priority paths, favoring inexpensive geometric detours over future waiting. Second, a Decentralized Local Controller (DLC) enforces collision-free execution via local per-vertex authorization queues, inserting wait actions only when necessary. The resulting separation between geometric planning and on-demand temporal coordination improves scalability while preserving competitive SOC in constrained environments. Contributions. The main contributions are: (i) a congestion-aware prioritized planner (GCP) that inflates vertex-entry costs based on higher-priority geometric footprints, without building a time-expanded graph; (ii) a queue-based local execution mechanism (DLC) that guarantees collision-free asynchronous execution by serializing only contested vertex entries; and (iii) an empirical evaluation up to 1000 agents showing near-linear scaling trends and improved SOC in bottleneck-heavy maps via reduced waiting. II Related Work MAPF algorithms are commonly grouped into optimal solvers, bounded-suboptimal solvers, and highly scalable (often decoupled) solvers [ 3 ] . Optimal centralized methods, exemplified by Conflict-Based Search (CBS) [ 1 ] , guarantee minimum SOC solutions but can exhibit exponential runtime and high memory usage in dense instances, limiting applicability to large teams. To improve scalability, bounded-suboptimal methods trade optimality for speed while bounding solution quality. Enhanced CBS (ECBS) [ 4 ] and Explicit Estimation CBS (EECBS) [ 5 ] accelerate CBS using inadmissible heuristics and focal search, but remain centralized and still rely on conflict-tree exploration. As a result, scalability is typically limited to a few hundred agents in constrained environments. For problems with several hundred agents or more, decoupled methods become essential due to their near-linear runtime complexity with respect to the number of agents, since planning is performed sequentially or independently once higher-priority decisions are fixed. Prioritized MAPF (P-MAPF) [ 6 ] is the representative approach, planning agents sequentially according to a fixed priority ordering. The main drawback is solution quality: higher-priority paths become hard constraints for subsequent agents, often causing cascaded waiting and SOC inflation. This inflation is exacerbated when time is modeled explicitly via space–time reservation tables, which enforce step-by-step synchronization and can introduce repeated waiting actions to resolve conflicts [ 7 ] . Related challenges appear in continuous-time MAPF, where guaranteeing collision-free motion over real-valued time while maintaining completeness and soundness remains an active topic [ 8 ] . Our method belongs to the class of scalable, decoupled MAPF approaches, while explicitly targeting congestion mitigation to improve solution quality. In particular, it modifies costs to discourage geometric overlap, in the spirit of congestion-aware planning [ 9 ] and traffic-flow incentives in lifelong MAPF [ 10 ] . Unlike iterative replanning or flow-based methods, Geometric Conflict Preemption (GCP) applies a one-shot cost inflation derived from higher-priority geometric paths, without constructing a time-expanded graph. Residual conflicts are resolved during execution by a queue-based local controller. The resulting framework remains decoupled and scalable, and it is complete for instances satisfying certain geometric feasibility conditions. III Problem Definition The environment is a connected undirected graph G=(V,E) with nonnegative edge costs C:E\rightarrow\mathbb{R}_{\geq 0} . Unless stated otherwise, all edges have unit cost. A set of agents A=\{a_{1},\dots,a_{k}\} is given, where each agent a_{i} has a start vertex s_{i}\in V and a goal vertex g_{i}\in V . We assume that all starts and all goals are pairwise distinct. A path for agent a_{i} is a finite sequence of vertices p_{i}=(v_{i,0},v_{i,1},\dots,v_{i,\ell_{i}}) such that v_{i,0}=s_{i} and v_{i,\ell_{i}}=g_{i} . Paths are purely geometric and do not encode temporal information. To define time execution, conflicts, and SOC, we use the standard discrete-time semantics of MAPF. A trajectory for agent a_{i} is a function \tau_{i}:\mathbb{N}_{\geq 0}\to V such that there exists a finite T_{i}\in\mathbb{N}_{\geq 0} satisfying \tau_{i}(0)=s_{i} , \tau_{i}(T_{i})=g_{i} , and \tau_{i}(t)=g_{i} for all t\geq T_{i} . For each t\geq 0 , either (\tau_{i}(t),\tau_{i}(t+1))\in E or \tau_{i}(t)=\tau_{i}(t+1) . This timing model is used only to formalize collisions and cost; both planning stages of our method operates on geometric paths on G and does not construct a time-expanded graph. A set of trajectories \mathcal{T}=\{\tau_{1},\dots,\tau_{k}\} is collision-free if for all

Read the complete text