Learning Repairable Initializations for Multi-Agent Path Finding via Discrete Diffusion

Multi-Agent Path Finding (MAPF) is a coordination problem that requires computing globally consistent, collision-free trajectories for multiple agents from their start positions to assigned goals in a shared environment. In dense settings, sequential prioritized planning can concentrate repeated conflicts on a small subset of agents, hindering local repair. Despite its importance for downstream repair, the initialization stage of repair-based MAPF solvers has received relatively limited research attention. We propose DiffLNS, a hybrid framework that integrates a discrete denoising diffusion probabilistic model (D3PM) with LNS2 to improve initialization for repair. Trained on expert demonstrations, the D3PM initializer uses diffusion-aware sparse social attention to learn a spatiotemporal prior and samples diverse plans directly in the categorical action space. These plans serve as warm starts for LNS2, which completes unfinished trajectories and resolves conflicts under hard MAPF constraints. Controlled comparisons show that diffusion-generated initializations exhibit more balanced conflict loads across agents and achieve higher repair success under the same repair procedure and budget, despite starting with more colliding pairs. Although trained with at most 96 agents, the initializer generalizes to tested scenarios with up to 312 agents. Across 20 complex and congested settings, DiffLNS achieves an average success rate of 95.8%, exceeding the strongest tested baseline by 9.65 percentage points and matching or exceeding all baselines in every setting. To the best of our knowledge, this is the first work to use discrete diffusion to warm-start an LNS-based MAPF solver.