Decentralized multi-agent path finding (MAPF) with communication requires agents to reach individual goals without collisions under partial observability. Learnable policies trained on expert data provide an effective approach to this problem. However, when several coordinated joint actions are valid in the same context, independently sampling from per-agent distributions can recombine locally valid choices into incompatible joint actions. This failure can arise from the final sampling mechanism even when the per-agent action distributions are learned correctly. DMM (Decentralized Master-Mind) addresses this by replacing one-shot action sampling with discrete, iterative refinement of action intents across communication rounds, inspired by denoising in diffusion models. Agents initialize random action intents and refine them through local communication, coupling their choices before commitment. DMM is pretrained with imitation learning on expert MAPF solutions and further optimized with MICPO, a critic-free group-relative reinforcement-learning method designed for multi-agent, multi-round action refinement. DMM generally achieves higher success rates and lower solution costs than the evaluated learnable baselines. On 1,600 MovingAI tasks, DMM fine-tuned with MICPO solves 1,598, the highest coverage among the evaluated methods, while achieving solution costs close to those of the strongest baselines. DMM also scales to over one million simultaneously acting agents in obstacle-rich environments. These results show that round-level intent refinement can improve joint-action coordination while preserving decentralized execution.
Figures & tables
Figure 1: A symmetric corridor conflict illustrates the limitation of independent per-agent action sampling and the effect of iterative intent refinement. All policies are trained solely on this corridor scenario. (a) Two agents start at opposite ends of a corridor and must swap positions by reaching their assigned goals. (b) At the shared ambiguous state, independent sampling permits four joint outcomes: Blue goes and Red goes are valid, mutual waiting causes a stall, and simultaneous movement causes a collision. (c) Joint-action frequencies obtained from 1,000 samples per independently trained checkpoint, averaged across five checkpoints. LC-MAPF, MAGAT+, and HMAGAT sample each agent’s action independently and distribute probability nearly uniformly over the four outcomes, yielding about 50% valid joint actions. DMM instead concentrates probability on the two valid outcomes. With checkpoints trained at Ktrain=4 , increasing the test-time refinement depth from Ktest=4 to 8 and 12 raises the displayed valid joint-action frequency from 94.8% to 99.6% and 99.9%, respectively.
Figure 2: Overview of DMM for two agents resolving a shared conflict (Section 4 ). Each agent encodes its observation into a latent and initializes an action intent, then exchanges intent-augmented messages over K rounds while refining its intent toward successive votes. In this example, the resulting actions are jointly consistent: the red agent waits while the blue agent moves left.
Figure 3: POGEMA benchmark results for four DMM variants (DMM-0.8M, DMM-3M, DMM-MICPO-0.8M, DMM-MICPO-3M) and five learnable baselines (MAPF-GPT-85M, MAPF-GPT-DDG-2M, MAGAT+, HMAGAT, LC-MAPF-3M), across four POGEMA domains: Random, Mazes, Warehouse, and Cities-Tiles. Top: success rate versus number of agents; each point is the mean over n=128 task instances per agent count, with shaded bands showing 95% Wilson score CIs. Bottom: SoC ratio relative to the centralized LaCAM* solution; each box pools solved instances across all evaluated agent counts for a given map.
Figure 4: Results on 1,600 MovingAI tasks from 32 maps, each instantiated using all available start–goal pairs in its scenario file (i.e., the maximum available agent count). Annotations above the panels report the number of solved tasks (out of 1,600) and virtual-best SoC wins. The virtual best is the minimum SoC obtained by any of the six displayed methods on each task; ties count as wins for every tied method. (a) SoC relative to the virtual best on tasks solved by each method. Annotations show mean values, and the nested bands show the q75 , q90 , and q95 quantiles. (b) Reported solver runtime on a logarithmic scale; dots and crosses denote all solved and unsolved tasks. Search-based and hybrid methods receive 600 seconds per task, while HMAGAT and DMM receive 5,000 environment steps. HMAGAT and DMM use CS–PIBT and RSE.
Episode length ↓
Method
Agent count
Agent density (%)
Final on goal (%) ↑
Avg.
Min.
Max.
Avg. step time (ms)
PIBT time (ms/step)
Decision time ( μ s/agent/step)
Peak GPU memory
Total time (min)
DMM-MICPO-0.8M
1048576
27.86
100.00
20867
16345
29508
763.1±
195.0
249.22±
62.86
0.745±
0.189
49.07 GiB
256.9
GPU-PIBT
89.15
32768
32768
32768
228.9±
6.7
186.26±
6.50
0.234±
0.006
34.01 GiB
134.3
DMM-MICPO-0.8M
524288
13.93
100.00
8389
7600
8989
528.6±
40.0
22.02±
4.98
1.035±
0.077
28.77 GiB
75.7
GPU-PIBT
95.46
32768
32768
32768
32.7±
1.2
10.56±
0.73
0.077±
0.002
17.84 GiB
21.9
DMM-MICPO-0.8M
262144
6.97
100.00
5185
4961
5461
488.9±
11.6
2.73±
0.66
1.902±
0.046
18.63 GiB
43.1
Table 1: Results on matched 2304×2304 POGEMA mazes using four H100 GPUs. Each row aggregates four matched scenarios, one per maze layout. Final on goal is the final on-goal percentage; episodes stop when all agents are on goal or at 32768 steps. Avg. episode length is the mean across the four scenarios, while Min. and Max. are the minimum and maximum episode lengths across them. Decision time is 106T/(NL) for total wall time T (seconds, including prefill and overhead), N agents and L steps, counting all agents including skipped policy computations. Density is agents per free cell. Total time reports the same T in minutes. Step, PIBT and decision times are mean ± SD across the four scenarios; all other values are means.
Figure 5: Congestion and computation during a successful 1,048,576 -agent DMM-MICPO-0.8M rollout. (a–e) Five consecutive windows of approximately 52 minutes of measured step time. Purple shows mean agent presence per traversable cell in each 64×64 region, including agents on goal; rose contours mark the top 5% of regions by CS–PIBT action changes within each window. Central congestion clears as agents reach their goals. (f) Per-step policy inference, shielding with action broadcast, and observation construction times: the maximum across four GPUs for each stage, smoothed over 32 steps. Faster steps let later windows cover more steps. The broken axis marks the one-time 121-second cost-to-go prefill; the legend gives episode totals by stage. All agents reach their goals at step 16,345.
Valid
Invalid
Method
WL (%)
RW (%)
WW (%)
RL (%)
DMM ( β=0.8 )
51.4 ± 9.0
43.4 ± 9.4
2.2 ± 0.5
3.0 ± 1.0
DMM ( β=0 )
24.5 ± 0.4
25.6 ± 0.5
23.3 ± 0.2
26.6 ± 0.2
LC-MAPF
25.7 ± 0.1
24.2 ± 0.2
22.7 ± 0.4
27.4 ± 0.2
MAGAT+
24.6 ± 0.3
24.9 ± 0.4
23.5 ± 0.4
26.9 ± 0.2
HMAGAT
25.6 ± 1.4
24.7 ± 2.0
22.5 ± 2.2
27.1 ± 1.4
Table 2: Sample frequency over the four joint actions at the shared ambiguous corridor state, as percentages (1,000 samples per seed, 5 training seeds; mean ± 95% Student- t confidence interval across seeds). For DMM, β denotes the shared teacher-forcing floor, β0=βr . Joint actions are abbreviated as WL = (wait, left), RW = (right, wait), WW = (wait, wait), and RL = (right, left).
Figure 6: DMM architecture variants. (a) DMM-3M retains the Transformer encoder–decoder backbone of LC-MAPF. The tokenized observation is compressed into 32 latent tokens, which are combined with the current neighbor messages and processed by the decoder at every refinement round. (b) DMM-0.8M uses a structured observation encoder that separately processes the spatial field and local agent records. The resulting observation tokens are mixed once per environment step, and their cross-attention key/value projections are reused across refinement rounds; only the current messages and query state change between rounds. Both architectures implement the same DMM intent-refinement process.
Parameter
DMM-3M
DMM-0.8M
Imitation pretraining
Effective batch size
512
800
Training iterations
1,000,000
1,000,000
Maximum learning rate
6×10−4
6×10−4
Minimum learning rate
6×10−5
6×10−5
Warm-up iterations
2,000
2,000
Table 3: Model and training hyperparameters for DMM variants.
Figure 7: Effect of inference-time refinement depth at the largest evaluated team size in each POGEMA domain. DMM-3M and DMM-MICPO-3M are both trained with Ktrain=4 refinement rounds; at evaluation, the same fixed checkpoints are executed with Ktest∈{1,2,3,4,8,12} without retraining. Rows report success rate, makespan, and agent-agent collisions, respectively. Shaded regions show 95% confidence intervals across n=128 validation instances per domain, with the same instances used across refinement depths and policies. Wilson score intervals are used for success rate, while makespan and collision counts use normal intervals of the form xˉ±1.96s/n . The vertical dashed line marks the training depth Ktrain=4 .
Figure 8: Success rate on Mazes under inference-time perturbations of the communicated state. Both DMM-3M and DMM-MICPO-3M are evaluated with fixed weights at K=4 . Full communicates both h and the evolving intent z ; no- h removes h from the broadcast, no- z removes z , and z0 -only replaces the evolving communicated intent with its initial value while leaving the agent’s own intent dynamics unchanged. Shuffled permutes the assembled messages across agents before decoding. Shaded regions show 95% Wilson score confidence intervals across n=128 validation instances, with the same instances used for all compared communication variants.
Figure 9: Corridor ablations of refinement depth and teacher forcing. All panels report the valid joint-action frequency pvalid=p(WL)+p(RW) . (a) Checkpoints trained with Ktrain=4 , evaluated at different test-time refinement depths without retraining; the vertical dashed line marks the training depth. (b) Contribution of initial-intent teacher forcing β0 and round-level teacher forcing βr : for the blue series, excluded mechanisms are annealed to a zero floor; for the red series, they are disabled from the start of training. (c) Effect of the shared teacher-forcing floor β0=βr=β ; the vertical dashed line marks the retained floor used in the main DMM training, β=0.8 . (d) Corridor annealed schedule versus a constant teacher-forcing probability at matched floors. The horizontal dotted line marks the 0.5 valid-action frequency from independent recombination of the expert marginals.
Joint-action frequency (%)
Ktest
pvalid (%)
WL
RW
Invalid
2
83.7 ± 2.7
41.7
42.1
16.3 ± 2.7
4 (train)
94.8 ± 1.1
51.4
43.4
5.2 ± 1.1
8
99.6 ± 0.4
52.7
46.9
0.4 ± 0.4
12
99.9 ± 0.1
52.9
47.0
0.1 ± 0.1
Table 4: Effect of test-time refinement depth in the corridor, as percentages. All checkpoints are trained with Ktrain=4 . Entries are mean frequencies across five independently trained checkpoints (one per training seed), with 1,000 joint-action samples per checkpoint. The valid joint-action frequency is pvalid=p(WL)+p(RW) ; uncertainty denotes the 95% Student- t confidence interval across checkpoints. WL and RW are the two valid joint actions, while Invalid combines the stall (WW) and collision (RL) outcomes.
Method
Decoding / RSE
Solved ↑
SoC ↓
MS ↓
HMAGAT
Sampling
1,556
362,741
506.3
Sampling + RSE
1,576
361,858
481.6
Argmax + RSE
1,543
334,302
534.3
DMM-MICPO- 0.8M
Sampling
1,593
369,955
492.6
Sampling + RSE
1,592
369,956
494.4
Argmax + RSE
1,593
321,085
460.0
Table 5: MovingAI decoding and RSE configurations. Solved is out of 1,600 tasks. MS: makespan.
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) 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
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.
Zhanjiang Yang, Yueming Li, Yang Shen +2
Shenzhen Technology University, China. · University of Technology Sydney, Australia.