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

# Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
Source: [https://arxiv.org/html/2605.13296](https://arxiv.org/html/2605.13296)
Yuanzhe Wang1,2,3Tian Zhi1Zihang Wei1,3Hongguang Wang1,3Jiaming Guo1 Yang Zhao4Zisheng Liu1,3Shiyu Quan1,2,3Xing Hu1Zidong Du1Yunji Chen1,3 1State Key Lab of Processors, Institute of Computing Technology, CAS 2School of Advanced Interdisciplinary Sciences, CAS 3University of Chinese Academy of Sciences 4Institute of Microelectronics, CAS

###### Abstract

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

## 1Introduction

Multi\-Agent Path Finding \(MAPF\) aims to compute collision\-free trajectories that guide multiple agents from their start locations to individual goals in a shared environment\. As a fundamental multi\-agent coordination problem, MAPF is computationally challenging and underpins a broad spectrum of real\-world applications, including warehouse automation, autonomous vehicle coordination, unmanned aircraft systems, fleet management, and multi\-robot systems\(Stern et al\.,[2019](https://arxiv.org/html/2605.13296#bib.bib27)\)\. Consequently, scalable suboptimal planning has remained a sustained research focus\.

Among existing approaches, repair\-based methods such as Large Neighborhood Search 2 \(LNS2\) have demonstrated strong empirical performance in practical settings\. These methods start from an initial set of paths and iteratively repair selected agent subsets until conflicts are resolved\(Li et al\.,[2021a](https://arxiv.org/html/2605.13296#bib.bib9),[2022](https://arxiv.org/html/2605.13296#bib.bib11)\)\. Recent work on LNS\-based MAPF has made significant progress in the repair stage, including adaptive neighborhood selection, destroy strategies, and enhanced replanning\(Huang et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib6);Phan et al\.,[2024](https://arxiv.org/html/2605.13296#bib.bib22);Yan and Wu,[2024](https://arxiv.org/html/2605.13296#bib.bib32);Wang et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib31)\)\. However, the initialization stage remains comparatively underexplored, with limited work on selecting promising initial solutions\(Huber et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib7)\)\. This gap is consequential because the initial plan can substantially affect the success rate and convergence speed of LNS\-based repair\(Huber et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib7);Li et al\.,[2021a](https://arxiv.org/html/2605.13296#bib.bib9)\)\. In dense and congested environments, low\-quality initial plans often contain severe conflicts, deadlocks, or globally inconsistent motion patterns\. As a result, the back\-end planner may spend a substantial computational budget correcting poor structures rather than refining an already promising solution\.

A useful initializer for LNS\-based MAPF should provide globally coherent joint plans that capture meaningful spatiotemporal coordination among agents, motivating a structured generative prior over coordinated trajectories\. Discrete diffusion is well suited to this formulation because it can capture complex trajectory distributions through iterative denoising, operate directly in the categorical action space, and sample diverse candidate drafts for subsequent repair\(Carvalho et al\.,[2023](https://arxiv.org/html/2605.13296#bib.bib3);Shaoul et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib24);Liang et al\.,[2025a](https://arxiv.org/html/2605.13296#bib.bib13)\)\. However, directly applying diffusion to MAPF remains challenging: the model must generate centralized joint plans for many agents, maintain temporal consistency toward individual goals, and efficiently model conflict\-relevant agent–agent interactions during denoising\.

To overcome the limitations of suboptimal initialization in repair\-based MAPF solvers and address the challenges of applying diffusion to complex and congested MAPF environments, we introduce*DiffLNS*, a hybrid framework that combines a discrete denoising diffusion probabilistic model \(D3PM\)\(Austin et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib2)\)with LNS2\. The D3PM initializer learns a spatiotemporal prior over coordinated multi\-agent action trajectories from expert demonstrations\. It employs a diffusion\-aware sparse social attention mechanism that dynamically constructs local neighborhoods from the current denoising state, thereby focusing computation on agents that are more likely to interact or conflict\. During inference, DiffLNS samples multiple drafts for the same instance, repairs them independently with LNS2, and selects the best feasible solution\. This design allows D3PM to serve not only as a learned initializer but also as a source of diverse repair seeds, making DiffLNS scalable to larger agent teams and naturally parallelizable across independently generated candidates\.

We summarize our main contributions and findings below:

- •A hybrid framework for initialization\-aware MAPF\.We propose DiffLNS, which integrates a discrete diffusion\-based generator with LNS2 repair, shifting the focus from repair\-only improvement to initialization quality\. To the best of our knowledge, this is the first work that leverages discrete diffusion to warm\-start an LNS\-based MAPF solver\.
- •Diffusion\-aware sparse social attention\.We introduce a dynamic, step\-dependent sparse attention mechanism that constructs local neighborhoods from the current noisy trajectory estimate\. This design reduces unnecessary interaction modeling while focusing on conflict\-relevant agent pairs, improving both efficiency and plan repairability\.
- •Strong empirical generalization and performance\.Despite being trained with at most 96 agents, DiffLNS scales to teams of up to 312 agents\. Across 20 complex and congested settings, it achieves a 95\.8% average success rate and improves over LNS2\+RL, the strongest tested baseline by average success rate, by 9\.6 percentage points\.

## 2Preliminaries

### 2\.1Multi\-Agent Path Finding

Multi\-Agent Path Finding \(MAPF\) is commonly defined as the problem of finding collision\-free paths for multiple agents from individual start locations to individual goals in a shared graph or grid environment\(Stern et al\.,[2019](https://arxiv.org/html/2605.13296#bib.bib27)\)\. LetG∈\{0,1\}H×WG\\in\\\{0,1\\\}^\{H\\times W\}denote the map, whereGh,w=0G\_\{h,w\}=0indicates a traversable cell andGh,w=1G\_\{h,w\}=1indicates an obstacle\. A set ofNNagents is specified by start locations\{si\}i=1N\\\{s\_\{i\}\\\}\_\{i=1\}^\{N\}and goal locations\{gi\}i=1N\\\{g\_\{i\}\\\}\_\{i=1\}^\{N\}\. The planning horizon is denoted byTT, andτ∈\{0,1,…,T\}\\tau\\in\\\{0,1,\\dots,T\\\}indexes discrete timesteps\. At each timestepτ\\tau, each agentiiexecutes an action

aiτ∈𝒜,𝒜=\{stay,up,down,left,right\}\.a\_\{i\}^\{\\tau\}\\in\\mathcal\{A\},\\qquad\\mathcal\{A\}=\\\{\\texttt\{stay\},\\texttt\{up\},\\texttt\{down\},\\texttt\{left\},\\texttt\{right\}\\\}\.A valid solution must avoid vertex conflicts, where different agents occupy the same cell at the same timestep, and edge conflicts, where two agents swap positions between consecutive timesteps\. Solution quality is measured by sum of costs \(SOC\), defined as the sum of the individual path costs over all agents\.

### 2\.2Discrete Denoising Diffusion Probabilistic Model

A discrete denoising diffusion probabilistic model defines a forward Markov chain that gradually corrupts a clean discrete variable𝐱0\\mathbf\{x\}\_\{0\}overKKsteps\(Hoogeboom et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib5);Austin et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib2)\)\. For a one\-hot row vector𝐱k∈\{0,1\}C\\mathbf\{x\}\_\{k\}\\in\\\{0,1\\\}^\{C\}, the one\-step transition is parameterized by𝐐k∈ℝC×C\\mathbf\{Q\}\_\{k\}\\in\\mathbb\{R\}^\{C\\times C\}:

q​\(𝐱k∣𝐱k−1\)=Cat​\(𝐱k;𝐩=𝐱k−1​𝐐k\)\.q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{k\-1\}\)=\\mathrm\{Cat\}\\\!\\left\(\\mathbf\{x\}\_\{k\};\\,\\mathbf\{p\}=\\mathbf\{x\}\_\{k\-1\}\\mathbf\{Q\}\_\{k\}\\right\)\.\(1\)For structured discrete data, this transition is applied independently to each discrete element\.

D3PM commonly adopts an𝐱0\\mathbf\{x\}\_\{0\}\-parameterization, in which the model predicts the clean state𝐱0\\mathbf\{x\}\_\{0\}from𝐱k\\mathbf\{x\}\_\{k\}throughp~θ​\(𝐱0∣𝐱k\)\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\}\)\(Hoogeboom et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib5);Austin et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib2)\)\. The reverse transition is then constructed as

pθ​\(𝐱k−1∣𝐱k\)∝∑𝐱~0q​\(𝐱k−1,𝐱k∣𝐱~0\)​p~θ​\(𝐱~0∣𝐱k\)\.p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\}\)\\propto\\sum\_\{\\tilde\{\\mathbf\{x\}\}\_\{0\}\}q\(\\mathbf\{x\}\_\{k\-1\},\\mathbf\{x\}\_\{k\}\\mid\\tilde\{\\mathbf\{x\}\}\_\{0\}\)\\,\\tilde\{p\}\_\{\\theta\}\(\\tilde\{\\mathbf\{x\}\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\}\)\.\(2\)The standard training objective combines the variational bound with an auxiliary clean\-state prediction term\(Austin et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib2)\):

ℒλ=ℒvb\+λ​𝔼q​\(𝐱0\)​𝔼q​\(𝐱k∣𝐱0\)​\[−log⁡p~θ​\(𝐱0∣𝐱k\)\]\.\\mathcal\{L\}\_\{\\lambda\}=\\mathcal\{L\}\_\{\\mathrm\{vb\}\}\+\\lambda\\,\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{0\}\)\}\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\left\[\-\\log\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\}\)\\right\]\.\(3\)The full variational decomposition used in our implementation is provided in Appendix[D\.3](https://arxiv.org/html/2605.13296#A4.SS3)\. At inference time, sampling starts from𝐱K∼p​\(𝐱K\)\\mathbf\{x\}\_\{K\}\\sim p\(\\mathbf\{x\}\_\{K\}\)and iteratively applies the learned reverse transitions fork=K,…,1k=K,\\dots,1\.

### 2\.3Large Neighborhood Search for MAPF

MAPF\-LNS2\(Li et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib11)\)is an unbounded\-suboptimal MAPF algorithm based on large neighborhood search\. It first constructs an initial plan using prioritized planning \(PP\)\(Erdmann and Lozano\-Perez,[1986](https://arxiv.org/html/2605.13296#bib.bib4)\)with SIPPS as the low\-level solver; the resulting plan may contain collisions\. LNS2 then repeatedly selects a subset of agents for replanning while keeping the remaining paths fixed, and accepts an update if the number of colliding pairs does not increase\. The same PP\+SIPPS procedure is used for neighborhood replanning, where SIPPS computes single\-agent paths under dynamic obstacles and soft collision constraints\(Li et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib11)\)\. Because each iteration repairs only a local subset of agents, the difficulty of repair depends strongly on the conflict structure of the initial plan: localized and mild conflicts are easier to resolve than heavily entangled collisions\. This property makes initialization quality a key factor in the effectiveness of LNS2\.

## 3Methodology

DiffLNS formulates MAPF initialization as structured generative warm\-starting rather than direct feasibility solving\. The denoising model learns a spatiotemporal prior over coordinated joint action sequences and generates spatiotemporally structured drafts, while LNS2 enforces hard MAPF constraints by repairing residual conflicts and incomplete paths\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x1.png)Figure 1:Overview of the DiffLNS hybrid framework\. The lower panel shows the denoising network architecture used in the D3PM initializer, detailed in Section[3\.2](https://arxiv.org/html/2605.13296#S3.SS2.SSS0.Px1)\.### 3\.1Hybrid Framework Overview

#### Joint action formulation\.

An initial plan is represented as a joint discrete action tensor

𝐱0∈\{0,1\}N×T×C,\\mathbf\{x\}\_\{0\}\\in\\\{0,1\\\}^\{N\\times T\\times C\},\(4\)whereNNis the number of agents,TTis the planning horizon, andC=5C=5corresponds to the grid actions \{stay,up,down,left,right\}\. Each slice𝐱0,i,τ,:\\mathbf\{x\}\_\{0,i,\\tau,:\}denotes a one\-hot action token for agentiiat timestepτ\\tau\. This representation matches the categorical structure of grid\-based MAPF and enables D3PM to operate directly in the discrete joint action space\.

#### Overall pipeline\.

Given a MAPF instance, the D3PM initializer samples a batch of joint action drafts conditioned on the instance\. Each draft is converted into a seed plan and repaired by LNS2\. If one or more repaired plans are feasible, DiffLNS returns the best one according to solution quality, e\.g\., sum of costs \(SOC\)\. Otherwise, the system samples and repairs additional batches until the evaluation budget is exhausted\. This design makes the framework complementary to repair\-side improvements in LNS\-based MAPF: rather than modifying the repair operator itself, DiffLNS improves the initial plans provided to it\. The DiffLNS hybrid framework is illustrated in Figure[1](https://arxiv.org/html/2605.13296#S3.F1)\.

### 3\.2Structured Initialization with Discrete Diffusion

#### Conditional denoising model\.

Training samples consist of MAPF conditions𝐜\\mathbf\{c\}and expert joint action tensors𝐱0\\mathbf\{x\}\_\{0\}defined in Eq\. \([4](https://arxiv.org/html/2605.13296#S3.E4)\)\. Given a noisy sample𝐱k∼q​\(𝐱k∣𝐱0\)\\mathbf\{x\}\_\{k\}\\sim q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{0\}\), we train a conditional clean\-state predictorp~θ​\(𝐱0∣𝐱k,𝐜\)\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)under the𝐱0\\mathbf\{x\}\_\{0\}\-parameterization introduced in Sec\.[2\.2](https://arxiv.org/html/2605.13296#S2.SS2)\. The denoising network embeds the noisy action distribution of each agent at each timestep and fuses it with start, goal, map, and diffusion\-step features\. The resulting conditioned action tokens are processed by structured spatiotemporal blocks that integrate temporal attention, sparse social attention, and environment sensing\. Temporal attention promotes motion consistency and goal progress through dense local\-window attention and sparse strided global connections along each agent trajectory; sparse social attention models local conflict interactions, and environment sensing provides obstacle awareness\. Details of dataset construction, preprocessing, and the full network architecture are provided in Appendix[D](https://arxiv.org/html/2605.13296#A4); the sparse social attention module is described below\.

#### Sparse social attention\.

A central bottleneck in centralized denoising lies in the social interaction module\. Dense all\-to\-all attention is not only computationally expensive but also poorly aligned with MAPF, because most conflict\-relevant interactions are local, whereas attending to all agents disperses attention across many irrelevant pairs\. We therefore replace dense social attention with a diffusion\-aware dynamic sparse variant\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x2.png)Figure 2:Diffusion\-aware sparse social attention\. At each denoising step, agents attend to dynamic local neighborhoods constructed from inferred\-trajectory proximity, thereby focusing computation on nearby agents that are most relevant to potential conflicts\.At diffusion stepkk, we construct the social neighborhood from the current noisy tensor𝐱k\\mathbf\{x\}\_\{k\}rather than from a fixed interaction graph\. We first derive an inferred soft trajectory for each agent, with𝐩i,τinf\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}denoting its inferred position at timestepτ\\tau, and then compute pairwise trajectory proximity as

di​j=minτ=1,…,T⁡‖𝐩i,τinf−𝐩j,τinf‖1,d\_\{ij\}=\\min\_\{\\tau=1,\\ldots,T\}\\left\\\|\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}\-\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{j,\\tau\}\\right\\\|\_\{1\},\(5\)which measures the minimum expected distance between two agents along the current inferred trajectories\. For each agent, we retain only the top\-MkM\_\{k\}nearest neighbors, whereMkM\_\{k\}is set as a clipped fraction of the current team sizeNN\. As illustrated in Fig\.[2](https://arxiv.org/html/2605.13296#S3.F2), the neighborhood is recomputed at every diffusion step: early in denoising, it remains relatively broad to preserve potentially relevant interactions, whereas later it becomes sparser as the inferred trajectory becomes more precise\. Let𝒩k​\(i\)\\mathcal\{N\}\_\{k\}\(i\)denote the sparse neighborhood of agentiiat diffusion stepkk\. For each timestepτ\\tau, the social module first projects the agent features into query, key, and value vectors, denoted by𝐪i,τ\\mathbf\{q\}\_\{i,\\tau\},𝐤j,τ\\mathbf\{k\}\_\{j,\\tau\}, and𝐯j,τ\\mathbf\{v\}\_\{j,\\tau\}\. Attention for agentiiis then computed only overj∈𝒩k​\(i\)j\\in\\mathcal\{N\}\_\{k\}\(i\):

αi​jτ=softmaxj∈𝒩k​\(i\)​\(𝐪i,τ⊤​𝐤j,τd\+bθ​\(𝐩i,τinf−𝐩j,τinf\)\),\\alpha\_\{ij\}^\{\\tau\}=\\mathrm\{softmax\}\_\{j\\in\\mathcal\{N\}\_\{k\}\(i\)\}\\left\(\\frac\{\\mathbf\{q\}\_\{i,\\tau\}^\{\\top\}\\mathbf\{k\}\_\{j,\\tau\}\}\{\\sqrt\{d\}\}\+b\_\{\\theta\}\\\!\\left\(\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}\-\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{j,\\tau\}\\right\)\\right\),\(6\)wherebθ​\(⋅\)b\_\{\\theta\}\(\\cdot\)is a learned geometric bias generated from relative inferred positions\. The updated social feature is obtained by aggregating value vectors from the selected neighbors according to the sparse attention weights\. This computation preserves focused attention on the most relevant local interactions while reducing the cost of denseN2N^\{2\}interaction modeling\.

#### Training objective\.

Our main training signal is the generative objective

ℒgen=ℒaux\+λKL​ℒKL,\\mathcal\{L\}\_\{\\mathrm\{gen\}\}=\\mathcal\{L\}\_\{\\mathrm\{aux\}\}\+\\lambda\_\{\\mathrm\{KL\}\}\\mathcal\{L\}\_\{\\mathrm\{KL\}\},\(7\)whereℒaux\\mathcal\{L\}\_\{\\mathrm\{aux\}\}is the auxiliary clean\-state prediction term in Eq\. \([3](https://arxiv.org/html/2605.13296#S2.E3)\)\. The KL term corresponds to the posterior\-matching component of the variational boundℒvb\\mathcal\{L\}\_\{\\mathrm\{vb\}\}\. Letq​\(𝐱0,𝐜\)q\(\\mathbf\{x\}\_\{0\},\\mathbf\{c\}\)denote the expert data distribution over clean joint action tensors and MAPF conditions\. The KL term is

ℒKL=𝔼q​\(𝐱0,𝐜\)𝔼k∼Unif​\(\{1,…,K\}\)𝔼q​\(𝐱k∣𝐱0\)\[KL\(q\(𝐱k−1∣𝐱k,𝐱0\)∥pθ\(𝐱k−1∣𝐱k,𝐜\)\)\]\.\\mathcal\{L\}\_\{\\mathrm\{KL\}\}=\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{0\},\\mathbf\{c\}\)\}\\mathbb\{E\}\_\{k\\sim\\mathrm\{Unif\}\(\\\{1,\\ldots,K\\\}\)\}\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\left\[\\mathrm\{KL\}\\\!\\left\(q\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{x\}\_\{0\}\)\\,\\\|\\,p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)\\right\)\\right\]\.\(8\)Under the𝐱0\\mathbf\{x\}\_\{0\}\-parameterization,pθ​\(𝐱k−1∣𝐱k,𝐜\)p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)is constructed from Eq\. \([2](https://arxiv.org/html/2605.13296#S2.E2)\) usingp~θ​\(𝐱0∣𝐱k,𝐜\)\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)\. In practice,ℒaux\\mathcal\{L\}\_\{\\mathrm\{aux\}\}is a token\-level cross\-entropy loss on clean action prediction, whileℒKL\\mathcal\{L\}\_\{\\mathrm\{KL\}\}aligns the induced reverse transition with the analytic posterior\.

We further add a task\-oriented auxiliary lossℒtask\\mathcal\{L\}\_\{\\mathrm\{task\}\}for goal progress, conflict reduction, and action validity, with exact forms provided in Appendix[D\.3](https://arxiv.org/html/2605.13296#A4.SS3)\. The final objective is

ℒ=ℒgen\+ℒtask,\\mathcal\{L\}=\\mathcal\{L\}\_\{\\mathrm\{gen\}\}\+\\mathcal\{L\}\_\{\\mathrm\{task\}\},\(9\)whereℒgen\\mathcal\{L\}\_\{\\mathrm\{gen\}\}remains the primary expert\-imitation objective\. For stable optimization, we first train withℒgen\\mathcal\{L\}\_\{\\mathrm\{gen\}\}alone and then gradually increase the weight ofℒtask\\mathcal\{L\}\_\{\\mathrm\{task\}\}\.

#### Agent scalability\.

DiffLNS is not architecturally tied to a fixed team size\. Although the diffusion initializer is trained on smaller teams, it can be applied to larger teams at inference time because forward corruption and reverse denoising operate tokenwise on the joint action tensor\. Increasing the number of agents changes only the number of action tokens, not the form of the diffusion process\.

The denoiser shares parameters across agents and is permutation\-equivariant along the agent dimension:

fθ​\(P​𝐱k,P​c\)=P​fθ​\(𝐱k,c\),f\_\{\\theta\}\(P\\mathbf\{x\}\_\{k\},Pc\)=Pf\_\{\\theta\}\(\\mathbf\{x\}\_\{k\},c\),\(10\)wherePPis a permutation matrix acting on the agent axis\. During denoising, each action token is predicted from the corrupted joint plan and the MAPF condition, using both global scene context and local interaction cues from other agents\. Sparse social attention implements this locality bias through dynamic neighborhoods𝒩i​\(k\)\\mathcal\{N\}\_\{i\}\(k\)constructed from the current trajectory estimate\. These properties make inference on larger teams well defined and provide an inductive bias for reusing local coordination patterns, but they do not guarantee distributional generalization\. We therefore evaluate scaling beyond the training agent range empirically and show that DiffLNS remains effective on substantially larger teams in dense MAPF settings\.

### 3\.3Iterative Multi\-Sample Repair with LNS2

The diffusion initializer produces structured plans that capture useful global coordination patterns, but these plans may still contain unfinished paths, residual conflicts, or invalid moves\. We therefore use LNS2 as a repair stage to convert these drafts into valid MAPF solutions\.

#### Preprocessing diffusion drafts\.

Empirically, we observe that in many diffusion drafts, some agents already reach their goals, while many others terminate close to their goals\. Before passing each sampled draft to LNS2, we therefore apply a short preprocessing step: redundant suffixes are removed after an agent reaches its goal, and unfinished trajectories are completed with an obstacle\-aware shortest\-path suffix from the last valid position to the goal\. Here, invalid actions refer to action attempts that move an agent out of the map or into an obstacle\. This preprocessing step preserves useful global structure while completing all trajectories to their goals before repair\.

Algorithm 1Iterative Repair with D3PM and LNS2

Input:MAPF instanceℐ\\mathcal\{I\}, initializerpθp\_\{\\theta\}, batch sizeMM, roundsRR, time budgetBB

#### LNS2 repair\.

Given the preprocessed draft, LNS2 performs neighborhood\-based replanning to restore feasibility\. Starting from the diffusion\-generated trajectories, it iteratively selects subsets of agents for replanning while keeping the remaining trajectories fixed\. This local repair process progressively removes residual vertex conflicts, edge\-swap conflicts, and other inconsistencies until a feasible global solution is obtained or the repair budget is exhausted\.

#### Multi\-sample selection and iterative retry\.

For each MAPF instance, the diffusion initializer samples multiple drafts under the same condition, allowing different global coordination patterns to be explored\. If a round yields feasible repaired candidates, DiffLNS returns the one with the smallest SOC\. Otherwise, it samples a new batch and repeats the procedure until either the maximum number of repair rounds is reached or the time budget is exhausted\. This iterative strategy improves robustness by exploring diverse structured initializations within the given evaluation budget\.

## 4Experiments

#### Baselines and metrics\.

We compare DiffLNS with LNS2\(Li et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib11)\), LNS2\+RL\(Wang et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib31)\), HMAGAT\(Jain et al\.,[2026](https://arxiv.org/html/2605.13296#bib.bib8)\), and LaCAM3\(Okumura,[2024](https://arxiv.org/html/2605.13296#bib.bib19)\)\. These baselines cover a strong repair\-based solver, a learning\-augmented repair method, a state\-of\-the\-art learning\-based solver, and a strong classical anytime solver that can continue improving SOC after finding a feasible solution within the time budget\. For DiffLNS, we generate candidates in batches, withM=4M=4diffusion samples per batch, and use a 120 s downstream LNS2 repair budget for each candidate\. DiffLNS terminates successfully once any candidate is repaired into a feasible solution\. DiffLNS, LNS2, LNS2\+RL, and HMAGAT are evaluated as fixed\-budget methods: for each benchmark family and agent cardinality, they use the same per\-setting time limit, and timeout before finding a feasible solution is counted as failure\. By contrast, LaCAM3 is evaluated under a matched per\-instance wall\-clock budget, with its time limit set to the actual runtime of DiffLNS on the same instance\. Since this protocol differs from the fixed\-budget setting, LaCAM3 is used only as a matched\-time reference for DiffLNS and is not directly compared with the other baselines\. For a fair compute protocol, learning\-based methods with neural inference, including DiffLNS, LNS2\+RL, and HMAGAT, are evaluated with access to the same NVIDIA L40S GPU, while all CPU\-based components, including LNS2 repair and classical search baselines, are run in the same CPU environment\. We report success rate \(SR\), average sum of costs \(SOC\) over successful instances, and average runtime over all instances using actual elapsed time, including failed runs\. HMAGAT terminates when either the wall\-clock limit or the 512\-step episode limit is reached\. DiffLNS runtime includes both diffusion generation and downstream LNS2 repair\. Detailed evaluation protocols are provided in Appendix[C\.1](https://arxiv.org/html/2605.13296#A3.SS1)\.

#### Evaluation settings\.

All evaluation instances are randomly generated with POGEMA\(Skrynnik et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib26)\)\. We consider five environment families:*Small Random*\(10×1010\\times 10, obstacle density 0\.175\),*Medium Maze*\(25×2525\\times 25, average obstacle density 0\.33\),*Medium Room*\(23×2323\\times 23, average obstacle density 0\.34\),*Medium Warehouse*\(25×2525\\times 25, obstacle density 0\.35\), and*Large Maze*\(33×3333\\times 33, average obstacle density 0\.33\)\. These settings emphasize dense and congested MAPF regimes, where global coordination and repair quality become major bottlenecks\. Detailed per\-setting statistics and more result analyses are provided in Appendix[C\.1](https://arxiv.org/html/2605.13296#A3.SS1)\.

### 4\.1Results

![Refer to caption](https://arxiv.org/html/2605.13296v1/x3.png)Figure 3:Performance comparison on MAPF benchmarks across different environments\. The bottom row reports relative SOC, where each value is normalized by the lowest SOC among all methods for the same environment and agent number\. Transparent regions indicate 95% confidence intervals\.As shown in Fig\.[3](https://arxiv.org/html/2605.13296#S4.F3), DiffLNS matches or exceeds all baselines in SR across 20 evaluated settings, with a 95\.8% average SR and a 9\.6\-point gain over LNS2\+RL, the strongest baseline by average SR\. The advantage of DiffLNS is especially clear in maze and warehouse environments, where the success rates of classical baselines decrease more sharply as congestion increases\. Under the matched\-time protocol, DiffLNS achieves higher SR than LaCAM3 in all dense settings, especially at larger agent counts, although it has higher SOC in some scenarios\. HMAGAT is fast and stable in some room and warehouse cases, but its SOC is consistently higher, indicating less cost\-efficient coordination\. Its runtime should also be interpreted with its 512\-step episode limit: HMAGAT stops when either the wall\-clock or episode limit is reached, so unfinished rollouts may terminate early and would yield extremely large SOC if evaluated directly\. Overall, these results show that DiffLNS is robust across agent scales and support the effectiveness of combining generative initialization with classical repair\.

DiffLNS incurs higher average runtime in most evaluated settings because each candidate requires reverse\-diffusion denoising followed by LNS2 repair\. Runtime tends to increase with instance difficulty, as harder cases require more generated candidates and repair attempts before a feasible solution is found; detailed candidate statistics are provided in Appendix[C\.2](https://arxiv.org/html/2605.13296#A3.SS2)\. Since candidates are independent, denoising and repair can be parallelized with sufficient GPU and CPU resources, which can substantially reduce wall\-clock runtime\. DiffLNS therefore trades additional but parallelizable computation for higher feasibility in congested settings while maintaining competitive SOC\.

### 4\.2Initialization Comparison under Fixed LNS2 Repair

To isolate the effect of initialization quality from the full DiffLNS pipeline, we disable multi\-sample generation and compare a single diffusion\-generated initialization with the official LNS2 initialization\. Both initializations are passed to the same downstream LNS2 repair procedure under the same 120 s repair budget\. Figure[4](https://arxiv.org/html/2605.13296#S4.F4)reports the repair success rate \(SR\) and the LNS2 repair runtime, where runtime is computed only over successful repairs and excludes the cost of initialization generation\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x4.png)Figure 4:Initialization comparison under fixed LNS2 repair across five benchmark families\. Both initialization strategies are repaired by the same LNS2 procedure under the same repair budget\. Runtime is computed over successful repairs only, with N/A denoting no successful repairs\. Error bars indicate 95% confidence intervals\.Figure[4](https://arxiv.org/html/2605.13296#S4.F4)shows that diffusion\-generated initializations improve repair success in most dense and congested settings, with larger gains in highly coupled maze and room scenarios, while often leading to comparable or lower LNS2 repair time among successfully repaired instances\. Overall, even a single diffusion\-generated initialization provides a more repairable starting point for LNS2, indicating that DiffLNS gains are not solely due to multi\-sample generation and selection\. Appendix[B](https://arxiv.org/html/2605.13296#A2)further shows that D3PM warm\-starting outperforms repeated prioritized\-planning initializations under the same multi\-start budget\.

Interestingly, higher repairability does not necessarily require fewer raw conflicts before repair\. In our experiments, DiffLNS initializations usually contain more vertex or edge conflicts than the official LNS2 initialization, yet often achieve higher repair success with comparable or lower repair time\. This is consistent with prior work on selecting promising initial solutions for LNS\-based MAPF\(Huber et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib7)\): initialization quality should be judged by downstream LNS outcomes rather than by pre\-repair statistics alone\. The official LNS2 initialization uses sequential PP\+SIPPS, which can produce locally low\-conflict and low\-cost paths under a fixed priority order but may yield globally rigid plans that are difficult to reorganize through local repair\. In contrast, D3PM samples joint action plans from a learned expert trajectory prior, producing more coordinated and structured drafts that can be easier for LNS2 to repair even without fewer raw conflicts\.

### 4\.3Ablation Study on Sparse Social Attention

To evaluate the proposed sparse social attention, we compare it with a dense all\-to\-all variant while keeping the rest of the DiffLNS framework unchanged\. We focus on the densest settings of three representative benchmark environments: Medium Maze \(N=190N=190\), Medium Room \(N=192N=192\), and Medium Warehouse \(N=252N=252\), where social interaction modeling is most critical\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x5.png)Figure 5:Ablation of sparse versus dense social attention on three dense maps\. \(a\) Repair success rate\. \(b\) Average number of generated candidates\. Error bars indicate 95% confidence intervals\.As shown in Fig\.[5](https://arxiv.org/html/2605.13296#S4.F5), sparse social attention consistently achieves higher repair success rates while requiring fewer generated candidates across all three settings\. Averaged over the three tested settings, the dense variant also incurs approximately 12% higher end\-to\-end runtime than the sparse variant\. In congested MAPF instances, conflict\-relevant interactions are primarily local, whereas dense attention distributes modeling capacity across many irrelevant agent pairs\. By dynamically focusing on nearby agents that are most relevant to the current trajectory estimate, the sparse variant provides more effective social context and produces initial plans that are easier for LNS2 to repair in highly congested scenarios\.

### 4\.4Limitations

DiffLNS is most useful on dense, difficult MAPF instances where initialization quality strongly affects repair; on simpler instances, pure LNS2 is often sufficient, making the extra initialization cost less necessary\. Since the current denoiser is trained on23×2323\\times 23maps, generalization to substantially larger maps may be affected by distribution shift and require broader training scales\. Moreover, DiffLNS remains constrained by the downstream LNS2 repair stage: results on the hardest*Medium Room*setting and the fixed\-repair analysis in Section[4\.2](https://arxiv.org/html/2605.13296#S4.SS2)show that D3PM warm\-starting improves repairability but cannot fully overcome extremely difficult repair cases under a limited budget\.

## 5Related Work

#### Classical MAPF solvers\.

Classical MAPF algorithms formulate planning as combinatorial search\. Representative methods include conflict\-based search \(CBS\), bounded\-suboptimal variants such as EECBS, and joint\-configuration search methods such as LaCAM\(Sharon et al\.,[2012](https://arxiv.org/html/2605.13296#bib.bib25);Li et al\.,[2021b](https://arxiv.org/html/2605.13296#bib.bib10);Okumura,[2023](https://arxiv.org/html/2605.13296#bib.bib18)\)\. Large neighborhood search \(LNS\) offers a scalable repair\-based paradigm that starts from an initial plan and improves it by replanning agent subsets while keeping the remaining paths fixed\(Li et al\.,[2021a](https://arxiv.org/html/2605.13296#bib.bib9),[2022](https://arxiv.org/html/2605.13296#bib.bib11)\)\. Although initialization quality becomes increasingly important on harder instances\(Li et al\.,[2021a](https://arxiv.org/html/2605.13296#bib.bib9)\), most LNS\-based MAPF studies focus on improving the repair process, including neighborhood selection, neural neighborhood generation, adaptive destroy strategies, and reinforcement\-learning\-based replanners\(Huang et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib6);Yan and Wu,[2024](https://arxiv.org/html/2605.13296#bib.bib32);Phan et al\.,[2024](https://arxiv.org/html/2605.13296#bib.bib22);Wang et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib31)\)\. Direct studies of MAPF initialization remain limited and mainly select from existing solutions rather than generating higher\-quality initializations\(Huber et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib7)\)\. Our work instead improves the quality and diversity of initial plans provided to LNS2, targeting a complementary stage of the LNS pipeline\.

#### Learning\-based MAPF\.

Learning\-based MAPF methods amortize coordination through neural policies or predictors\. Early methods such as PRIMAL, DHC, and SCRIMP learn decentralized local coordination through imitation learning or multi\-agent reinforcement learning\(Sartoretti et al\.,[2019](https://arxiv.org/html/2605.13296#bib.bib23);Ma et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib16);Wang et al\.,[2023](https://arxiv.org/html/2605.13296#bib.bib30)\)\. Recent methods improve interaction modeling with graph, hypergraph, or token\-based architectures, including MAGAT, HMAGAT, MAPF\-GPT, and centralized predictors such as RAILGUN\(Li et al\.,[2021c](https://arxiv.org/html/2605.13296#bib.bib12);Jain et al\.,[2026](https://arxiv.org/html/2605.13296#bib.bib8);Andreychuk et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib1);Tang et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib28)\)\. Although efficient at inference time, these methods typically produce limited rollouts and struggle to strictly satisfy hard MAPF constraints in dense environments\. In contrast, DiffLNS generates multiple globally structured joint plans as initialization candidates and relies on LNS2 repair to guarantee feasibility\.

#### Diffusion and generative planning\.

Diffusion models have been widely adopted as trajectory priors for robot planning, motion generation, and multi\-robot coordination, often in continuous state spaces with additional collision handling or planner guidance\(Carvalho et al\.,[2023](https://arxiv.org/html/2605.13296#bib.bib3);Shaoul et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib24);Liang et al\.,[2025a](https://arxiv.org/html/2605.13296#bib.bib13),[b](https://arxiv.org/html/2605.13296#bib.bib14)\)\. Their stochastic sampling naturally yields diverse candidates for a given problem instance\. However, most diffusion\-based planners operate over continuous trajectories, whereas grid\-based MAPF is discrete and requires strict vertex and edge conflict constraints\. We therefore formulate diffusion over discrete joint action tensors and use its samples to warm\-start LNS2, combining multimodal generative priors with classical hard\-constraint repair\.

## 6Conclusion

We presented DiffLNS, a hybrid MAPF framework that uses D3PM as a learned initializer for LNS2\. DiffLNS models joint action plans through a discrete diffusion process and generates structured repair seeds conditioned on the MAPF instance, shifting the focus from repair\-only improvement to initialization quality\. These drafts are not required to satisfy all hard constraints by themselves; instead, they provide coordinated spatiotemporal priors that make downstream LNS2 repair more robust\. Together with diffusion\-aware sparse social attention and multi\-sample repair, this design improves repair success in dense and congested settings while maintaining competitive solution quality\. More broadly, our results suggest that discrete diffusion models can serve as structured, iterative generators for multi\-agent decision making, providing useful joint priors for downstream planning and control\.

## References

- Andreychuk et al\. \(2025\)Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov, and Alexey Skrynnik\.Mapf\-gpt: Imitation learning for multi\-agent pathfinding at scale\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 39\(22\):23126–23134, Apr\. 2025\.doi:10\.1609/aaai\.v39i22\.34477\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/34477](https://ojs.aaai.org/index.php/AAAI/article/view/34477)\.
- Austin et al\. \(2021\)Jacob Austin, Daniel D\. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg\.Structured denoising diffusion models in discrete state\-spaces\.In M\. Ranzato, A\. Beygelzimer, Y\. Dauphin, P\.S\. Liang, and J\. Wortman Vaughan, editors,*Advances in Neural Information Processing Systems*, volume 34, pages 17981–17993\. Curran Associates, Inc\., 2021\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2021/file/958c530554f78bcd8e97125b70e6973d\-Paper\.pdf](https://proceedings.neurips.cc/paper_files/paper/2021/file/958c530554f78bcd8e97125b70e6973d-Paper.pdf)\.
- Carvalho et al\. \(2023\)J\. Carvalho, A\. T\. Le, M\. Baierl, D\. Koert, and J\. Peters\.Motion planning diffusion: Learning and planning of robot motions with diffusion models\.In*IEEE/RSJ International Conference on Intelligent Robots and Systems \(IROS\)*, 2023\.URL[https://arxiv\.org/abs/2308\.01557](https://arxiv.org/abs/2308.01557)\.
- Erdmann and Lozano\-Perez \(1986\)M\. Erdmann and T\. Lozano\-Perez\.On multiple moving objects\.In*Proceedings\. 1986 IEEE International Conference on Robotics and Automation*, volume 3, pages 1419–1424, 1986\.doi:10\.1109/ROBOT\.1986\.1087401\.
- Hoogeboom et al\. \(2021\)Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling\.Argmax flows and multinomial diffusion: learning categorical distributions\.In*Proceedings of the 35th International Conference on Neural Information Processing Systems*, NIPS ’21, Red Hook, NY, USA, 2021\. Curran Associates Inc\.ISBN 9781713845393\.
- Huang et al\. \(2022\)Taoan Huang, Jiaoyang Li, Sven Koenig, and Bistra Dilkina\.Anytime multi\-agent path finding via machine learning\-guided large neighborhood search\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 36\(9\):9368–9376, Jun\. 2022\.doi:10\.1609/aaai\.v36i9\.21168\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/21168](https://ojs.aaai.org/index.php/AAAI/article/view/21168)\.
- Huber et al\. \(2025\)Marc Huber, Günther R\. Raidl, and Christian Blum\.Learning to select promising initial solutions for large neighborhood search\-based multi\-agent path finding\.In Alexis Quesada\-Arencibia, Michael Affenzeller, and Roberto Moreno\-Díaz, editors,*Computer Aided Systems Theory – EUROCAST 2024*, volume 15172 of*LNCS*, pages 236–250\. Springer, 2025\.doi:10\.1007/978\-3\-031\-82949\-9\_22\.URL[https://www\.ac\.tuwien\.ac\.at/files/pub/huber\-24\.pdf](https://www.ac.tuwien.ac.at/files/pub/huber-24.pdf)\.
- Jain et al\. \(2026\)Rishabh Jain, Keisuke Okumura, Michael Amir, Pietro Liò, and Amanda Prorok\.Pairwise is not enough: Hypergraph neural networks for multi\-agent pathfinding\.In*International Conference on Learning Representations \(ICLR\)*, 2026\.
- Li et al\. \(2021a\)Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J\. Stuckey, and Sven Koenig\.Anytime multi\-agent path finding via large neighborhood search\.In Zhi\-Hua Zhou, editor,*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI\-21*, pages 4127–4135\. International Joint Conferences on Artificial Intelligence Organization, 8 2021a\.doi:10\.24963/ijcai\.2021/568\.URL[https://doi\.org/10\.24963/ijcai\.2021/568](https://doi.org/10.24963/ijcai.2021/568)\.Main Track\.
- Li et al\. \(2021b\)Jiaoyang Li, Wheeler Ruml, and Sven Koenig\.Eecbs: A bounded\-suboptimal search for multi\-agent path finding\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 35\(14\):12353–12362, May 2021b\.doi:10\.1609/aaai\.v35i14\.17466\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/17466](https://ojs.aaai.org/index.php/AAAI/article/view/17466)\.
- Li et al\. \(2022\)Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J\. Stuckey, and Sven Koenig\.MAPF\-LNS2: fast repairing for multi\-agent path finding via large neighborhood search\.In*Thirty\-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty\-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelfth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 \- March 1, 2022*, pages 10256–10265\. AAAI Press, 2022\.doi:10\.1609/AAAI\.V36I9\.21266\.URL[https://doi\.org/10\.1609/aaai\.v36i9\.21266](https://doi.org/10.1609/aaai.v36i9.21266)\.
- Li et al\. \(2021c\)Qingbiao Li, Weizhe Lin, Zhe Liu, and Amanda Prorok\.Message\-aware graph attention networks for large\-scale multi\-robot path planning\.*IEEE Robotics Autom\. Lett\.*, 6\(3\):5533–5540, 2021c\.doi:10\.1109/LRA\.2021\.3077863\.URL[https://doi\.org/10\.1109/LRA\.2021\.3077863](https://doi.org/10.1109/LRA.2021.3077863)\.
- Liang et al\. \(2025a\)Jinhao Liang, Jacob K Christopher, Sven Koenig, and Ferdinando Fioretto\.Simultaneous multi\-robot motion planning with projected diffusion models\.In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste\-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors,*Proceedings of the 42nd International Conference on Machine Learning*, volume 267 of*Proceedings of Machine Learning Research*, pages 37162–37180\. PMLR, 13–19 Jul 2025a\.URL[https://proceedings\.mlr\.press/v267/liang25e\.html](https://proceedings.mlr.press/v267/liang25e.html)\.
- Liang et al\. \(2025b\)Jinhao Liang, Sven Koenig, and Ferdinando Fioretto\.Discrete\-guided diffusion for scalable and safe multi\-robot motion planning, 2025b\.URL[https://arxiv\.org/abs/2508\.20095](https://arxiv.org/abs/2508.20095)\.
- Loshchilov and Hutter \(2019\)Ilya Loshchilov and Frank Hutter\.Decoupled weight decay regularization\.In*International Conference on Learning Representations*, 2019\.URL[https://openreview\.net/forum?id=Bkg6RiCqY7](https://openreview.net/forum?id=Bkg6RiCqY7)\.
- Ma et al\. \(2021\)Ziyuan Ma, Yudong Luo, and Hang Ma\.Distributed heuristic multi\-agent path finding with communication\.In*2021 IEEE International Conference on Robotics and Automation \(ICRA\)*, pages 8699–8705, 2021\.doi:10\.1109/ICRA48506\.2021\.9560748\.
- Nichol and Dhariwal \(2021\)Alexander Quinn Nichol and Prafulla Dhariwal\.Improved denoising diffusion probabilistic models\.In Marina Meila and Tong Zhang, editors,*Proceedings of the 38th International Conference on Machine Learning*, volume 139 of*Proceedings of Machine Learning Research*, pages 8162–8171\. PMLR, 18–24 Jul 2021\.URL[https://proceedings\.mlr\.press/v139/nichol21a\.html](https://proceedings.mlr.press/v139/nichol21a.html)\.
- Okumura \(2023\)Keisuke Okumura\.Lacam: Search\-based algorithm for quick multi\-agent pathfinding\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 37\(10\):11655–11662, Jun\. 2023\.doi:10\.1609/aaai\.v37i10\.26377\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/26377](https://ojs.aaai.org/index.php/AAAI/article/view/26377)\.
- Okumura \(2024\)Keisuke Okumura\.Engineering lacam\*: Towards real\-time, large\-scale, and near\-optimal multi\-agent pathfinding\.In Mehdi Dastani, Jaime Simão Sichman, Natasha Alechina, and Virginia Dignum, editors,*Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2024, Auckland, New Zealand, May 6\-10, 2024*, pages 1501–1509\. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024\.doi:10\.5555/3635637\.3663010\.URL[https://dl\.acm\.org/doi/10\.5555/3635637\.3663010](https://dl.acm.org/doi/10.5555/3635637.3663010)\.
- Peebles and Xie \(2023\)William Peebles and Saining Xie\.Scalable diffusion models with transformers\.In*Proceedings of the IEEE/CVF International Conference on Computer Vision \(ICCV\)*, pages 4195–4205, October 2023\.
- Perez et al\. \(2017\)Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron Courville\.Film: Visual reasoning with a general conditioning layer, 2017\.URL[https://arxiv\.org/abs/1709\.07871](https://arxiv.org/abs/1709.07871)\.
- Phan et al\. \(2024\)Thomy Phan, Taoan Huang, Bistra Dilkina, and Sven Koenig\.Adaptive anytime multi\-agent path finding using bandit\-based large neighborhood search\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 38\(16\):17514–17522, Mar\. 2024\.doi:10\.1609/aaai\.v38i16\.29701\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/29701](https://ojs.aaai.org/index.php/AAAI/article/view/29701)\.
- Sartoretti et al\. \(2019\)Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, T\. K\. Satish Kumar, Sven Koenig, and Howie Choset\.Primal: Pathfinding via reinforcement and imitation multi\-agent learning\.*IEEE Robotics and Automation Letters*, 4\(3\):2378–2385, 2019\.doi:10\.1109/LRA\.2019\.2903261\.
- Shaoul et al\. \(2025\)Yorai Shaoul, Itamar Mishani, Shivam Vats, Jiaoyang Li, and Maxim Likhachev\.Multi\-robot motion planning with diffusion models\.In Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu, editors,*International Conference on Learning Representations*, volume 2025, pages 95791–95811, 2025\.URL[https://proceedings\.iclr\.cc/paper\_files/paper/2025/file/eee6efe709623f36483e3fbb0bb513dd\-Paper\-Conference\.pdf](https://proceedings.iclr.cc/paper_files/paper/2025/file/eee6efe709623f36483e3fbb0bb513dd-Paper-Conference.pdf)\.
- Sharon et al\. \(2012\)Guni Sharon, Roni Stern, Ariel Felner, and Nathan R\. Sturtevant\.Conflict\-based search for optimal multi\-agent path finding\.In Jörg Hoffmann and Bart Selman, editors,*Proceedings of the Twenty\-Sixth AAAI Conference on Artificial Intelligence, July 22\-26, 2012, Toronto, Ontario, Canada*, pages 563–569\. AAAI Press, 2012\.doi:10\.1609/AAAI\.V26I1\.8140\.URL[https://doi\.org/10\.1609/aaai\.v26i1\.8140](https://doi.org/10.1609/aaai.v26i1.8140)\.
- Skrynnik et al\. \(2025\)Alexey Skrynnik, Anton Andreychuk, Anatolii Borzilov, Alexander Chernyavskiy, Konstantin Yakovlev, and Aleksandr Panov\.Pogema: A benchmark platform for cooperative multi\-agent pathfinding\.In Y\. Yue, A\. Garg, N\. Peng, F\. Sha, and R\. Yu, editors,*International Conference on Learning Representations*, volume 2025, pages 5576–5606, 2025\.URL[https://proceedings\.iclr\.cc/paper\_files/paper/2025/file/10d19888a94f390e58f922ab3937e1cb\-Paper\-Conference\.pdf](https://proceedings.iclr.cc/paper_files/paper/2025/file/10d19888a94f390e58f922ab3937e1cb-Paper-Conference.pdf)\.
- Stern et al\. \(2019\)Roni Stern, Nathan R\. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T\. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T\. K\. Satish Kumar, Roman Barták, and Eli Boyarski\.Multi\-agent pathfinding: Definitions, variants, and benchmarks\.In Pavel Surynek and William Yeoh, editors,*Proceedings of the Twelfth International Symposium on Combinatorial Search, SOCS 2019, Napa, California, 16\-17 July 2019*, pages 151–158\. AAAI Press, 2019\.doi:10\.1609/SOCS\.V10I1\.18510\.URL[https://doi\.org/10\.1609/socs\.v10i1\.18510](https://doi.org/10.1609/socs.v10i1.18510)\.
- Tang et al\. \(2025\)Yimin Tang, Xiao Xiong, Jingyi Xi, Jiaoyang Li, Erdem Bıyık, and Sven Koenig\.Railgun: A unified convolutional policy for multi\-agent path finding across different environments and tasks\.In*Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems \(IROS\)*, pages 8645–8651, 2025\.doi:10\.1109/IROS60139\.2025\.11247527\.
- Vaswani et al\. \(2017\)Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin\.Attention is all you need\.In I\. Guyon, U\. Von Luxburg, S\. Bengio, H\. Wallach, R\. Fergus, S\. Vishwanathan, and R\. Garnett, editors,*Advances in Neural Information Processing Systems*, volume 30\. Curran Associates, Inc\., 2017\.URL[https://proceedings\.neurips\.cc/paper\_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa\-Paper\.pdf](https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf)\.
- Wang et al\. \(2023\)Yutong Wang, Bairan Xiang, Shinan Huang, and Guillaume Sartoretti\.Scrimp: Scalable communication for reinforcement\- and imitation\-learning\-based multi\-agent pathfinding\.In*Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems*, AAMAS ’23, page 2598–2600, Richland, SC, 2023\. International Foundation for Autonomous Agents and Multiagent Systems\.ISBN 9781450394321\.
- Wang et al\. \(2025\)Yutong Wang, Tanishq Duhan, Jiaoyang Li, and Guillaume Sartoretti\.Lns2\+rl: Combining multi\-agent reinforcement learning with large neighborhood search in multi\-agent path finding\.*Proceedings of the AAAI Conference on Artificial Intelligence*, 39\(22\):23343–23350, Apr\. 2025\.doi:10\.1609/aaai\.v39i22\.34501\.URL[https://ojs\.aaai\.org/index\.php/AAAI/article/view/34501](https://ojs.aaai.org/index.php/AAAI/article/view/34501)\.
- Yan and Wu \(2024\)Zhongxia Yan and Cathy Wu\.Neural neighborhood search for multi\-agent path finding\.In B\. Kim, Y\. Yue, S\. Chaudhuri, K\. Fragkiadaki, M\. Khan, and Y\. Sun, editors,*International Conference on Learning Representations*, volume 2024, pages 48473–48494, 2024\.URL[https://proceedings\.iclr\.cc/paper\_files/paper/2024/file/d41f8403e9bb5141bc2c81fad7658185\-Paper\-Conference\.pdf](https://proceedings.iclr.cc/paper_files/paper/2024/file/d41f8403e9bb5141bc2c81fad7658185-Paper-Conference.pdf)\.

## Appendix AOutline

This appendix provides additional results, protocol details, and implementation details that complement the main paper\. Appendix[B](https://arxiv.org/html/2605.13296#A2)presents a controlled PP\-Multistart comparison that separates the effect of the learned diffusion initializer from the benefit of repeated LNS2 initialization attempts\. Appendix[C](https://arxiv.org/html/2605.13296#A3)reports the complete main experimental results, including benchmark details, evaluation budgets, candidate\-generation statistics, and per\-setting numerical results\. Appendix[C\.3](https://arxiv.org/html/2605.13296#A3.SS3)provides additional observations on the behavior of DiffLNS and the compared baselines across scene families\. Finally, Appendix[D](https://arxiv.org/html/2605.13296#A4)describes the implementation details of the training pipeline and denoising network, including expert\-data construction, the conditional denoising architecture, supervised losses, the training schedule, and optimization hyperparameters\.

## Appendix BAdditional Experiment

We further examine whether the improvement of DiffLNS can be explained by repeated LNS2 initialization attempts\. To this end, we construct a PP\-Multistart baseline under a controlled fixed candidate budget, while replacing the diffusion initializer with the official prioritized\-planning initialization used by LNS2\. We evaluate both methods on the most congested setting of each benchmark family:*Small Random*with6060agents,*Medium Maze*with190190agents,*Medium Room*with192192agents,*Medium Warehouse*with252252agents, and*Large Maze*with312312agents\. This experiment is separate from the fixed\-time main evaluation and is designed to isolate the effect of initializer quality under the same number of candidate attempts\. Both methods use the same candidate\-generation budget: batch size44, at most55batches, and at most2020generated candidates\. We report success rate \(SR\), average sum of costs \(SOC\), average runtime over successful instances, and the average number of generated candidates\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x6.png)Figure 6:Comparison between DiffLNS and PP\-Multistart on the most congested setting of each benchmark family\. Both methods use the same multi\-round candidate\-generation budget\. Error bars indicate 95% confidence intervals over test instances\.Figure[6](https://arxiv.org/html/2605.13296#A2.F6)shows that increasing the number of prioritized\-planning initializations is not sufficient to match the robustness of DiffLNS in highly congested scenarios\. Under the same multi\-start budget, DiffLNS achieves higher SR on all five congested settings\. The largest improvement appears on*Medium Room*with192192agents, where DiffLNS improves SR from44%44\\%to64%64\\%\. DiffLNS also improves SR from72%72\\%to82%82\\%on*Small Random*, from92%92\\%to98%98\\%on*Medium Maze*, from94%94\\%to100%100\\%on*Medium Warehouse*, and from86%86\\%to94%94\\%on*Large Maze*\. These results indicate that learned diffusion initialization provides more reliable repair seeds than repeated prioritized\-planning restarts, with the advantage becoming especially important when PP\-Multistart exhibits a clear drop in success rate\.

The SOC results show a different trend from SR\. PP\-Multistart obtains slightly lower SOC than DiffLNS on all five settings, suggesting that prioritized\-planning restarts can produce shorter solutions when they succeed\. However, SOC is averaged only over successful instances\. Since DiffLNS solves more instances, the successful set of DiffLNS can include harder cases that PP\-Multistart fails to solve\. These additional solved cases often require longer coordinated paths and can increase the average SOC\. Therefore, the lower SOC of PP\-Multistart should not be interpreted as uniformly better solution quality, but rather as a result computed on a smaller and easier subset of instances\. The absolute SOC values also increase on larger and more congested maps, reflecting longer path lengths and greater coordination difficulty\.

The runtime and candidate statistics further highlight the robustness–efficiency trade\-off\. The reported runtime includes both initialization and repair\. PP\-Multistart generally requires more generated candidates than DiffLNS\. For example, it uses15\.115\.1candidates on average on*Medium Room*, compared with11\.011\.0for DiffLNS, and it also uses more candidates on*Medium Maze*,*Medium Warehouse*, and*Large Maze*\. Despite this larger candidate usage, PP\-Multistart still obtains lower SR, suggesting that repeated prioritized\-planning initializations are less reliable repair seeds than diffusion\-generated initializations\. Runtime follows a similar pattern in most settings, with PP\-Multistart requiring longer total runtime on*Small Random*,*Medium Maze*,*Medium Room*, and*Medium Warehouse*\. The exception is*Large Maze*, where PP\-Multistart is slightly faster, but still has lower SR and uses more candidates\.

These results indicate that the benefit of DiffLNS is not merely due to using more initialization attempts\. Under the same multi\-start budget, the diffusion initializer provides more structured and repairable starting plans than repeated prioritized\-planning initializations, leading to higher repair robustness in dense MAPF instances while using fewer candidates in most settings\.

## Appendix CComplete Main Experiment Results

### C\.1Supplementary Experimental Details

This appendix supplements the main experimental section with additional protocol details and per\-setting statistics for interpreting Table[4](https://arxiv.org/html/2605.13296#A3.T4), Fig\.[3](https://arxiv.org/html/2605.13296#S4.F3), and Fig\.[4](https://arxiv.org/html/2605.13296#S4.F4)\. Table[1](https://arxiv.org/html/2605.13296#A3.T1)summarizes the benchmark families, map sizes, obstacle\-density ranges, and evaluated agent cardinalities\. Table[2](https://arxiv.org/html/2605.13296#A3.T2)reports the number of evaluated instances and the fixed evaluation budgets for the fixed\-budget baselines\.

#### Baselines and implementation details\.

The main experiments compare DiffLNS with four MAPF baselines: LNS2\(Li et al\.,[2022](https://arxiv.org/html/2605.13296#bib.bib11)\)111[https://github\.com/Jiaoyang\-Li/MAPF\-LNS2](https://github.com/Jiaoyang-Li/MAPF-LNS2), LNS2\+RL\(Wang et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib31)\)222[https://github\.com/marmotlab/LNS2\-RL](https://github.com/marmotlab/LNS2-RL), HMAGAT\(Jain et al\.,[2026](https://arxiv.org/html/2605.13296#bib.bib8)\)333[https://github\.com/proroklab/hmagat](https://github.com/proroklab/hmagat), and LaCAM3\(Okumura,[2024](https://arxiv.org/html/2605.13296#bib.bib19)\)444[https://github\.com/Kei18/lacam3](https://github.com/Kei18/lacam3)\. LNS2 is a strong classical repair\-based solver\. LNS2\+RL is a learning\-augmented variant of LNS2\. HMAGAT is a state\-of\-the\-art learning\-based MAPF solver; in our evaluation, we use its k\-means variant and set the maximum episode length to 512 steps\. LaCAM3 is a strong classical anytime solver\. After finding an initial feasible solution, LaCAM3 continues to improve the solution cost until the given time limit is reached\.

For DiffLNS, we generate candidates in batches, withM=4M=4diffusion samples per batch\. The downstream LNS2 repair budget for each DiffLNS candidate is fixed to 120 s\. DiffLNS terminates successfully once any candidate is repaired into a feasible solution\. For DiffLNS, LNS2, LNS2\+RL, and HMAGAT, we use fixed per\-setting time limits that increase with scene difficulty, ranging from 180 s to 1200 s, as reported in Table[2](https://arxiv.org/html/2605.13296#A3.T2)\. An instance is counted as a failure for all fixed\-budget methods if the time limit is reached before a feasible solution is found\. For all LNS\-based methods, including DiffLNS, LNS2, and LNS2\+RL, the repair neighborhood size is fixed to 8\.

#### Licenses of existing assets\.

We use publicly available implementations only for evaluation and baseline comparison\. MAPF\-LNS2 is released under the USC Research License; LNS2\+RL is released under the MIT License; HMAGAT builds on MAGAT, whose included implementation is released under the MIT License; LaCAM3 is released under the MIT License; and POGEMA is released under the MIT License\. We cite the corresponding papers and provide the official repository links above\.

#### Hardware and parallelization\.

All methods were evaluated on machines equipped with NVIDIA L40S GPUs and Intel Xeon Gold 6348 CPUs at 2\.60 GHz\. Evaluation instances were parallelized across independent worker processes, with each process handling one MAPF instance at a time\. Each worker was allocated 8 logical CPU threads\. Methods requiring GPU acceleration were assigned one NVIDIA L40S GPU per worker, while CPU\-only methods used the same 8\-thread CPU setting without GPU acceleration\. This protocol ensures that all methods are evaluated under the same per\-instance CPU resource allocation, with GPU resources provided only to methods that require neural inference\.

#### Evaluation metrics and runtime protocol\.

We report success rate \(SR\), average sum of costs \(SOC\), and average runtime\. SR is the percentage of instances in which all agents reach their assigned goals within the given budget\. SOC is computed only over successful instances, while runtime is averaged over all instances using the actual elapsed time of each run, including failed runs\. For fixed\-budget solvers, failed runs may terminate either at the wall\-clock time limit or at a method\-specific stopping condition\. In particular, HMAGAT terminates when either the wall\-clock limit or the 512\-step episode limit is reached, whichever comes first\. For DiffLNS, runtime includes both diffusion generation and downstream LNS2 repair\.

DiffLNS, LNS2, LNS2\+RL, and HMAGAT are evaluated under fixed per\-setting time budgets, where each setting is defined by a benchmark family and an agent cardinality\. These budgets are assigned according to setting difficulty estimated from preliminary pilot runs: larger or more congested settings are given longer budgets, while easier settings use shorter budgets to avoid unnecessary computation\. Within each setting, all fixed\-budget methods use the same time limit, and timeout before finding a feasible solution is counted as failure\.

LaCAM3 is evaluated under a matched per\-instance time budget rather than this fixed\-budget protocol\. Specifically, for each instance, the time limit of LaCAM3 is set to the actual runtime of DiffLNS on the same instance\. This protocol allows LaCAM3 to be used as a matched\-time reference for DiffLNS in SR and SOC\. Since this protocol differs from the fixed\-budget setting, LaCAM3 is not directly compared with the other fixed\-budget methods, and its runtime is omitted from the runtime comparison\.

#### Benchmark statistics\.

All evaluation instances are randomly generated with POGEMA\(Skrynnik et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib26)\)555[https://github\.com/CognitiveAISystems/pogema](https://github.com/CognitiveAISystems/pogema)\. Example test maps from the evaluated benchmark families are shown in Fig\.[7](https://arxiv.org/html/2605.13296#A3.F7)\. The reported agent densities are computed with respect to free cells, i\.e\., as the ratio between the number of agents and the number of non\-obstacle cells\. The instance counts shown in Table[2](https://arxiv.org/html/2605.13296#A3.T2)are the actual numbers of evaluated MAPF instances for each agent cardinality\. The listed time limits correspond to the fixed\-budget methods, namely DiffLNS,LNS2,LNS2\+RL, andHMAGAT\. LaCAM3 is excluded from this table because it is evaluated under matched per\-instance budgets determined by the runtime of DiffLNS on the same instance\.

![Refer to caption](https://arxiv.org/html/2605.13296v1/x7.png)Figure 7:Example test maps generated with POGEMA for the evaluated benchmark families\. These maps illustrate the obstacle layouts and structural differences across the random, maze, room, and warehouse environments used in our experiments\.Table 1:Benchmark families used in the main experiments\. Obstacle\-density ranges are measured from the generated benchmark instances\.Table 2:Evaluation budgets for the main experiments\. Levels 1–4 correspond to the four agent cardinalities listed in Table[1](https://arxiv.org/html/2605.13296#A3.T1), from low to high density\. Each entry reports the number of cases and the corresponding time limit\. The listed time limits apply to the fixed\-budget methods \(DiffLNS,LNS2,LNS2\+RL, andHMAGAT\)\.

### C\.2Candidate Generation Statistics

Table[3](https://arxiv.org/html/2605.13296#A3.T3)reports the average number of generated candidates used by DiffLNS under the iterative inference strategy\. As agent density and coordination difficulty increase, DiffLNS typically needs more candidate generations to obtain a feasible repaired solution, which accounts for part of the runtime increase observed in the main results\.

Table 3:Average number of generated candidates used by DiffLNS\. For each scenario family, Levels 1–4 denote increasing agent density\.Table 4:Complete main experiment results\. Higher success rate is better, while lower SOC and runtime are better\. The symbols↑\\uparrowand↓\\downarrowindicate that larger and smaller values are better, respectively\. Agent density is computed as the ratio between the number of agents and the number of free cells, i\.e\., non\-obstacle cells\. For DiffLNS, LNS2, LNS2\+RL, and HMAGAT, runtime is averaged over all evaluated instances using the actual elapsed time of each run, including failed runs\. HMAGAT terminates when either the wall\-clock limit or the 512\-step episode limit is reached\. The evaluation time limits are shown in parentheses in the runtime headers for each scene and agent cardinality\. For LaCAM3, runtime is omitted because LaCAM3 is evaluated under per\-instance budgets matched to DiffLNS\.

### C\.3Additional Observations on Main Results

Table[4](https://arxiv.org/html/2605.13296#A3.T4)provides the complete scene\-by\-scene numerical results underlying Fig\.[3](https://arxiv.org/html/2605.13296#S4.F3)\. Beyond the main observations in the paper, several additional patterns are worth noting\.

#### DiffLNS\.

The most prominent strength of DiffLNS is its consistently high success rate across all evaluated settings\. In most scene families and agent cardinality levels, it matches or exceeds all compared methods in success rate\. The advantage is especially pronounced in*Medium Maze*,*Medium Warehouse*, and*Large Maze*, where DiffLNS maintains nearly perfect success rates even under very dense and highly congested conditions\. This result suggests that the learned initializer is particularly effective in scenarios where global coordination and repair quality are the dominant bottlenecks\.

In terms of solution quality, DiffLNS usually obtains slightly higher SOC than LNS2, which is expected because LNS2 is a strong classical solver optimized for cost efficiency on successful instances\. Nevertheless, DiffLNS still achieves competitive SOC in most settings and does not substantially sacrifice solution quality in exchange for improved feasibility\. Taken together, these results indicate a favorable balance between robustness and cost\.

Regarding runtime, DiffLNS is generally slower than the compared baselines because each instance requires both diffusion\-based generation and downstream LNS2 repair\. This overhead is discussed in the main experimental section and in the limitations section, and it represents the main computational trade\-off of the proposed framework\.

#### LNS2\.

LNS2 remains a strong classical baseline, especially in solution quality and runtime\. Across many settings, it attains the lowest or near\-lowest SOC and is often among the fastest fixed\-budget methods\. However, its success rate drops substantially as environments become more crowded\. This trade\-off is particularly visible in*Medium Maze*,*Medium Room*,*Medium Warehouse*, and*Large Maze*, where LNS2 can remain efficient on solved instances but fails to retain the same level of robustness as DiffLNS\.

#### LNS2\+RL\.

LNS2\+RLgenerally improves the success rate ofLNS2in harder settings, indicating that learning\-guided repair provides a meaningful robustness gain\. This is especially evident in the denser maze and warehouse settings, whereLNS2\+RLnarrows part of the feasibility gap to DiffLNS\. In our experiments, we adopt the best\-performing hyperparameter setting reported in the originalLNS2\+RLpaper, namely neighborhood size88, switch thresholdρ=0\.3\\rho=0\.3, stop\-MARL\-planning thresholdtl=1\.2t\_\{l\}=1\.2, and maximum lengthth=2\.2t\_\{h\}=2\.2\. However, the gain in success rate usually comes at the cost of higher SOC thanLNS2, andLNS2\+RLstill does not match the strongest success\-rate performance of DiffLNS in the most challenging settings\. In this sense,LNS2\+RLcan be viewed as a more robust but less cost\-efficient variant ofLNS2\. More importantly, sinceLNS2\+RLimproves the repair stage whereas DiffLNS improves the initialization stage, the two directions are largely complementary rather than mutually exclusive\. This suggests that combining a stronger learned initializer with a stronger learned repair policy is a promising direction for further improving success rates in highly congested MAPF settings\.

#### HMAGAT\.

HMAGATshows a different profile from the LNS\-based methods\. It is relatively stable and fast in the room and warehouse families, suggesting that its learned policy captures useful regularity in structured indoor layouts\. However,HMAGATalso exhibits the highest SOC in nearly all scene families and struggles more severely in maze\-like environments, especially*Large Maze*\. Its runtime should also be interpreted with its maximum episode length of 512 steps: in hard instances, unfinished rollouts can terminate early after reaching this limit, which partly explains the lower average runtime\. Thus, the strength ofHMAGATlies more in maintaining a usable success rate in some structured layouts than in producing low\-cost solutions\.

#### LaCAM3\.

LaCAM3 should be interpreted separately from the other baselines because it is evaluated under matched per\-instance budgets rather than the fixed\-budget protocol\. Under this matched\-time setting, it remains competitive on several easier or medium\-difficulty settings and can still achieve favorable SOC on the solved subset\. However, its success rate degrades much more rapidly in dense and difficult regimes, especially in*Large Maze*and the hardest*Medium Warehouse*settings\. These results suggest that although LaCAM3 remains a strong classical anytime solver, the matched\-time comparison still favors DiffLNS in highly congested instances where feasible planning under a limited per\-instance runtime becomes difficult\.

## Appendix DTraining and Denoising Network Details

This appendix provides implementation details that are omitted from the main text, including expert\-data construction, the MAPF\-conditioned denoising network, the exact supervised losses, the training schedule, and optimization hyperparameters\. The main text defines the high\-level DiffLNS framework and the generative objective; here we give the concrete choices used in our experiments\.

### D\.1Training Data and Distributed Setup

Training data are constructed from procedurally generated POGEMA\(Skrynnik et al\.,[2025](https://arxiv.org/html/2605.13296#bib.bib26)\)MAPF instances\. We use three scene families: maze, room, and warehouse\. All training maps have size23×2323\\times 23, and the dataset contains three agent cardinalities,N∈\{32,64,96\}N\\in\\\{32,64,96\\\}\. The dataset is evenly split across the three scene types and contains 4\.5K instances with 32 agents, 9K instances with 64 agents, and 9K instances with 96 agents\. For each instance, start and goal locations are randomly generated, and obstacle densities are sampled to produce diverse MAPF configurations\. We solve these instances with LaCAM3\(Okumura,[2024](https://arxiv.org/html/2605.13296#bib.bib19)\)and retain only successful rollouts as expert demonstrations\.

To preserve a fixed team size within each mini\-batch while training a shared denoiser across different agent counts, we use a round\-robin dataset mixing strategy: each mini\-batch is sampled from one fixed\-NNsubset, and the three subsets are alternated throughout each epoch\. The per\-GPU batch size is 8\.

Training is performed with distributed data parallelism on a single node with 8 NVIDIA A100 GPUs\. The total training procedure takes approximately 26 hours for 400 epochs\. Random seeds are fixed to 42 for both PyTorch and NumPy\. Mixed\-precision training is enabled with BF16 autocasting, and activation checkpointing is used to reduce peak memory usage during backbone training\.

### D\.2Model and Diffusion Configuration

The denoising network implements the conditional clean\-state predictorp~θ​\(𝐱0∣𝐱k,𝐜\)\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)used by thex0x\_\{0\}\-parameterized D3PM reverse process\. It follows the general design paradigm of diffusion transformers by using a timestep\-conditioned transformer\-style backbone for denoising, but is specialized for MAPF rather than being a direct DiT architecture\(Peebles and Xie,[2023](https://arxiv.org/html/2605.13296#bib.bib20)\)\. In particular, it operates on structured agent\-time action tokens and factorizes denoising into temporal attention, diffusion\-aware sparse social attention, and trajectory\-conditioned environment sensing\.

Given a noisy joint action tensor𝐱k∈\[0,1\]N×T×C\\mathbf\{x\}\_\{k\}\\in\[0,1\]^\{N\\times T\\times C\}, whereC=5C=5corresponds tostay,up,down,left, andright, the network outputs action logitsfθ​\(𝐱k,𝐜,k\)∈ℝN×T×Cf\_\{\\theta\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{c\},k\)\\in\\mathbb\{R\}^\{N\\times T\\times C\}\. The predicted clean distribution is

p~θ​\(𝐱0∣𝐱k,𝐜\)=∏i=1N∏τ=1TCat​\(𝐱0,i,τ,:;softmax​\(fθ​\(𝐱k,𝐜,k\)i,τ,:\)\)\.\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)=\\prod\_\{i=1\}^\{N\}\\prod\_\{\\tau=1\}^\{T\}\\mathrm\{Cat\}\\\!\\left\(\\mathbf\{x\}\_\{0,i,\\tau,:\};\\mathrm\{softmax\}\\\!\\left\(f\_\{\\theta\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{c\},k\)\_\{i,\\tau,:\}\\right\)\\right\)\.\(11\)We useK=100K=100diffusion steps with a cosine noise schedule\(Nichol and Dhariwal,[2021](https://arxiv.org/html/2605.13296#bib.bib17)\)\. During training, the diffusion step is sampled uniformly ask∼𝒰​\{1,…,K\}k\\sim\\mathcal\{U\}\\\{1,\\ldots,K\\\}\.

#### Uniform forward transition matrix\.

We use the standard uniform transition kernel from the D3PM family\(Austin et al\.,[2021](https://arxiv.org/html/2605.13296#bib.bib2)\):

𝐐k=αk​𝐈\+\(1−αk\)​1C​𝟏𝟏⊤\.\\mathbf\{Q\}\_\{k\}=\\alpha\_\{k\}\\mathbf\{I\}\+\(1\-\\alpha\_\{k\}\)\\frac\{1\}\{C\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\.\(12\)Hereαk\\alpha\_\{k\}preserves the current action with probabilityαk\\alpha\_\{k\}and redistributes the remaining mass uniformly over theCCaction classes\. This choice is natural for MAPF because the action space is discrete and unordered, with no meaningful notion of distance between action classes\. As the diffusion step increases, each action is therefore gradually mixed toward a uniform categorical distribution\.

#### Condition encoding\.

The MAPF condition𝐜\\mathbf\{c\}contains the obstacle map, goal map, start and goal locations, map size, and a global density feature\. Let the grid map have widthWWand heightHH, and denote the map\-size vector by𝐦=\(W,H\)\\mathbf\{m\}=\(W,H\)\. LetVfree=\{\(u,v\):Gu,v=0\}V\_\{\\mathrm\{free\}\}=\\\{\(u,v\):G\_\{u,v\}=0\\\}denote the set of traversable cells, whereGu,v=0G\_\{u,v\}=0indicates a free cell andGu,v=1G\_\{u,v\}=1indicates an obstacle\. Start and goal locations are represented in normalized map coordinates,𝐬i,𝐠i∈\[−1,1\]2\\mathbf\{s\}\_\{i\},\\mathbf\{g\}\_\{i\}\\in\[\-1,1\]^\{2\}\. The global agent\-density feature is

ρ=log⁡\(1\+N\|Vfree\|\)\.\\rho=\\log\\\!\\left\(1\+\\frac\{N\}\{\|V\_\{\\mathrm\{free\}\}\|\}\\right\)\.\(13\)The diffusion step is encoded by a sinusoidal embeddingPE​\(k\)\\mathrm\{PE\}\(k\)\(Vaswani et al\.,[2017](https://arxiv.org/html/2605.13296#bib.bib29)\)\. The global condition is computed as

𝐜g=ψg​\(\[ϕk​\(PE​\(k\)\),ϕm​\(log⁡𝐦\)\+ϕρ​\(ρ\)\]\),\\mathbf\{c\}\_\{\\mathrm\{g\}\}=\\psi\_\{\\mathrm\{g\}\}\\left\(\\left\[\\phi\_\{k\}\(\\mathrm\{PE\}\(k\)\),\\;\\phi\_\{m\}\(\\log\\mathbf\{m\}\)\+\\phi\_\{\\rho\}\(\\rho\)\\right\]\\right\),\(14\)whereϕk\\phi\_\{k\},ϕm\\phi\_\{m\},ϕρ\\phi\_\{\\rho\}, andψg\\psi\_\{\\mathrm\{g\}\}are learned projections\. For each agent, the agent\-wise condition is

𝐜i=ψn​\(\[𝐜g,ϕs​\(𝐬i\),ϕg​\(𝐠i\),ϕr​\(𝐠i−𝐬i\)\]\)\.\\mathbf\{c\}\_\{i\}=\\psi\_\{\\mathrm\{n\}\}\\left\(\\left\[\\mathbf\{c\}\_\{\\mathrm\{g\}\},\\phi\_\{s\}\(\\mathbf\{s\}\_\{i\}\),\\phi\_\{g\}\(\\mathbf\{g\}\_\{i\}\),\\phi\_\{r\}\(\\mathbf\{g\}\_\{i\}\-\\mathbf\{s\}\_\{i\}\)\\right\]\\right\)\.\(15\)The global condition also predicts a scale gate for the map pyramid, later used to weight multi\-scale map features in Eq\. \([31](https://arxiv.org/html/2605.13296#A4.E31)\):

𝜼=softmax​\(ψscale​\(𝐜g\)\),𝜼∈ℝS\.\\boldsymbol\{\\eta\}=\\mathrm\{softmax\}\\\!\\left\(\\psi\_\{\\mathrm\{scale\}\}\(\\mathbf\{c\}\_\{\\mathrm\{g\}\}\)\\right\),\\qquad\\boldsymbol\{\\eta\}\\in\\mathbb\{R\}^\{S\}\.\(16\)

#### Initial denoising tokens\.

The network first embeds each noisy action distribution and adds start, goal, and relative\-goal embeddings\. The initial denoising token for agentiiat timestepτ\\tauis

𝐱i,τ\(0\)=ϕa​\(𝐱k,i,τ,:\)\+ϕs​\(𝐬i\)\+ϕg​\(𝐠i\)\+ϕr​\(𝐠i−𝐬i\),𝐱i,τ\(0\)∈ℝD\.\\mathbf\{x\}^\{\(0\)\}\_\{i,\\tau\}=\\phi\_\{a\}\(\\mathbf\{x\}\_\{k,i,\\tau,:\}\)\+\\phi\_\{s\}\(\\mathbf\{s\}\_\{i\}\)\+\\phi\_\{g\}\(\\mathbf\{g\}\_\{i\}\)\+\\phi\_\{r\}\(\\mathbf\{g\}\_\{i\}\-\\mathbf\{s\}\_\{i\}\),\\qquad\\mathbf\{x\}^\{\(0\)\}\_\{i,\\tau\}\\in\\mathbb\{R\}^\{D\}\.\(17\)Here the superscript in𝐱\(ℓ\)\\mathbf\{x\}^\{\(\\ell\)\}denotes the denoising\-network layer index, while the subscriptkkin𝐱k\\mathbf\{x\}\_\{k\}denotes the diffusion step\.

#### Environment feature pyramid\.

The environment input is a three\-channel map containing obstacle cells, free cells, and goal cells\. A lightweight convolutional pyramid produces multi\-scale feature maps

\{𝐅\(s\)\}s=1S=Emap​\(𝐆;𝐜g\),𝐅\(s\)∈ℝD×Hs×Ws\.\\\{\\mathbf\{F\}^\{\(s\)\}\\\}\_\{s=1\}^\{S\}=E\_\{\\mathrm\{map\}\}\(\\mathbf\{G\};\\mathbf\{c\}\_\{\\mathrm\{g\}\}\),\\qquad\\mathbf\{F\}^\{\(s\)\}\\in\\mathbb\{R\}^\{D\\times H\_\{s\}\\times W\_\{s\}\}\.\(18\)Each convolutional stage is modulated by the global condition through FiLM\(Perez et al\.,[2017](https://arxiv.org/html/2605.13296#bib.bib21)\):

FiLM​\(𝐅;𝐜g\)=\(1\+𝜸​\(𝐜g\)\)⊙𝐅\+𝜷​\(𝐜g\)\.\\mathrm\{FiLM\}\(\\mathbf\{F\};\\mathbf\{c\}\_\{\\mathrm\{g\}\}\)=\\left\(1\+\\boldsymbol\{\\gamma\}\(\\mathbf\{c\}\_\{\\mathrm\{g\}\}\)\\right\)\\odot\\mathbf\{F\}\+\\boldsymbol\{\\beta\}\(\\mathbf\{c\}\_\{\\mathrm\{g\}\}\)\.\(19\)The pyramid uses two strided downsampling stages and a partial upsampling path, and each scale is projected to the hidden dimensionDD\.

#### Inferred trajectory and sparse social graph\.

At every diffusion step, the network constructs a soft inferred trajectory from the current noisy action distribution\. This trajectory is used only as an internal continuous estimate for interaction modeling and map\-feature sampling, rather than as a discrete MAPF path\. LetΔ​\(a\)∈ℝ2\\Delta\(a\)\\in\\mathbb\{R\}^\{2\}be the grid displacement of actionaain row\-column coordinates\. The expected displacement is

Δ¯i,τ=∑a=1C𝐱k,i,τ,a​Δ​\(a\)\.\\bar\{\\Delta\}\_\{i,\\tau\}=\\sum\_\{a=1\}^\{C\}\\mathbf\{x\}\_\{k,i,\\tau,a\}\\Delta\(a\)\.\(20\)Since start locations are represented in normalized coordinates, the expected grid displacement is rescaled by the map size before accumulation\. The soft inferred position is then

𝐩i,τinf=𝐬i\+∑u=1τNorm𝐦​\(Δ¯i,u\),\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}=\\mathbf\{s\}\_\{i\}\+\\sum\_\{u=1\}^\{\\tau\}\\mathrm\{Norm\}\_\{\\mathbf\{m\}\}\\\!\\left\(\\bar\{\\Delta\}\_\{i,u\}\\right\),\(21\)whereNorm𝐦​\(⋅\)\\mathrm\{Norm\}\_\{\\mathbf\{m\}\}\(\\cdot\)converts row\-column grid displacement into the normalized coordinate system according to the map size𝐦=\(W,H\)\\mathbf\{m\}=\(W,H\)\.

The uncertainty of each action distribution is measured by the normalized entropy and is later used to enlarge the environment\-sensing radius in Eq\. \([30](https://arxiv.org/html/2605.13296#A4.E30)\):

ei,τ=−1log⁡C​∑a=1C𝐱k,i,τ,a​log⁡𝐱k,i,τ,a\.e\_\{i,\\tau\}=\-\\frac\{1\}\{\\log C\}\\sum\_\{a=1\}^\{C\}\\mathbf\{x\}\_\{k,i,\\tau,a\}\\log\\mathbf\{x\}\_\{k,i,\\tau,a\}\.\(22\)
The sparse social graph is constructed from these soft inferred trajectories\. For each pair of agents, we compute their minimum inferred\-trajectory distance:

di​j=minτ=1,…,T⁡‖𝐩i,τinf−𝐩j,τinf‖1\.d\_\{ij\}=\\min\_\{\\tau=1,\\ldots,T\}\\left\\\|\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}\-\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{j,\\tau\}\\right\\\|\_\{1\}\.\(23\)LetMkM\_\{k\}be a clipped top\-kkneighbor count that increases with the noise level, with the non\-self neighbor ratio scheduled from0\.100\.10to0\.250\.25\. For each agentii,𝒩k​\(i\)\\mathcal\{N\}\_\{k\}\(i\)contains agentiiitself and theMkM\_\{k\}nearest non\-self agents according todi​jd\_\{ij\}\. Invalid or padded neighbors are masked before the attention softmax\.

#### Interaction backbone\.

The backbone consists ofL=4L=4interaction blocks\. Each block contains temporal attention, sparse social attention, deformable environment sensing, and a feed\-forward network\. Adaptive layer normalization uses the agent\-wise condition:

AdaLN​\(𝐱i,τ;𝐜i\)=\(1\+𝜸i\)⊙LN​\(𝐱i,τ\)\+𝜷i,\[𝜸i,𝜷i\]=ψada​\(𝐜i\)\.\\mathrm\{AdaLN\}\(\\mathbf\{x\}\_\{i,\\tau\};\\mathbf\{c\}\_\{i\}\)=\\left\(1\+\\boldsymbol\{\\gamma\}\_\{i\}\\right\)\\odot\\mathrm\{LN\}\(\\mathbf\{x\}\_\{i,\\tau\}\)\+\\boldsymbol\{\\beta\}\_\{i\},\\qquad\[\\boldsymbol\{\\gamma\}\_\{i\},\\boldsymbol\{\\beta\}\_\{i\}\]=\\psi\_\{\\mathrm\{ada\}\}\(\\mathbf\{c\}\_\{i\}\)\.\(24\)For blockℓ\\ell, the residual updates are

𝐱\(ℓ,1\)\\displaystyle\\mathbf\{x\}^\{\(\\ell,1\)\}=𝐱\(ℓ\)\+TempAttn​\(AdaLN​\(𝐱\(ℓ\),𝐜\)\),\\displaystyle=\\mathbf\{x\}^\{\(\\ell\)\}\+\\mathrm\{TempAttn\}\\left\(\\mathrm\{AdaLN\}\(\\mathbf\{x\}^\{\(\\ell\)\},\\mathbf\{c\}\)\\right\),\(25\)𝐱\(ℓ,2\)\\displaystyle\\mathbf\{x\}^\{\(\\ell,2\)\}=𝐱\(ℓ,1\)\+SocialAttn​\(AdaLN​\(𝐱\(ℓ,1\),𝐜\),𝐩inf,𝒩k\),\\displaystyle=\\mathbf\{x\}^\{\(\\ell,1\)\}\+\\mathrm\{SocialAttn\}\\left\(\\mathrm\{AdaLN\}\(\\mathbf\{x\}^\{\(\\ell,1\)\},\\mathbf\{c\}\),\\mathbf\{p\}^\{\\mathrm\{inf\}\},\\mathcal\{N\}\_\{k\}\\right\),𝐱\(ℓ,3\)\\displaystyle\\mathbf\{x\}^\{\(\\ell,3\)\}=𝐱\(ℓ,2\)\+EnvSense​\(AdaLN​\(𝐱\(ℓ,2\),𝐜\),𝐩inf,𝐞,\{𝐅\(s\)\}s=1S,𝜼\),\\displaystyle=\\mathbf\{x\}^\{\(\\ell,2\)\}\+\\mathrm\{EnvSense\}\\left\(\\mathrm\{AdaLN\}\(\\mathbf\{x\}^\{\(\\ell,2\)\},\\mathbf\{c\}\),\\mathbf\{p\}^\{\\mathrm\{inf\}\},\\mathbf\{e\},\\\{\\mathbf\{F\}^\{\(s\)\}\\\}\_\{s=1\}^\{S\},\\boldsymbol\{\\eta\}\\right\),𝐱\(ℓ\+1\)\\displaystyle\\mathbf\{x\}^\{\(\\ell\+1\)\}=𝐱\(ℓ,3\)\+FFN​\(AdaLN​\(𝐱\(ℓ,3\),𝐜\)\)\.\\displaystyle=\\mathbf\{x\}^\{\(\\ell,3\)\}\+\\mathrm\{FFN\}\\left\(\\mathrm\{AdaLN\}\(\\mathbf\{x\}^\{\(\\ell,3\)\},\\mathbf\{c\}\)\\right\)\.Here𝐩inf\\mathbf\{p\}^\{\\mathrm\{inf\}\}and𝐞\\mathbf\{e\}denote the soft inferred positions and normalized action entropies defined above\.

The temporal attention module is applied independently to each agent trajectory\. For agentii, it treats\{𝐱i,τ\}τ=1T\\\{\\mathbf\{x\}\_\{i,\\tau\}\\\}\_\{\\tau=1\}^\{T\}as a temporal token sequence and performs self\-attention along the time dimension\. Local window attention restricts each timestepτ\\tauto attend only to tokensu∈𝒲​\(τ\)u\\in\\mathcal\{W\}\(\\tau\)within the same window of sizeWt=32W\_\{t\}=32:

TempAttnlocal​\(𝐱i,τ\)=∑u∈𝒲​\(τ\)softmaxu​\(𝐪i,τ⊤​𝐤i,ud\)​𝐯i,u\.\\mathrm\{TempAttn\}\_\{\\mathrm\{local\}\}\(\\mathbf\{x\}\_\{i,\\tau\}\)=\\sum\_\{u\\in\\mathcal\{W\}\(\\tau\)\}\\mathrm\{softmax\}\_\{u\}\\left\(\\frac\{\\mathbf\{q\}\_\{i,\\tau\}^\{\\top\}\\mathbf\{k\}\_\{i,u\}\}\{\\sqrt\{d\}\}\\right\)\\mathbf\{v\}\_\{i,u\}\.\(26\)The module additionally uses sparse global attention over temporal anchors sampled everySt=16S\_\{t\}=16timesteps, allowing each token to receive coarse long\-range context without full attention over allTTtimesteps\.

The sparse social attention module operates at each timestep over the dynamic neighborhood𝒩k​\(i\)\\mathcal\{N\}\_\{k\}\(i\)\. Let𝐪i,τ\\mathbf\{q\}\_\{i,\\tau\},𝐤j,τ\\mathbf\{k\}\_\{j,\\tau\}, and𝐯j,τ\\mathbf\{v\}\_\{j,\\tau\}be the query, key, and value projections\. The attention weights are

αi​j,τ=softmaxj∈𝒩k​\(i\)​\(𝐪i,τ⊤​𝐤j,τd\+bθ​\(𝐩i,τinf−𝐩j,τinf\)\),\\alpha\_\{ij,\\tau\}=\\mathrm\{softmax\}\_\{j\\in\\mathcal\{N\}\_\{k\}\(i\)\}\\left\(\\frac\{\\mathbf\{q\}\_\{i,\\tau\}^\{\\top\}\\mathbf\{k\}\_\{j,\\tau\}\}\{\\sqrt\{d\}\}\+b\_\{\\theta\}\\left\(\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}\-\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{j,\\tau\}\\right\)\\right\),\(27\)wherebθ​\(⋅\)b\_\{\\theta\}\(\\cdot\)is a learned geometric bias from relative inferred positions\. The social update is

SocialAttni,τ=∑j∈𝒩k​\(i\)αi​j,τ​𝐯j,τ\.\\mathrm\{SocialAttn\}\_\{i,\\tau\}=\\sum\_\{j\\in\\mathcal\{N\}\_\{k\}\(i\)\}\\alpha\_\{ij,\\tau\}\\mathbf\{v\}\_\{j,\\tau\}\.\(28\)
The environment\-sensing module samples map features around the inferred trajectory\. Lets=1,…,Ss=1,\\ldots,Sindex the map\-pyramid level andp=1,…,Pp=1,\\ldots,Pindex the sampling point\. For each agentiiand timestepτ\\tau, the module predicts a sampling offset𝜹i,τp\\boldsymbol\{\\delta\}^\{p\}\_\{i,\\tau\}and an attention weightωi,τs,p\\omega^\{s,p\}\_\{i,\\tau\}over scale\-point pairs:

𝜹i,τp=tanh⁡\(Wδp​𝐱i,τ\),ωi,τs,p=softmaxs,p​\(Wωs,p​𝐱i,τ\)\.\\boldsymbol\{\\delta\}^\{p\}\_\{i,\\tau\}=\\tanh\\\!\\left\(W\_\{\\delta\}^\{p\}\\mathbf\{x\}\_\{i,\\tau\}\\right\),\\qquad\\omega^\{s,p\}\_\{i,\\tau\}=\\mathrm\{softmax\}\_\{s,p\}\\left\(W\_\{\\omega\}^\{s,p\}\\mathbf\{x\}\_\{i,\\tau\}\\right\)\.\(29\)The sampling location𝐮i,τp\\mathbf\{u\}^\{p\}\_\{i,\\tau\}is centered at the inferred position𝐩i,τinf\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}and expanded according to the action\-distribution entropy:

𝐮i,τp=𝐩i,τinf\+r0​\(1\+0\.2​ei,τ\)​𝜹i,τp,\\mathbf\{u\}^\{p\}\_\{i,\\tau\}=\\mathbf\{p\}^\{\\mathrm\{inf\}\}\_\{i,\\tau\}\+r\_\{0\}\(1\+0\.2e\_\{i,\\tau\}\)\\boldsymbol\{\\delta\}^\{p\}\_\{i,\\tau\},\(30\)wherer0r\_\{0\}is a learned base radius andei,τe\_\{i,\\tau\}is the normalized entropy defined in Eq\. \([22](https://arxiv.org/html/2605.13296#A4.E22)\)\. With bilinear interpolationℬ​\(𝐅\(s\),𝐮\)\\mathcal\{B\}\(\\mathbf\{F\}^\{\(s\)\},\\mathbf\{u\}\)on thess\-th map feature𝐅\(s\)\\mathbf\{F\}^\{\(s\)\}, the environment context is

𝐳i,τ=∑s=1S∑p=1Pωi,τs,p​ηs​ℬ​\(𝐅\(s\),𝐮i,τp\),\\mathbf\{z\}\_\{i,\\tau\}=\\sum\_\{s=1\}^\{S\}\\sum\_\{p=1\}^\{P\}\\omega^\{s,p\}\_\{i,\\tau\}\\,\\eta\_\{s\}\\,\\mathcal\{B\}\\\!\\left\(\\mathbf\{F\}^\{\(s\)\},\\mathbf\{u\}^\{p\}\_\{i,\\tau\}\\right\),\(31\)whereηs\\eta\_\{s\}is the scale\-gate weight from Eq\. \([16](https://arxiv.org/html/2605.13296#A4.E16)\)\. The resulting context𝐳i,τ\\mathbf\{z\}\_\{i,\\tau\}is projected back to dimensionDDto form the residual environment\-sensing update used in Eq\. \([25](https://arxiv.org/html/2605.13296#A4.E25)\)\.

#### Output head\.

After the final interaction block, the network normalizes the denoising tokens and maps each token to action logits through a linear output head:

ℓi,τ,:=Linearout​\(LN​\(𝐱i,τ\(L\)\)\)∈ℝC\.\\boldsymbol\{\\ell\}\_\{i,\\tau,:\}=\\mathrm\{Linear\}\_\{\\mathrm\{out\}\}\\left\(\\mathrm\{LN\}\\\!\\left\(\\mathbf\{x\}^\{\(L\)\}\_\{i,\\tau\}\\right\)\\right\)\\in\\mathbb\{R\}^\{C\}\.\(32\)Collecting all agents and timesteps givesfθ​\(𝐱k,𝐜,k\)∈ℝN×T×Cf\_\{\\theta\}\(\\mathbf\{x\}\_\{k\},\\mathbf\{c\},k\)\\in\\mathbb\{R\}^\{N\\times T\\times C\}\. The clean\-action probability vector is obtained by normalizing the logits over the action dimension:

𝐱^0,i,τ,:=softmax​\(ℓi,τ,:\)\.\\hat\{\\mathbf\{x\}\}\_\{0,i,\\tau,:\}=\\mathrm\{softmax\}\\\!\\left\(\\boldsymbol\{\\ell\}\_\{i,\\tau,:\}\\right\)\.\(33\)These probability vectors parameterize the factorized clean\-state distribution predicted by the denoiser:

p~θ​\(𝐱0∣𝐱k,𝐜\)=∏i=1N∏τ=1TCat​\(𝐱0,i,τ,:;𝐱^0,i,τ,:\),\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)=\\prod\_\{i=1\}^\{N\}\\prod\_\{\\tau=1\}^\{T\}\\mathrm\{Cat\}\\\!\\left\(\\mathbf\{x\}\_\{0,i,\\tau,:\};\\hat\{\\mathbf\{x\}\}\_\{0,i,\\tau,:\}\\right\),\(34\)which is then used to construct the D3PM reverse transitionpθ​\(𝐱k−1∣𝐱k,𝐜\)p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)\.

### D\.3Training Objective

For completeness, the generic D3PM variational term referenced in Eq\. \([3](https://arxiv.org/html/2605.13296#S2.E3)\) decomposes as

ℒvb=𝔼q​\(𝐱0\)\[\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{vb\}\}=\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{0\}\)\}\\Big\[KL\(q\(𝐱K∣𝐱0\)∥p\(𝐱K\)\)\+∑k=2K𝔼q​\(𝐱k∣𝐱0\)\[KL\(q\(𝐱k−1∣𝐱k,𝐱0\)∥pθ\(𝐱k−1∣𝐱k\)\)\]\\displaystyle\\mathrm\{KL\}\\\!\\left\(q\(\\mathbf\{x\}\_\{K\}\\mid\\mathbf\{x\}\_\{0\}\)\\,\\\|\\,p\(\\mathbf\{x\}\_\{K\}\)\\right\)\+\\sum\_\{k=2\}^\{K\}\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\left\[\\mathrm\{KL\}\\\!\\left\(q\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{x\}\_\{0\}\)\\,\\\|\\,p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\}\)\\right\)\\right\]\(35\)−𝔼q​\(𝐱1∣𝐱0\)\[logpθ\(𝐱0∣𝐱1\)\]\]\.\\displaystyle\-\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{1\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\left\[\\log p\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{1\}\)\\right\]\\Big\]\.In the conditional MAPF setting, letq​\(𝐱0,𝐜\)q\(\\mathbf\{x\}\_\{0\},\\mathbf\{c\}\)denote the expert data distribution over clean joint action tensors and MAPF conditions\. Our main text uses the generative objective

ℒgen=ℒaux\+λKL​ℒKL,\\mathcal\{L\}\_\{\\mathrm\{gen\}\}=\\mathcal\{L\}\_\{\\mathrm\{aux\}\}\+\\lambda\_\{\\mathrm\{KL\}\}\\mathcal\{L\}\_\{\\mathrm\{KL\}\},\(36\)whereℒaux\\mathcal\{L\}\_\{\\mathrm\{aux\}\}is the auxiliary clean\-state prediction term in Eq\. \([3](https://arxiv.org/html/2605.13296#S2.E3)\), andℒKL\\mathcal\{L\}\_\{\\mathrm\{KL\}\}is the posterior\-matching component extracted from the variational termℒvb\\mathcal\{L\}\_\{\\mathrm\{vb\}\}\. Instead of evaluating the full variational decomposition, we keep the intermediate KL term that aligns the learned reverse transition with the analytic discrete posterior:

ℒKL=𝔼q​\(𝐱0,𝐜\)𝔼k∼Unif​\(\{1,…,K\}\)𝔼q​\(𝐱k∣𝐱0\)\[KL\(q\(𝐱k−1∣𝐱k,𝐱0\)∥pθ\(𝐱k−1∣𝐱k,𝐜\)\)\]\.\\mathcal\{L\}\_\{\\mathrm\{KL\}\}=\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{0\},\\mathbf\{c\}\)\}\\mathbb\{E\}\_\{k\\sim\\mathrm\{Unif\}\(\\\{1,\\ldots,K\\\}\)\}\\mathbb\{E\}\_\{q\(\\mathbf\{x\}\_\{k\}\\mid\\mathbf\{x\}\_\{0\}\)\}\\left\[\\mathrm\{KL\}\\\!\\left\(q\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{x\}\_\{0\}\)\\,\\\|\\,p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)\\right\)\\right\]\.\(37\)Under the𝐱0\\mathbf\{x\}\_\{0\}\-parameterization,pθ​\(𝐱k−1∣𝐱k,𝐜\)p\_\{\\theta\}\(\\mathbf\{x\}\_\{k\-1\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)is induced by the predicted clean\-state distributionp~θ​\(𝐱0∣𝐱k,𝐜\)\\tilde\{p\}\_\{\\theta\}\(\\mathbf\{x\}\_\{0\}\\mid\\mathbf\{x\}\_\{k\},\\mathbf\{c\}\)through the analytic D3PM posterior, as in Eq\. \([2](https://arxiv.org/html/2605.13296#S2.E2)\)\.

We further add the task\-oriented auxiliary objective used in the main text:

ℒ=ℒgen\+ℒtask,\\mathcal\{L\}=\\mathcal\{L\}\_\{\\mathrm\{gen\}\}\+\\mathcal\{L\}\_\{\\mathrm\{task\}\},\(38\)with

ℒtask=λgoal​ℒgoal\+λvertex​ℒvertex\+λedge​ℒedge\+λvalid​ℒvalid\.\\mathcal\{L\}\_\{\\mathrm\{task\}\}=\\lambda\_\{\\mathrm\{goal\}\}\\mathcal\{L\}\_\{\\mathrm\{goal\}\}\+\\lambda\_\{\\mathrm\{vertex\}\}\\mathcal\{L\}\_\{\\mathrm\{vertex\}\}\+\\lambda\_\{\\mathrm\{edge\}\}\\mathcal\{L\}\_\{\\mathrm\{edge\}\}\+\\lambda\_\{\\mathrm\{valid\}\}\\mathcal\{L\}\_\{\\mathrm\{valid\}\}\.\(39\)The default weights are

λKL=0\.02,λgoal=0\.4,λvertex=0\.2,λedge=0\.2,λvalid=0\.4\.\\lambda\_\{\\mathrm\{KL\}\}=0\.02,\\quad\\lambda\_\{\\mathrm\{goal\}\}=0\.4,\\quad\\lambda\_\{\\mathrm\{vertex\}\}=0\.2,\\quad\\lambda\_\{\\mathrm\{edge\}\}=0\.2,\\quad\\lambda\_\{\\mathrm\{valid\}\}=0\.4\.The task losses are computed from the predicted clean\-action distribution𝐱^0\\hat\{\\mathbf\{x\}\}\_\{0\}through its induced soft trajectory, rather than from samples generated by the full reverse diffusion process\. Therefore,ℒtask\\mathcal\{L\}\_\{\\mathrm\{task\}\}serves as an auxiliary shaping signal, whileℒgen\\mathcal\{L\}\_\{\\mathrm\{gen\}\}remains the primary expert\-imitation objective\. We next define each task\-oriented term used in Eq\. \([39](https://arxiv.org/html/2605.13296#A4.E39)\)\.

#### Goal\-progress loss\.

We use a BFS\-based goal\-progress loss\. For each agent and timestep, letdi,τd\_\{i,\\tau\}be the shortest\-path distance from the predicted position to the goal on the obstacle map, and letd~i,τ=di,τ/s\\tilde\{d\}\_\{i,\\tau\}=d\_\{i,\\tau\}/sbe the normalized distance, wheres=max⁡\(Hmap,Wmap\)s=\\max\(H\_\{\\mathrm\{map\}\},W\_\{\\mathrm\{map\}\}\)is the map scale\. For trajectory horizonTT, the loss penalizes failures to make progress toward the goal:

ℒgoal=1N​\(T−1\)∑i=1N∑τ=0T−2max\(\\displaystyle\\mathcal\{L\}\_\{\\mathrm\{goal\}\}=\\frac\{1\}\{N\(T\-1\)\}\\sum\_\{i=1\}^\{N\}\\sum\_\{\\tau=0\}^\{T\-2\}\\max\\Bigl\(d~i,τ\+1−max\(d~i,τ−1s,0\),0\)\.\\displaystyle\\tilde\{d\}\_\{i,\\tau\+1\}\-\\max\\bigl\(\\tilde\{d\}\_\{i,\\tau\}\-\\tfrac\{1\}\{s\},0\\bigr\),0\\Bigr\)\.\(40\)This objective encourages each step to reduce the shortest\-path distance by approximately one cell whenever possible\.

#### Vertex\-conflict loss\.

Let𝐩i,τ\\mathbf\{p\}\_\{i,\\tau\}denote the expected position of agentiiat timestepτ\\tau, obtained from the predicted clean\-action probabilities𝐱^0\\hat\{\\mathbf\{x\}\}\_\{0\}\. We penalize agents that come within a Manhattan safety radiusrvr\_\{\\mathrm\{v\}\}:

ℒvertex=1\|𝒮v\|​∑\(i,j,τ\)∈𝒮vexp⁡\(−‖𝐩i,τ−𝐩j,τ‖1\),\\mathcal\{L\}\_\{\\mathrm\{vertex\}\}=\\frac\{1\}\{\|\\mathcal\{S\}\_\{\\mathrm\{v\}\}\|\}\\sum\_\{\(i,j,\\tau\)\\in\\mathcal\{S\}\_\{\\mathrm\{v\}\}\}\\exp\\\!\\left\(\-\\\|\\mathbf\{p\}\_\{i,\\tau\}\-\\mathbf\{p\}\_\{j,\\tau\}\\\|\_\{1\}\\right\),\(41\)where

𝒮v=\{\(i,j,τ\):i≠j,‖𝐩i,τ−𝐩j,τ‖1≤rv\}\.\\mathcal\{S\}\_\{\\mathrm\{v\}\}=\\left\\\{\(i,j,\\tau\):i\\neq j,\\,\\\|\\mathbf\{p\}\_\{i,\\tau\}\-\\mathbf\{p\}\_\{j,\\tau\}\\\|\_\{1\}\\leq r\_\{\\mathrm\{v\}\}\\right\\\}\.\(42\)

#### Edge\-conflict loss\.

We penalize swap\-like conflicts, where two agents move through the same edge in opposite directions between consecutive timesteps\. For agentsiiandjj, this occurs when𝐩i,τ\\mathbf\{p\}\_\{i,\\tau\}is close to𝐩j,τ\+1\\mathbf\{p\}\_\{j,\\tau\+1\}and𝐩i,τ\+1\\mathbf\{p\}\_\{i,\\tau\+1\}is close to𝐩j,τ\\mathbf\{p\}\_\{j,\\tau\}\. We therefore define

di​j,τ→=‖𝐩i,τ−𝐩j,τ\+1‖1,di​j,τ←=‖𝐩i,τ\+1−𝐩j,τ‖1\.d^\{\\rightarrow\}\_\{ij,\\tau\}=\\\|\\mathbf\{p\}\_\{i,\\tau\}\-\\mathbf\{p\}\_\{j,\\tau\+1\}\\\|\_\{1\},\\qquad d^\{\\leftarrow\}\_\{ij,\\tau\}=\\\|\\mathbf\{p\}\_\{i,\\tau\+1\}\-\\mathbf\{p\}\_\{j,\\tau\}\\\|\_\{1\}\.\(43\)Let𝒮e\\mathcal\{S\}\_\{\\mathrm\{e\}\}contain all triples\(i,j,τ\)\(i,j,\\tau\)for which both distances are no larger than the edge\-conflict radiusrer\_\{\\mathrm\{e\}\}\. The edge\-conflict loss is

ℒedge=1\|𝒮e\|​∑\(i,j,τ\)∈𝒮eexp⁡\(−di​j,τ→\+di​j,τ←2\)\.\\mathcal\{L\}\_\{\\mathrm\{edge\}\}=\\frac\{1\}\{\|\\mathcal\{S\}\_\{\\mathrm\{e\}\}\|\}\\sum\_\{\(i,j,\\tau\)\\in\\mathcal\{S\}\_\{\\mathrm\{e\}\}\}\\exp\\\!\\left\(\-\\frac\{d^\{\\rightarrow\}\_\{ij,\\tau\}\+d^\{\\leftarrow\}\_\{ij,\\tau\}\}\{2\}\\right\)\.\(44\)

#### Action\-validity loss\.

Let𝒜i,τvalid\\mathcal\{A\}\_\{i,\\tau\}^\{\\mathrm\{valid\}\}be the set of actions that remain in bounds and do not enter obstacles from the current rollout position\. We penalize probability mass assigned to invalid actions:

ℒvalid=1N​T​∑i,τ∑a∉𝒜i,τvalidx^0,i,τ,a\.\\mathcal\{L\}\_\{\\mathrm\{valid\}\}=\\frac\{1\}\{NT\}\\sum\_\{i,\\tau\}\\sum\_\{a\\notin\\mathcal\{A\}\_\{i,\\tau\}^\{\\mathrm\{valid\}\}\}\\hat\{x\}\_\{0,i,\\tau,a\}\.\(45\)

### D\.4Training Schedule

Training follows a two\-stage schedule\. In the first stage, we optimize only the generative objectiveℒgen\\mathcal\{L\}\_\{\\mathrm\{gen\}\}, which consists of the clean\-state auxiliary loss and the diffusion posterior\-matching KL loss\. The task\-oriented losses are disabled during the first 60 epochs\. In the second stage, we gradually introduce the task\-oriented objectiveℒtask\\mathcal\{L\}\_\{\\mathrm\{task\}\}over a 150\-epoch warmup period\. Leteedenote the number of epochs elapsed after the first stage\. The task\-loss scaling factor is

α​\(e\)=0\.2\+0\.8⋅min⁡\(e150,1\)\.\\alpha\(e\)=0\.2\+0\.8\\cdot\\min\\\!\\left\(\\frac\{e\}\{150\},\\,1\\right\)\.\(46\)The weights ofℒgoal\\mathcal\{L\}\_\{\\mathrm\{goal\}\},ℒvertex\\mathcal\{L\}\_\{\\mathrm\{vertex\}\},ℒedge\\mathcal\{L\}\_\{\\mathrm\{edge\}\}, andℒvalid\\mathcal\{L\}\_\{\\mathrm\{valid\}\}are multiplied byα​\(e\)\\alpha\(e\)during this warmup\.

### D\.5Optimization Hyperparameters

We optimize the model with AdamW\(Loshchilov and Hutter,[2019](https://arxiv.org/html/2605.13296#bib.bib15)\)using a constant learning rate of2×10−42\\times 10^\{\-4\}and weight decay10−410^\{\-4\}\. Gradients are clipped to norm1\.01\.0\. We do not use a learning\-rate scheduler or an exponential moving average\. The denoiser uses hidden dimension 128, conditioning dimension 128, 4 attention heads, 4 interaction layers, and dropout 0\. The deformable environment\-sensing module uses 8 sampling points per head and 3 feature scales\.

Table 5:Main supervised training hyperparameters used by DiffLNS\.