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

Fernando Salanova; Eduardo Montijano; Cristian Mahulea

cs.MAMar 11, 2026

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

Authors: Fernando Salanova, Eduardo Montijano, Cristian Mahulea

Organizations: Dept. of Systems Engineering and Computer Science, University of Zaragoza, Zaragoza, Spain

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 to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an near-linear runtime trend and attains a 100% success rate on instances satisfying the geometric feasibility assumption. Page of the project: https://sites.google.com/unizar.es/multi-agent-path-finding/home

Figures & tables

Fig. 1: Success rate comparison against methods [ 5 ] , [ 6 ] , [ 12 ] (CA* values are consistently 100% and are covered by the red line of our method) (Mean values over 100 iterations).

Fig. 2: Runtime comparison against methods [ 5 ] , [ 6 ] , [ 12 ] (both axes in logarithmic scale). The red ’X’ indicates that the algorithm failed to complete due to timeout (Mean values over 100 iterations).

Fig. 3: Cost comparison against methods [ 5 ] , [ 6 ] , [ 12 ] for Room and Paris maps (Mean values over 100 iterations).

$k$	Method	Diff. of Spatial Cost	Diff. of Temporal Cost	Total Cost	% of Spatial Cost	% of Temporal Cost
250	Cost Update	16%	—	$18\,518$	89.8%	10.2%
250	No Cost Update	—	67%	17529	82%	18%
500	Cost Update	12%	—	40192	76.8%	23.2%
500	No Cost Update	—	201%	$46\,363$	59.4%	40.6%
1000	Cost Update	16%	—	106843	47.6%	52.4%
1000	No Cost Update	—	70%	$138\,874$	31.6%	68.4%

TABLE I: Spatial and temporal cost analysis comparing the proposed method with and without geometric cost inflation. The results illustrate the trade-off between spatial detours and reduced temporal synchronization (waiting) for collision avoidance ( Room map , 30.94% of free space occupied with 1000 agents). Percentages in the first two result columns indicate the relative increase with respect to the alternative configuration.

Paris Map					Room Map
$k$	Priority	Diff. Solved Colls %	Diff Cost %	Total Cost	$k$	Priority	Diff. Solved Colls %	Diff Cost %	Total Cost
100	SPF	100%	—	18092	100	SPF	9%	4%	6982
	LPF	335%	6%	19211		LPF	13%	2%	6851
	CF	40%	9%	19723		CF	16%	12%	7541
	CL	110%	2%	18446		CL	—	—	6723
	Random	—	12%	20356		Random	23%	11%	7448

TABLE II: Comparison of results for different priority policies across maps and agent counts. Percentage values indicate the relative increase of each metric with respect to the best-performing policy.

Explore similar work

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding
Nov 26, 2025Jingtian Yan, Shuai Zhou, He Jiang +2Multi-Robot Motion Planning World Models for Robotics
This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.
The Cost of Classical Multi-Agent Path Finding
Oct 7, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path Finding Graph-Based Planning
Chalmers University of Technology Gothenburg, Sweden
AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding
Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianRobust MAPF Conflict-Based Search
Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

Nov 26, 2025J/K move · Enter open · S save

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding

Jingtian Yan, Shuai Zhou, He Jiang, Stephen F. Smith+1

This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.

Multi-Robot Motion Planning World Models for Robotics World Model-Based Planning Multi-Agent Path Finding

Open paper AskPDF arXiv

Multi-Agent Path Finding (MAPF) studies how to coordinate multiple agents to reach their goals without collisions and underpins a range of large-scale robotic systems, including automated warehousing and manufacturing. Recent advances enable MAPF solvers to compute high-quality plans for hundreds of agents. However, these plans are generated using simplified robot models with discretized time and action spaces. When they are deployed in physical systems, heterogeneous robot dynamics, asynchronous interactions, communication delays, and other real-world factors can lead to substantial deviations from planned performance. We bridge the gap between discrete planning and real-world execution through ExecTimeNet, a learned world model of MAPF execution that predicts how a discrete MAPF solution will unfold on physical robots, mapping each discrete action to its realized execution state, including its wall-clock completion time and the kinodynamic state in which it ends. Building on this capability, we first propose REMAP, an execution-aware MAPF framework that integrates execution-time estimation into planning, guiding the search toward MAPF solutions with improved execution performance. We also introduce ESADG, a post-planning optimization procedure that optimizes the execution schedule of a given MAPF solution while preserving path feasibility. We evaluate proposed frameworks in high-fidelity simulation with up to 300 agents and on physical robots. In simulation, ExecTimeNet predicts the execution state accurately and transfers to unseen maps and agent counts. Across simulation benchmarks spanning diverse map topologies, REMAP reduces delays by up to 21% over baselines, while ESADG achieves up to 40% normalized improvement. On physical hardware, the full pipeline reduces total execution time by up to 15.3%, demonstrating effective transfer from simulation to real-world deployment.

Abstract

Explore similar work

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding

The Cost of Classical Multi-Agent Path Finding

AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding