Skip to main content

# Multi-Agent Pathfinding

2 related articles

Subscribe to updates

arXiv Oct 2, 2026
DMM has agents agree before they act: 1,598 of 1,600 MovingAI tasks solved, scaling past a million agents
The work identifies that in decentralized multi-agent path finding, even correctly learned per-agent action distributions can be recombined by independent sampling into incompatible joint actions, and proposes DMM, which replaces one-shot sampling with discrete iterative refinement of action intents across communication rounds before commitment, fine-tuned by MICPO, a critic-free multi-agent reinforcement-learning method; DMM generally achieves higher success rates and lower solution costs on POGEMA, solves 1,598 of 1,600 MovingAI tasks (the highest coverage among the evaluated methods), and scales to over one million simultaneously acting agents.
The work identifies that in decentralized multi-agent path finding, even correctly learned per-agent action distributions can be recombined by independent sampling into incompatible joint actions, and proposes DMM, which replaces one-shot sampling with discrete iterative refinement of action intents across communication rounds before commitment, fine-tuned by MICPO, a critic-free multi-agent reinforcement-learning method; DMM generally achieves higher success rates and lower solution costs on POGEMA, solves 1,598 of 1,600 MovingAI tasks (the highest coverage among the evaluated methods), and scales to over one million simultaneously acting agents.
Valeriy Vyaltsev（First author）
DMM (Decentralized Master-Mind)MICPO Multi-Agent Pathfinding Imitation Learning
arXiv Sep 16, 2026
Routing Multiple Agents Below the Sum of Distances: A Parameterized Complexity Characterization of Transient Multiagent Pathfinding
This work studies Transient Multiagent Pathfinding, in which agents must be routed without collisions and disappear upon reaching their destinations, and shows that the problem is fixed-parameter tractable in the combined parameter k+ζ, where k is the number of agents and ζ=L−λ is the gap between the sequential-routing upper bound L=1+Σdist(si,ti) and the target makespan λ, running in 2^O(k²ζ)·n^O(1) time, complemented by matching lower bounds (W[1]-hardness for k alone, W[1]-hardness for ζ alone when terminals need not be distinct, and no polynomial kernel for k+ζ) and by fixed-parameter tractability in ζ alone when all terminals are pairwise distinct, running in 2^O(ζ³)·n^O(1) time.
This work studies Transient Multiagent Pathfinding, in which agents must be routed without collisions and disappear upon reaching their destinations, and shows that the problem is fixed-parameter tractable in the combined parameter k+ζ, where k is the number of agents and ζ=L−λ is the gap between the sequential-routing upper bound L=1+Σdist(si,ti) and the target makespan λ, running in 2^O(k²ζ)·n^O(1) time, complemented by matching lower bounds (W[1]-hardness for k alone, W[1]-hardness for ζ alone when terminals need not be distinct, and no polynomial kernel for k+ζ) and by fixed-parameter tractability in ζ alone when all terminals are pairwise distinct, running in 2^O(ζ³)·n^O(1) time.
Technische Universität Berlin University of Bergen
Matthias Bentert（First author）
Multi-Agent Pathfinding Parameterized Complexity Color Coding

You’re all caught up