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

arXiv: https://arxiv.org/abs/2605.13296 · HTML: https://mlsanity.com/paper/2605.13296/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion and flow policies for robotics, one of 14 directions in Diffusion models.
- Builds on 23 of its 32 references that are in the map.
- First posted on arXiv 13 May 2026.

## Placed in

- Diffusion models / [Diffusion and flow policies for robotics](https://mlsanity.com/diffusion/diffusion-and-flow-policies-for-robotics/)

## Builds on (most cited first, 23 of 23)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Scalable Diffusion Models with Transformers](https://mlsanity.com/paper/2212.09748/) (2022)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Motion Planning Diffusion: Learning and Planning of Robot Motions with Diffusion Models](https://mlsanity.com/paper/2308.01557/) (2023)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning](https://mlsanity.com/paper/2011.13219/) (2020)
- [Multi-Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2410.03072/) (2024)
- [Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models](https://mlsanity.com/paper/2502.03607/) (2025)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.14931/) (2024)
- [MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale](https://mlsanity.com/paper/2409.00134/) (2024)
- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search](https://mlsanity.com/paper/2312.16767/) (2023)
- [LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Finding](https://mlsanity.com/paper/2405.17794/) (2024)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding](https://mlsanity.com/paper/2602.06733/) (2026)

## Built on by (most cited first, 1 of 1)

- [Decentralized Master-Mind: Joint Action Refinement through Iterative Intent Denoising in Multi-Agent Pathfinding](https://mlsanity.com/paper/2609.32019/) (2026)

## Abstract (arXiv)

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.