Multi-agent path finding (MAPF) studies the problem of planning conflict-free paths for multiple agents from given start locations to designated goals, with applications in robot-assisted logistics and social navigation. Recent decentralized learned solvers have shown promise for large-scale MAPF, particularly when leveraging foundation models and large datasets. However, most existing methods rely on reactive policies, often resulting in congestion, deadlocks, and degraded generalization in high agent-density environments. To address these limitations, we propose MAPF-World, an autoregressive action world model for MAPF that unifies short-horizon local future prediction and action generation, enabling decision-making beyond immediate local observations. MAPF-World models short-horizon local dynamics by predicting the next local observation and neighboring agents' action intentions, capturing both spatial structures and temporal interaction patterns. We further introduce a spatio-agent positional encoding that integrates spatial awareness with agent-level semantics in Transformer-based architectures, facilitating more coordinated multi-agent behaviors. In addition, we augment existing MAPF benchmarks by introducing an automated map generator grounded in real-world urban layouts, aiming to narrow the gap between synthetic simulation and practical deployment scenarios. Extensive experiments across diverse map types and interaction settings demonstrate that MAPF-World achieves strong performance compared with existing learned solvers. Notably, it exhibits robust zero-shot generalization and maintains a high success rate even as agent density increases.
Figures & tables
Fig. 1 : MAPF-World is a decentralized action–world model for multi-agent path finding (MAPF) under partial observation. Its action branch generates actions, while its world branch predicts short-horizon future local observations to support coordination in crowded and structurally complex scenarios.
Fig. 2 : Architecture of the proposed MAPF-World . Our model is designed as a fast–slow dual-system built on a hierarchical Transformer-based framework. It features a shared (a) backbone for spatio-temporal representations, coupled with two dedicated components: an (b) action branch (fast system) for rapid policy decisions and a (c) world branch (slow system) for local environmental transition prediction. Furthermore, we introduce an improved (d) spatio-agent positional encoding that distinguishes spatial guidance from the local map and semantic states at the agent level.
Fig. 3 : Two operational modes of MAPF-World: (a) MAPF-World-Fast , a reactive system using only the action branch; (b) MAPF-World , a deliberative system integrating both action and world branches, where predicted and default greedy action intentions are interleaved to balance inter-agent coordination and goal-directed behavior.
Fig. 4 : Automated urban map generation pipeline. (a) Geometric data acquisition: road networks are extracted from raw geographic data ( .osm.pbf ). (b) Spatial partitioning: geographic space is partitioned into localized tiles; traversable regions and obstacles are identified with imputation of missing properties, and valid tiles are filtered based on configurable criteria. (c) Grid map generation: tiles are rasterized into discrete occupancy grids, followed by denoising of isolated pixels and narrow gaps, and topological alignment to correct discretization artifacts.
Metric
Random
Mazes
Warehouse
MovingAI
EuropeanCity
(n=128)
(n=128)
(n=1)
(n=128)
(Ours, n=137 )
Size
172 – 212
172 – 212
33×46
642
2562
Free Ratio
0.80±0.06
0.70±0.10
0.84
0.73±0.09
0.46±0.11
CC
2.7±1.9
1.0±0.0
1.0
3.9±3.6
10.1±7.3
NPR
0.78±0.12
0.79±0.27
0.45
0.17±0.07
0.85±0.09
MCW
2.76±0.41
3.59±4.11
4.82
12.9±8.3
2.61±0.47
TABLE I : Structural statistics of MAPF benchmark map families. All metrics are computed using the same pipeline.
Fig. 5 : Success rate and runtime evaluation across benchmark maps. Random and Mazes are in-distribution, while the remaining maps are out-of-distribution (OOD). Among learning-based solvers, MAPF-World shows the smallest performance degradation and near-linear runtime scaling as agent density increases, indicating stronger zero-shot generalization.
Fig. 6 : Comparison between GNN-guided LaGAT variants and MAPF-World variants on the dense warehouse setting.
Fig. 7 : Ablation results of MAPF-World, including prediction horizon, SAPE, C2G tokens, and backbone architecture.
Fig. 8 : Attention comparison between SAPE and sinusoidal PE within the local observation window. SAPE highlights nearby agents and coordination-critical regions.
Dataset
Agents
Maps
Map Size
Seeds
Max Steps
Random
8, 16, … , 96
128
17 × 17, 21 × 21
1
128
Mazes
8, 16, … , 72
128
17 × 17, 21 × 21
1
128
Warehouse
32, 64, … , 192
1
33 × 46
128
128
MovingAI
128, 192, 256
128
64 × 64
1
256
Puzzles
2, 3, 4
16
5 × 5
10
128
European
64, 96, 128
137
256 × 256
1
128
TABLE II : Details of benchmarks used in evaluation.
Fig. 9 : Failure analysis of MAPF-World-Slow. (a) Next-step prediction accuracy by token segment for finished and unfinished agents. (b) ISR under different corridor densities. (c) ISR under different local congestion levels.
Multi-agent pathfinding (MAPF) is a widely used abstraction for multi-robot trajectory planning problems, where multiple homogeneous agents move simultaneously within a shared environment. Although solving MAPF optimally is NP-hard, scalable and efficient solvers are critical for real-world applications such as logistics and search-and-rescue. To this end, the research community has proposed various decentralized suboptimal MAPF solvers that leverage machine learning. Such methods frame MAPF (from a single agent perspective) as a Dec-POMDP where at each time step an agent has to decide an action based on the local observation and typically solve the problem via reinforcement learning or imitation learning. We follow the same approach but additionally introduce a learnable communication module tailored to enhance cooperation between agents via efficient feature sharing. We present the Local Communication for Multi-agent Pathfinding (LC-MAPF), a generalizable pre-trained model that applies multi-round communication between neighboring agents to exchange information and improve their coordination. Our experiments show that the introduced method outperforms the existing learning-based MAPF solvers, including IL and RL-based approaches, across diverse metrics in a diverse range of (unseen) test scenarios. Remarkably, the introduced communication mechanism does not compromise LC-MAPF's scalability, a common bottleneck for communication-based MAPF solvers.
Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk +5
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.
Jingtian Yan, Shuai Zhou, He Jiang +2
This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.
Multi-Agent Path Finding (MAPF) is a coordination problem that requires computing globally consistent, collision-free trajectories from individual start positions to assigned goal positions under combinatorial planning complexity. In dense environments, suboptimal initial plans induce compound conflicts that hinder feasible repair. For repair-based solvers like LNS2, initial plan quality critically affects downstream repair, yet this factor remains underexplored. We propose DiffLNS, a hybrid framework that integrates a discrete denoising diffusion probabilistic model (D3PM) with LNS2. The D3PM serves as an initializer with sparse social attention that learns a spatiotemporal prior over coordinated multi-agent action trajectories from expert demonstrations and samples multiple joint plans. Operating directly on the categorical action space, our discrete diffusion preserves the MAPF action structure and samples from a multimodal joint-plan distribution to produce diverse drafts well suited for neighborhood repair. These drafts act as warm starts for downstream repair, which completes unfinished trajectories and resolves remaining conflicts under hard MAPF constraints. Experimental results show that despite being trained only on instances with at most 96 agents, the initializer generalizes to scenarios with up to 312 agents at inference time. Across 20 complex and congested settings, DiffLNS achieves an average success rate of 95.8%, outperforming the strongest tested baseline by 9.6 percentage points and matching or exceeding all baselines in all 20 settings. To the best of our knowledge, this is the first work to leverage discrete diffusion for warm-starting an LNS-based MAPF solver.
Yuanzhe Wang, Tian Zhi, Zihang Wei +8
State Key Lab of Processors, Institute of Computing Technology, CAS · School of Advanced Interdisciplinary Sciences, CAS · University of Chinese Academy of Sciences +1