Decentralized Master-Mind: Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding

Valeriy Vyaltsev; Anton Andreychuk; Taisia Zlotnikova; Konstantin Yakovlev; Aleksandr Panov; Alexey Skrynnik

cs.AISep 25, 2026

Decentralized Master-Mind: Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding

Authors: Valeriy Vyaltsev, Anton Andreychuk, Taisia Zlotnikova, Konstantin Yakovlev, Aleksandr Panov, Alexey Skrynnik

Organizations: CogAI Lab, Moscow, Russia

Abstract

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

K_{\mathrm{train}}=4

, increasing the test-time refinement depth from

K_{\mathrm{test}}=4

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 $q_{75}$ , $q_{90}$ , and $q_{95}$ 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.

Method	Agent count	Agent density (%)	Final on goal (%) $\uparrow$	Avg.	Min.	Max.	Avg. step time (ms)		PIBT time (ms/step)		Decision time ( $\mu$ s/agent/step)		Peak GPU memory	Total time (min)
				Episode length $\downarrow$
DMM-MICPO-0.8M	$1\,048\,576$	$27.86$	$100.00$	$20\,867$	$16\,345$	$29\,508$	$763.1$ $\pm$	$195.0$	$249.22$ $\pm$	$62.86$	$0.745$ $\pm$	$0.189$	$49.07$ GiB	$256.9$
GPU-PIBT	$1\,048\,576$	$27.86$	$89.15$	$32\,768$	$32\,768$	$32\,768$	$228.9$ $\pm$	$6.7$	$186.26$ $\pm$	$6.50$	$0.234$ $\pm$	$0.006$	$34.01$ GiB	$134.3$
DMM-MICPO-0.8M	$524\,288$	$13.93$	$100.00$	$8\,389$	$7\,600$	$8\,989$	$528.6$ $\pm$	$40.0$	$22.02$ $\pm$	$4.98$	$1.035$ $\pm$	$0.077$	$28.77$ GiB	$75.7$
GPU-PIBT	$524\,288$	$13.93$	$95.46$	$32\,768$	$32\,768$	$32\,768$	$32.7$ $\pm$	$1.2$	$10.56$ $\pm$	$0.73$	$0.077$ $\pm$	$0.002$	$17.84$ GiB	$21.9$
DMM-MICPO-0.8M	$262\,144$	$6.97$	$100.00$	$5\,185$	$4\,961$	$5\,461$	$488.9$ $\pm$	$11.6$	$2.73$ $\pm$	$0.66$	$1.902$ $\pm$	$0.046$	$18.63$ GiB	$43.1$

Table 1: Results on matched

2304\times 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

32\,768

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

10^{6}T/(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

\pm

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\times 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 ( $\beta=0.8$ )	51.4 $\pm$ 9.0	43.4 $\pm$ 9.4	2.2 $\pm$ 0.5	3.0 $\pm$ 1.0
DMM ( $\beta=0$ )	24.5 $\pm$ 0.4	25.6 $\pm$ 0.5	23.3 $\pm$ 0.2	26.6 $\pm$ 0.2
LC-MAPF	25.7 $\pm$ 0.1	24.2 $\pm$ 0.2	22.7 $\pm$ 0.4	27.4 $\pm$ 0.2
MAGAT+	24.6 $\pm$ 0.3	24.9 $\pm$ 0.4	23.5 $\pm$ 0.4	26.9 $\pm$ 0.2
HMAGAT	25.6 $\pm$ 1.4	24.7 $\pm$ 2.0	22.5 $\pm$ 2.2	27.1 $\pm$ 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

\pm

95% Student-

t

confidence interval across seeds). For DMM,

\beta

denotes the shared teacher-forcing floor,

\beta_{0}=\beta_{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\times 10^{-4}$	$6\times 10^{-4}$
Minimum learning rate	$6\times 10^{-5}$	$6\times 10^{-5}$
Warm-up iterations	$2{,}000$	$2{,}000$

Table 3: Model and training hyperparameters for DMM variants.

Panel of Figure 7 — 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 $K_{\mathrm{train}}=4$ refinement rounds; at evaluation, the same fixed checkpoints are executed with $K_{\mathrm{test}}\in\{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 $\bar{x}\pm 1.96\,s/\sqrt{n}$ . The vertical dashed line marks the training depth $K_{\mathrm{train}}=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

z^{0}

-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

p_{\mathrm{valid}}=p(\mathrm{WL})+p(\mathrm{RW})

. (a) Checkpoints trained with

K_{\mathrm{train}}=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

\beta_{0}

and round-level teacher forcing

\beta_{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

\beta_{0}=\beta_{r}=\beta

; the vertical dashed line marks the retained floor used in the main DMM training,

\beta=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.

$K_{\mathrm{test}}$	$p_{\mathrm{valid}}$ (%)	WL	RW	Invalid
		Joint-action frequency (%)
2	83.7 $\pm$ 2.7	41.7	42.1	16.3 $\pm$ 2.7
4 (train)	94.8 $\pm$ 1.1	51.4	43.4	5.2 $\pm$ 1.1
8	99.6 $\pm$ 0.4	52.7	46.9	0.4 $\pm$ 0.4
12	99.9 $\pm$ 0.1	52.9	47.0	0.1 $\pm$ 0.1

Table 4: Effect of test-time refinement depth in the corridor, as percentages. All checkpoints are trained with

K_{\mathrm{train}}=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

p_{\mathrm{valid}}=p(\mathrm{WL})+p(\mathrm{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 $\uparrow$	SoC $\downarrow$	MS $\downarrow$
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 Path Finding

Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.

See all 92 papers

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding
May 8, 2026Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk +5Multi-Agent Coordination Robust MAPF
CogAI Lab, Moscow, Russia
Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
May 13, 2026Yuanzhe Wang, Tian Zhi, Zihang Wei +8Multi-Agent System Optimization Diffusion-Based Planning
State Key Lab of Processors, Institute of Computing Technology, CAS · School of Advanced Interdisciplinary Sciences, CAS · University of Chinese Academy of Sciences +1
MAPF-World: Action World Model for Multi-Agent Path Finding
Aug 16, 2025Zhanjiang Yang, Yueming Li, Yang Shen +2Multi-Agent Path Finding Multi-Agent Planning
Shenzhen Technology University, China. · University of Technology Sydney, Australia.

May 8, 2026J/K move · Enter open · S save

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Valeriy Vyaltsev, Alsu Sagirova, Anton Andreychuk, Oleg Bulichev+4

CogAI Lab, Moscow, Russia

Multi-Agent Coordination Robust MAPF Multi-Agent Communication Multi-Agent Path Finding

Open paper AskPDF arXiv

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.

Abstract

Multi-Agent Path Finding

Explore similar work

Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding

Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention

MAPF-World: Action World Model for Multi-Agent Path Finding