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.AI, cs.MA
2026-09-26
DMM replaces one-shot action sampling with iterative intent denoising over communication rounds, solving 1,598 of 1,600 MovingAI MAPF tasks and scaling to 1M agents.
Learnable decentralized MAPF policies all end the same way: each agent outputs its own action distribution and samples from it independently. Put two agents in a corridor where they must swap positions, and only two of the four joint outcomes are coordinated; simultaneous moves collide, mutual waits deadlock. LC-MAPF, MAGAT+, and HMAGAT, trained solely on this corridor, still put roughly 25% on each outcome, so half their samples are invalid.
The paper shows this is not a learning deficiency. It proves a decentralized factorization gap: whenever expert joint actions remain dependent given the full context, any product of per-agent distributions stays a positive KL distance from the expert joint distribution, with conditional total correlation as the bound plus a penalty for context each agent never sees. The argument transfers the multimodality analysis from non-autoregressive sequence models to agents: every per-position marginal can be correct while the product still assembles illegal sequences.
DMM swaps sampling for denoising, effectively a discrete diffusion loop:
The load-bearing choice is that the refined quantity is itself what gets communicated. Existing learned-communication methods exchange context and still sample independently once communication ends; DMM lets agents observe each other's stochastic choices while those choices are still forming, while per-agent compute stays independent of team size. DiffLNS, the closest diffusion-style relative, refines a centralized full-horizon plan; DMM refines per timestep, decentrally.
Training runs in two stages. Imitation on expert solutions supervises the vote at every round, with teacher forcing that injects expert actions into the initial intent and votes at a probability annealed from 1.0 down to a retained floor of 0.8. MICPO then fine-tunes without a critic: rollouts are grouped so members share the same sampled initial intents, advantages come from within-group comparison of a team return built from off-goal duration and blocked actions, importance ratios are clipped per agent and per refinement round, and a KL term anchors the policy to the frozen imitation checkpoint.
The corridor isolates the mechanism: DMM concentrates 94.8% of samples on the two valid resolutions versus about 50% for the baselines, and raising test-time refinement depth from 4 to 8 and 12 rounds lifts that to 99.6% and 99.9% with no retraining. Annealing the teacher-forcing floor to zero collapses DMM back to near-uniform.
POGEMA, standalone policies with no collision repair (the last two map types are out of distribution), at maximum team size:
| Method | Setting | Success rate |
| DMM-MICPO-3M | Warehouse, 192 agents | 1.000 |
| LC-MAPF-3M (strongest baseline) | Warehouse, 192 agents | 0.938 |
| DMM-MICPO-3M | Cities-Tiles, 256 agents | 0.922 |
| LC-MAPF-3M | Cities-Tiles, 256 agents | 0.805 |
Across solved instances, DMM-MICPO-3M posts the lowest median SoC ratio (sum of costs relative to LaCAM) on all four map types, 1.006–1.102, against 1.063–1.892 for MAGAT+ and HMAGAT.
MovingAI, 1,600 tasks, learned policies wrapped with CS-PIBT shielding:
| Method | Solved | Median SoC | Median runtime |
| DMM-MICPO-3M | 1,598 | 100.1% | 8.27 s |
| DMM-MICPO-0.8M | 1,593 | n/a | 2.33 s |
| HMAGAT | 1,576 | n/a | 48.10 s |
| LG-LaCAM | 1,569 | 100.3% (q95 164.0%) | 5.61 s |
| MAPF-LNS2 | 1,411 | n/a | 8.43 s |
DMM-MICPO-3M also matches the per-task virtual-best SoC on 736 tasks, more than any other method. At scale, DMM-0.8M solves all 16 instances on 2304×2304 mazes (about 29.1% obstacles) with 131,072 to 1,048,576 agents; every million-agent scenario ends with all agents on goal, in 16,345–29,508 steps and about 4.4 hours on four H100s, and an 8× increase in agents raises mean step time only 1.73×. GPU-PIBT hits the step horizon in every run, leaving only 89.15% on goal at the highest density. The paper claims this is the first learning-based MAPF policy to fully solve million-agent instances in obstacle-rich environments.
The diagnosis travels well beyond pathfinding. Any decentralized multi-agent policy that commits by independent sampling, whether robot fleets, game AI, or multi-agent LLM systems, fails the same way on multimodal joint decisions. The fix is cheap: keep the architecture and put the intermediate sample into the message content. Extra refinement rounds at test time buy coordination the same way extra diffusion sampler steps buy sample quality. The 0.8M variant has 763k parameters, roughly 114 GPU-hours of total training, and a 2.33 s median runtime that leaves over 99% of a planning budget for downstream LNS refinement. Code is public.
The authors' heaviest caveat is their own: DMM does not enforce joint-action feasibility, so the MovingAI and million-agent runs lean on CS-PIBT collision shielding, which uses global state and is therefore centralized; the purely decentralized evidence is confined to the POGEMA comparison. The corridor ablation shows the coordinated behavior partly rides on the retained teacher-forcing floor, and how far the mechanism generalizes without that crutch is untested. MovingAI runtimes are not budget-matched (600 s wall clock for search methods, 5,000 environment steps for learned ones), so the speed advantage deserves a discount. In the 4.4-hour million-agent rollout, shielding itself is a major runtime cost.