Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
作者: Yuanzhe Wang, Tian Zhi, Zihang Wei, Hongguang Wang, Jiaming Guo, Yang Zhao, Zisheng Liu, Shiyu Quan, Xing Hu, Zidong Du, Yunji Chen
分类: cs.AI, cs.LG, cs.MA
发布日期: 2026-05-13
备注: 24 pages, 7 figures
💡 一句话要点
DiffLNS：融合离散扩散与稀疏注意力机制，解决复杂拥堵环境下的多智能体路径规划问题
🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 多智能体路径规划 离散扩散模型 LNS2 稀疏注意力 组合优化
📋 核心要点
- 现有基于修复的MAPF求解器（如LNS2）在密集环境中受限于初始规划质量，次优初始规划导致复合冲突，阻碍可行解的搜索。
- DiffLNS融合离散去噪扩散概率模型（D3PM）与LNS2，利用D3PM学习时空先验并生成多样化初始规划，为LNS2提供高质量热启动。
- 实验表明，DiffLNS在复杂拥堵环境中显著提升MAPF求解成功率，平均成功率达95.8%，超越现有最优基线9.6个百分点。
📝 摘要（中文）
多智能体路径规划（MAPF）是一个协调问题，需要在组合规划复杂性下，计算从个体起始位置到指定目标位置的全局一致、无碰撞轨迹。在密集环境中，次优的初始规划会导致复合冲突，阻碍可行的修复。对于像LNS2这样的基于修复的求解器，初始规划质量至关重要，但这一因素尚未得到充分探索。我们提出了DiffLNS，一个混合框架，它将离散去噪扩散概率模型（D3PM）与LNS2集成。D3PM作为一个初始化器，通过稀疏社交注意力学习协调的多智能体行动轨迹的时空先验，并从专家演示中采样多个联合规划。我们的离散扩散直接在分类行动空间上操作，保留了MAPF行动结构，并从多模态联合规划分布中采样，以产生多样化的草案，非常适合邻域修复。这些草案作为下游修复的热启动，在硬MAPF约束下完成未完成的轨迹并解决剩余的冲突。实验结果表明，尽管初始化器仅在最多96个智能体的实例上进行训练，但在推理时可推广到最多312个智能体的场景。在20个复杂和拥堵的环境中，DiffLNS实现了95.8%的平均成功率，比最强的测试基线高出9.6个百分点，并且在所有20个设置中匹配或超过了所有基线。据我们所知，这是第一项利用离散扩散来热启动基于LNS的MAPF求解器的工作。
🔬 方法详解
问题定义：论文旨在解决复杂和拥堵环境中多智能体路径规划（MAPF）问题。现有基于修复的求解器，如LNS2，在密集环境中性能受限于初始规划的质量。次优的初始规划会导致大量的冲突，使得后续的修复过程难以找到可行解。因此，如何生成高质量的初始规划是解决该问题的关键。
核心思路：论文的核心思路是利用离散去噪扩散概率模型（D3PM）学习多智能体行动轨迹的时空先验，并生成多样化的初始规划。D3PM能够直接在离散的行动空间上进行采样，保留了MAPF的行动结构，并且能够生成多模态的联合规划，为后续的修复过程提供更好的起点。通过将D3PM生成的初始规划作为LNS2的热启动，可以加速LNS2的收敛，并提高求解成功率。
技术框架：DiffLNS的整体框架包含两个主要模块：离散扩散初始化器和LNS2修复器。首先，离散扩散初始化器基于专家演示数据学习多智能体行动轨迹的时空先验，并采样生成多个初始规划。然后，LNS2修复器以这些初始规划作为热启动，完成未完成的轨迹并解决剩余的冲突，最终得到满足硬MAPF约束的解。
关键创新：论文最重要的技术创新点在于将离散扩散模型应用于MAPF的初始规划生成。与传统的启发式方法或基于搜索的方法不同，离散扩散模型能够学习到更加复杂的时空依赖关系，并生成多样化的、高质量的初始规划。此外，论文还引入了稀疏社交注意力机制，使得模型能够更好地捕捉智能体之间的交互关系。
关键设计：D3PM使用Transformer架构，其中关键的设计包括：1) 离散扩散过程：使用分类交叉熵损失函数训练D3PM，使其能够从噪声分布逐步恢复到真实的行动轨迹分布。2) 稀疏社交注意力：通过限制每个智能体只能关注其邻近的智能体，降低了计算复杂度，并提高了模型的泛化能力。3) LNS2修复器：使用标准LNS2算法，但以D3PM生成的初始规划作为热启动，加速收敛。
🖼️ 关键图片
📊 实验亮点
DiffLNS在20个复杂拥堵环境中进行了实验，结果表明其平均成功率达到95.8%，比最强的基线提高了9.6个百分点。值得注意的是，尽管D3PM仅在最多96个智能体的场景下训练，但它能够泛化到最多312个智能体的场景，展示了良好的泛化能力。DiffLNS在所有20个测试环境中均匹配或超过了所有基线。
🎯 应用场景
该研究成果可应用于仓库机器人、自动驾驶、交通调度等领域，解决大规模、高密度场景下的多智能体协同问题。通过提升路径规划效率和成功率，可以显著提高物流效率、降低交通拥堵，并为智能交通系统的发展提供技术支撑。未来，该方法有望扩展到更复杂的任务规划和资源分配问题。
📄 摘要（原文）
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.