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

Decentralized Master-Mind. Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding. By Valeriy Vyaltsev and five others, from CogAI Lab. Published on the twenty-fifth of September. Its code repository is worked out: about one hundred and fifty source files, with a readme and a licence.

In decentralized multi-agent path finding with communication, every agent has to reach its own goal without colliding with the others, and each sees only part of the world. Learnable policies trained on expert data are an effective way to attack this. But there is a failure hiding in how those policies act. Often several coordinated joint actions are valid in the same situation. If each agent samples independently from its own action distribution, locally valid choices can recombine into a joint action that does not work. Picture two agents who could each yield or each go first: one picks yielding, the other picks going first from a different valid plan, and the combination collides. The authors stress that this can happen even when every per-agent distribution has been learned correctly. The fault is in the final sampling step, not in what was learned.

DMM, short for Decentralized Master-Mind, replaces that one-shot sampling. In its place is discrete, iterative refinement of action intents spread across communication rounds, inspired by denoising in diffusion models. Agents start from random action intents and refine them through local communication, so their choices become coupled before anyone commits to a move.

Training has two layers. DMM is first pretrained with imitation learning on expert MAPF solutions. It is then further optimized with MICPO, a critic-free, group-relative reinforcement-learning method designed specifically for this setting: many agents, refining their actions over many rounds.

Against the learnable baselines it was evaluated with, DMM generally reaches higher success rates and lower solution costs. The headline test is a set of one thousand six hundred MovingAI tasks. DMM fine-tuned with MICPO solves one thousand five hundred and ninety-eight of them, the highest coverage among the evaluated methods, with solution costs close to those of the strongest baselines. It also scales to over one million agents acting simultaneously in environments dense with obstacles.

That last number matters for the claim about decentralization. Coordination here is bought through rounds of local talk, not through a central planner, and the scale result shows that the approach does not give up decentralized execution to get it.

A useful way to hold this paper is as a relocation of the problem. The policies were not the weak link; the moment of sampling was. Letting agents refine their intents together across communication rounds, in the spirit of denoising, is offered as a way to fix coordination at exactly that point, while each agent still acts on its own.