复杂拥挤多智能体路径规划中的离散扩散与稀疏社交注意力

# 复杂拥挤多智能体路径规划中的离散扩散与稀疏社交注意力
来源：https://arxiv.org/html/2605.13296

Yuanzhe Wang¹,²,³ Tian Zhi¹ Zihang Wei¹,³ Hongguang Wang¹,³ Jiaming Guo¹ Yang Zhao⁴ Zisheng Liu¹,³ Shiyu Quan¹,²,³ Xing Hu¹ Zidong Du¹ Yunji Chen¹,³

¹中国科学院计算技术研究所处理器国家重点实验室
²中国科学院大学跨学科高等研究院
³中国科学院大学
⁴中国科学院微电子研究所

###### 摘要

多智能体路径规划（MAPF）是一个需要在组合规划复杂度下，计算从各自起始位置到指定目标位置的全局一致、无碰撞轨迹的协调问题。在密集环境中，次优的初始规划会导致复合冲突，阻碍可行的修复。对于基于修复的求解器（如LNS2），初始规划质量对后续修复有决定性影响，但这一因素仍未得到充分探索。我们提出DiffLNS，一个将离散去噪扩散概率模型（D3PM）与LNS2集成的混合框架。D3PM作为一个带有稀疏社交注意力的初始化器，从专家演示中学习协调的多智能体动作轨迹上的时空先验，并采样多个联合规划。我们的离散扩散直接在分类动作空间上操作，保留了MAPF的动作结构，并从多模态联合规划分布中采样，生成适合邻域修复的多样化草稿。这些草稿作为下游修复的热启动，在硬MAPF约束下完成未完成的轨迹并解决剩余冲突。实验结果表明，尽管仅训练于最多96个智能体的实例，该初始化器在推理时能泛化到多达312个智能体的场景。在20个复杂拥挤设置中，DiffLNS实现了平均95.8%的成功率，比测试中最强的基线高出9.6个百分点，并在所有20个设置中达到或超越所有基线。据我们所知，这是首次利用离散扩散为基于LNS的MAPF求解器提供热启动的工作。

## 1 引言

多智能体路径规划（MAPF）旨在计算无碰撞轨迹，引导多个智能体从共享环境中的起始位置到达各自目标。作为一个基础的多智能体协调问题，MAPF在计算上具有挑战性，并支撑着广泛的实际应用，包括仓库自动化、自动驾驶车辆协调、无人机系统、车队管理和多机器人系统（Stern等人，2019）。因此，可扩展的次优规划一直是持续的研究焦点。

在现有方法中，基于修复的方法，如大邻域搜索2（LNS2），在实践中展现了强大的经验性能。这些方法从一组初始路径开始，迭代修复选定的智能体子集，直到冲突解决（Li等人，2021a，2022）。近年来，基于LNS的MAPF在修复阶段取得了显著进展，包括自适应邻域选择、破坏策略和增强重规划（Huang等人，2022；Phan等人，2024；Yan and Wu，2024；Wang等人，2025）。然而，初始化阶段仍然相对未被探索，关于选择有前景的初始解的工作有限（Huber等人，2025）。这一缺口至关重要，因为初始规划会显著影响基于LNS的修复的成功率和收敛速度（Huber等人，2025；Li等人，2021a）。在密集拥挤的环境中，低质量的初始规划往往包含严重冲突、死锁或全局不一致的运动模式。因此，后端规划器可能花费大量计算预算来修正糟糕的结构，而不是优化一个已有望解。一个适用于基于LNS的MAPF的有用初始化器应提供全局一致的联合规划，捕捉智能体之间有意义的时空协调，从而激发一个关于协调轨迹的结构化生成先验。

离散扩散非常适合这种形式，因为它可以通过迭代去噪捕捉复杂的轨迹分布，直接在分类动作空间中操作，并采样多样化的候选草稿以供后续修复（Carvalho等人，2023；Shaoul等人，2025；Liang等人，2025a）。然而，将扩散直接应用于MAPF仍具有挑战性：模型必须为大量智能体生成集中式联合规划，维持朝向各自目标的时间一致性，并在去噪过程中高效建模与冲突相关的智能体间交互。

为了克服基于修复的MAPF求解器中次优初始化的局限性，并解决将扩散应用于复杂拥挤MAPF环境的挑战，我们引入了*DiffLNS*，一个将离散去噪扩散概率模型（D3PM）（Austin等人，2021）与LNS2结合的混合框架。D3PM初始化器从专家演示中学习协调的多智能体动作轨迹上的时空先验。它采用一种扩散感知的稀疏社交注意力机制，根据当前去噪状态动态构建局部邻域，从而将计算集中在更可能交互或冲突的智能体上。在推理过程中，DiffLNS为同一实例采样多个草稿，用LNS2独立修复它们，并选择最佳可行解。这种设计使D3PM不仅作为一个学习型初始化器，还作为多样化修复种子的来源，使DiffLNS可扩展到更大的智能体团队，并自然可并行化处理独立生成的候选。

我们总结主要贡献和发现如下：

- **•初始化感知MAPF的混合框架。** 我们提出DiffLNS，它将基于离散扩散的生成器与LNS2修复集成，将焦点从仅修复改进转移到初始化质量。据我们所知，这是首次利用离散扩散为基于LNS的MAPF求解器提供热启动的工作。
- **•扩散感知的稀疏社交注意力。** 我们引入一种动态的、依赖于步数的稀疏注意力机制，根据当前噪声轨迹估计构建局部邻域。该设计减少了不必要的交互建模，同时关注冲突相关的智能体对，提高了效率和规划可修复性。
- **•强大的经验泛化能力和性能。** 尽管训练时最多使用96个智能体，DiffLNS可扩展到多达312个智能体的团队。在20个复杂拥挤设置中，它实现了平均95.8%的成功率，并在平均成功率上比测试中最强的基线LNS2+RL提高了9.6个百分点。

## 2 预备知识

### 2.1 多智能体路径规划

多智能体路径规划（MAPF）通常定义为在一个共享图或网格环境中，为多个智能体寻找从各自起始位置到各自目标的无碰撞路径的问题（Stern等人，2019）。令 \(G \in \{0,1\}^{H \times W}\) 表示地图，其中 \(G_{h,w}=0\) 表示可通行单元，\(G_{h,w}=1\) 表示障碍物。一组 \(N\) 个智能体由起始位置 \(\{s_i\}_{i=1}^N\) 和目标位置 \(\{g_i\}_{i=1}^N\) 指定。规划时域记为 \(T\)，\(\tau \in \{0,1,\dots,T\}\) 索引离散时间步。在每个时间步 \(\tau\)，每个智能体 \(i\) 执行一个动作 \(a_i^\tau \in \mathcal{A}\)，其中 \(\mathcal{A} = \{\texttt{stay}, \texttt{up}, \texttt{down}, \texttt{left}, \texttt{right}\}\)。一个有效的解必须避免顶点冲突（不同智能体在同一时间步占据同一单元）和边冲突（两个智能体在连续时间步交换位置）。解的质量由总代价（SOC）衡量，定义为所有智能体个体路径代价之和。

### 2.2 离散去噪扩散概率模型

离散去噪扩散概率模型定义一个前向马尔可夫链，在 \(K\) 步内逐渐破坏一个干净的离散变量 \(\mathbf{x}_0\)（Hoogeboom等人，2021；Austin等人，2021）。对于一个独热行向量 \(\mathbf{x}_k \in \{0,1\}^C\)，单步转移由 \(\mathbf{Q}_k \in \mathbb{R}^{C \times C}\) 参数化：

\[
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). \tag{1}
\]

对于结构化离散数据，该转移独立应用于每个离散元素。D3PM通常采用 \(\mathbf{x}_0\) 参数化，其中模型通过 \(\tilde{p}_\theta(\mathbf{x}_0 \mid \mathbf{x}_k)\) 从 \(\mathbf{x}_k\) 预测干净状态 \(\mathbf{x}_0\)（Hoogeboom等人，2021；Austin等人，2021）。然后反向转移构建为：

\[
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). \tag{2}
\]

标准训练目标将变分界与一个辅助的干净状态预测项结合（Austin等人，2021）：

\[
\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]. \tag{3}
\]

我们实现中使用的完整变分解在附录D.3中提供。在推理时，采样从 \(\mathbf{x}_K \sim p(\mathbf{x}_K)\) 开始，并迭代应用学习到的反向转移 \(k=K,\dots,1\)。

### 2.3 MAPF的大邻域搜索

MAPF-LNS2（Li等人，2022）是一种基于大邻域搜索的无界次优MAPF算法。它首先使用优先规划（PP）（Erdmann and Lozano-Perez，1986）结合底层求解器SIPPS构建初始规划；得到的规划可能包含碰撞。然后LNS2重复选择智能体子集进行重规划，同时保持其余路径固定，并接受不增加碰撞对数的更新。相同的PP+SIPPS过程用于邻域重规划，其中SIPPS在动态障碍物和软碰撞约束下计算单智能体路径（Li等人，2022）。由于每次迭代只修复局部智能体子集，修复的难度很大程度上取决于初始规划的冲突结构：局部化且轻微的冲突比纠缠严重的碰撞更容易解决。这一特性使初始化质量成为LNS2有效性的关键因素。

## 3 方法论

DiffLNS将MAPF初始化公式化为结构化生成式热启动，而不是直接的可解性求解。去噪模型学习协调联合动作序列上的时空先验并生成时空结构化的草稿，而LNS2通过修复剩余冲突和不完整路径来强制执行硬MAPF约束。

请参阅图说明

图1：DiffLNS混合框架概述。下面板显示了D3PM初始化器中使用的去噪网络架构，详见第3.2节。

### 3.1 混合框架概述

#### 联合动作形式化。
一个初始规划表示为一个联合离散动作张量

\[
\mathbf{x}_0 \in \{0,1\}^{N \times T \times C}, \tag{4}
\]

其中 \(N\) 是智能体数量，\(T\) 是规划时域，\(C=5\) 对应于网格动作 \(\{\texttt{stay}, \texttt{up}, \texttt{down}, \texttt{left}, \texttt{right}\}\)。每个切片 \(\mathbf{x}_{0,i,\tau,:}\) 表示智能体 \(i\) 在时间步 \(\tau\) 的一个独热动作标记。此表示与基于网格的MAPF的分类结构相匹配，并使D3PM能够直接在离散联合动作空间中操作。

#### 整体流程。
给定一个MAPF实例，D3PM初始化器在实例条件下采样一批联合动作草稿。每个草稿被转换为一个种子规划，并由LNS2修复。如果一个或多个修复后的规划可行，DiffLNS根据解质量（例如总代价SOC）返回最佳的一个。否则，系统继续采样和修复额外批次，直到评估预算耗尽。这一设计使框架与基于LNS的MAPF中修复侧的改进互补：不是修改修复算子本身，而是改进提供给它的初始规划。DiffLNS混合框架如图1所示。

### 3.2 基于离散扩散的结构化初始化

#### 条件去噪模型。
训练样本包括MAPF条件 \(\mathbf{c}\) 和在公式（4）中定义的专家联合动作张量 \(\mathbf{x}_0\)。给定一个噪声样本 \(\mathbf{x}_k \sim q(\mathbf{x}_k \mid \mathbf{x}_0)\)，我们训练一个条件干净状态预测器 \(\tilde{p}_\theta(\mathbf{x}_0 \mid \mathbf{x}_k, \mathbf{c})\)，采用第2.2节中介绍的 \(\mathbf{x}_0\) 参数化。去噪网络嵌入每个智能体在每个时间步的噪声动作分布，并将其与起始、目标、地图和扩散步特征融合。得到的条件动作标记由结构化的时空块处理，这些块整合了时间注意力、稀疏社交注意力和环境感知。时间注意力通过沿每个智能体轨迹的密集局部窗口注意力和稀疏步长全局连接促进运动一致性和目标进展；稀疏社交注意力建模局部冲突交互；环境感知提供障碍物感知。数据集构建、预处理和完整网络架构的细节见附录D；稀疏社交注意力模块如下所述。