PARCO: Parallel AutoRegressive models for multi-agent combinatorial optimization

https://github.com/ai4co/parco

PARCO：并行自回归模型在多智能体组合优化中的应用

信息

• 作者: Federico Berto, Chuanbo Hua, Laurin Luttmann, Jiwoo Son, Junyoung Park, Kyuree Ahn, Changhyun Kwon, Lin Xie, Jinkyoo Park
• 单位: Leuphana University, Brandenburg University of Technology AI4CO
• 日期: 2025年10月
• 会议: NeurIPS 2025

---

1. 概述

1.1. 背景

在物流配送、机器人协作和生产调度等领域，多智能体组合优化（MACO）问题（如多旅行商问题 mTSP、多车辆路径规划 mCVRP 和作业车间调度 JSSP）具有极高的计算复杂度。

传统的求解器（如 Gurobi 或 LKH3）虽然效果好，但在大规模场景下推理缓慢。

传统的深度强化学习（DRL）方法通常面临一个两难困境：要么像自回归（AR）模型那样一个接一个地生成路径（质量高但慢），要么像非自回归（NAR）模型那样一次性生成所有路径（快但各智能体互不配合，质量差）。

1.2. 贡献

PARCO 的核心贡献在于：

• 并行自回归生成： 改变了以往逐个智能体决策的模式，允许 $N$ 个智能体在每个时间步同步进行决策，显著降低了推理延迟。
• Transformer 通讯机制： 通过在解码器中集成 Transformer 层，实现了智能体之间的信息交换，增强了协作性。
• 多指针机制（Multi-pointer Mechanism）： 扩展了传统的单指针网络，使其能够单次前向传播同时输出多个智能体的动作概率。
• 优先级冲突处理： 针对多智能体在并行决策中可能争抢同一资源（如同一个节点）的问题，设计了基于学习优先级的冲突解决算法。

---

2. 方法

PARCO 的核心逻辑是利用强化学习训练一个参数为 $\theta$ 的神经网络，通过并行自回归的方式构造解，在每一步 $t$，同时为所有 agent 生成动作（parallel AR），然后再通过一个显式的可行性修正机制（conflict handler）处理冲突，从而在保持并行性的同时保证解的合法性。

2.1. 问题定义

假设有 $N$ 个智能体和一组任务节点 $V$。在每个离散时间步 $t$，每个智能体 $i$ 选择一个动作 $a_i^t\in V$，则所有智能体的联合动作向量为 ${\mathbf{a}}^t=(a_1^t,\dots ,a_N^t)$，其中每个 $a_i^t$ 表示第 $i$ 个 agent 在时间步 $t$ 选择访问的节点或执行的操作，而完整解可以表示为序列 $a=(a^1,\dots ,a^T)$，其中 $T$ 为决策步数。

带冲突处理的联合概率分解为
$$p_{\theta }(a|x)=\prod _{t=1}^T\psi \left(\prod _{m=1}^M{p}_{\theta }(a_t^m\mid a^{<t},h)\right)$$

其中：

• $x$ 表示输入实例（如节点坐标、需求等原始问题信息）
• $\theta$ 表示模型参数
• $a^{<t}$ 表示在时间步 $t$ 之前所有已生成的联合动作序列
• $h$ 表示由编码器得到的全局上下文表示（包含节点和 agent 的嵌入）
• $M$ 表示 agent 数量
• $a_t^m$ 表示第 $m$ 个 agent 在时间步 $t$ 的动作
• $\psi (\cdot )$ 表示冲突处理函数（feasibility operator），用于将可能冲突的联合动作映射为可行解
• 内层 ${\prod }_m$：表示在给定历史 $a^{<t}$ 和上下文 $h$ 的条件下，各个 agent 的动作是条件独立建模并并行生成的
• 外层 $\psi$：对独立生成的动作集合进行可行性修正（conflict resolution）

因此每一步的联合动作 ${\mathbf{a}}^t$ 并不是直接从一个严格满足约束的分布中采样，而是先由 ${\prod }_m{p}_{\theta }(a_t^m\mid a^{<t},h)$ 生成“候选动作集合”，再通过 $\psi$ 投影到可行空间，这本质上是一种 “生成 + 投影”而非“直接可行建模” 的策略，这也是 PARCO 能够实现并行决策的关键。

模型的目标是最大化期望收益（或最小化总成本 $C$）：
$$J(\theta )={\mathbb{E}}_{p_{\theta }(\mathbf{a}|s)}\left[\sum _{t=1}^{T}R(s^t,{\mathbf{a}}^t)\right]$$

其中 $s^t$ 表示时间步 $t$ 的环境状态，通常包含所有 agent 的当前位置、剩余容量/资源以及节点的访问状态等动态信息。$R(s^t,{\mathbf{a}}^t)$ 表示在状态 $s^t$ 下执行联合动作 ${\mathbf{a}}^t$ 所获得的即时奖励

在实际训练中，通常使用策略梯度方法优化该目标，其梯度形式为：
$${\nabla }_{\theta }L(\theta )\approx {\mathbb{E}}_{p_{\theta }(a|x)}\left[(R(a)-b){\nabla }_{\theta }\log p_{\theta }(a|x)\right]$$

• $R(a)$ 是完整解 $a$ 的总回报（通常在终止时刻计算，因此是稀疏奖励）
• $b$ 是 baseline（如 critic 或移动平均），用于降低方差

2.2. 网络架构

PARCO 由编码器 (Encoder) 和 多指针解码器 (Multi-pointer Decoder) 组成，其中编码器负责构建全局表示 $h$，解码器在每一步生成所有 agent 的联合动作。

2.2.1. 编码器

编码器使用多层 Transformer 结构，将输入实例 $x$（如节点特征、agent 初始状态）映射为高维嵌入表示 $h$，其中既包含所有节点嵌入 $h_n$，也包含所有 agent 嵌入 $h_a$，从而在统一特征空间中建模“任务”和“执行者”。

每个节点 $v$ 的特征经过编码器处理为：

$${\mathbf{h}}_v=\text{Encoder}({\text{Features}}_v)$$

编码器可以通过以下两种方式建模关系：

• 对节点和 agent 拼接后进行 self-attention
• 或使用 agent→node 的 cross-attention

从而使每个 embedding 不仅包含局部信息，还编码了全局结构以及 agent–node 之间的交互关系。

2.2.2. 通讯增强的解码器

2.2.2.1. 第一阶段：智能体间的通讯（Communication Layer）

在时间步 $t$，每个 agent $i$ 的决策依赖于其当前状态和全局信息，因此首先构造 query 向量：

$$q_i^t=W_q\cdot \text{Concat}(h_a^i,h_{{\delta }_i^t},h_e^t)$$

其中：

• $W_q$ 是可学习的线性映射参数
• $h_a^i$ 是第 $i$ 个 agent 的静态 embedding
• $h_{{\delta }_i^t}$ 表示 agent 当前所在节点 ${\delta }_i^t$ 的 embedding（即当前位置）
• $h_e^t$ 是全局上下文 embedding
• $q_i^t$ 是第 $i$ 个 agent 在时间步 $t$ 的查询向量

接下来通过多头注意力进行 agent 之间的信息交互，其标准形式为：
$$q^{\prime }=\text{Norm}(\text{MHA}(q,q,q)+q)$$
$$q=\text{Norm}(\text{MLP}(q^{\prime })+q^{\prime })$$
$\text{MHA}(q,q,q)$ 表示以所有 agent 的 query 为输入的 self-attention，用于建模 agent–agent 交互。

该过程不仅包含 agent 对节点的关注（cross-attention），还包括 agent 之间的自注意力（self-attention），从而实现“我在看哪些节点”与“其他 agent 想去哪里”之间的信息融合，这一步本质上是在进行隐式的协同规划，而不是独立决策。

2.2.2.2. 第二阶段：多指针机制（Multi-pointer Mechanism）

在得到更新后的 query 后，每个 agent 同时对所有节点进行打分，打分公式为：
$$u=\beta \cdot \tanh \left(\frac{q^{\prime }(h_n{W}^L+{\xi }_t{W}_{\xi }^L{)}^T}{\sqrt{d}}\right)$$

• $q^{\prime }$ 是经过通信层更新后的 agent query
• $W^L$ 是节点投影矩阵
• ${\xi }_t$ 表示节点的动态特征（如是否已访问、剩余需求等）
• $W_{\xi }^L$ 是动态特征的投影矩阵
• $d$ 是 embedding 维度

随后对每个 agent 的打分做 masked softmax：

$$p(a^t)=\prod _{m}p(a_m^t)$$

这一步意味着在冲突处理之前，各 agent 的动作是条件独立建模的，从而可以并行计算。

2.2.2.3. 第三阶段：基于优先级的冲突处理（Conflict Resolution）

这是并行决策最关键的一步：由于多个 agent 是独立采样的，因此可能会出现多个 agent 同时选择同一节点的冲突情况。

PARCO 学习了一个优先级分数（Priority Score） ${\pi }_i^t$：
$${\pi }_i^t=p(a_i^t)$$
$p(a_i^t)$ 是该 agent 选择其动作的概率（即模型置信度），从而使得“更确定”的决策优先被保留。

• 算法流程（Algorithm 1）：
  • 每个智能体根据概率分布采样出一个候选动作 ${\hat{a}}_i^t$。
  • 如果发生碰撞（多人选同一点），则 ${\pi }_i^t$ 最高的智能体胜出，获得该节点，保证唯一性。
  • 被挤掉的智能体不会重新从完整分布中采样，而是执行简化策略（如保持不动或等待），从而避免复杂的循环重采样过程并稳定训练。

---

3. 实验

3.1. 实验设置

• 问题：
  • 最小-最大异构车辆路线问题（HCVRP）：多个容量不同的车辆需要服务客户节点并满足需求与容量约束，目标是最小化所有车辆中最长路径长度（min-max），因此该问题强调的是负载均衡而非总距离最短。
  • 开放多仓库取货送货问题 (OMDCPDP) ：多个 agent 从不同仓库出发执行带有 pickup-delivery 配对约束的任务且不需要返回仓库，需同时满足容量与顺序约束，目标是最小化总延迟（lateness），这是一个强耦合的路径+调度问题。
  • 柔性流水车间问题 (FFSP) ：多个作业需按阶段顺序在并行机器（agents）上加工，每台机器同一时间只能处理一个任务，目标是最小化完工时间（makespan），该问题主要为了体现了PARCO从路径规划向调度问题的泛化能力。

• 对比基准： 包含传统算法（如 OR-Tools、Gurobi、启发式方法 GA/SA）、非自回归方法（Matrix-Attention Network/MatNet）以及多种自回归方法（AM、ET、DPN、DRLLi、2D-Ptr 等），其中既包括顺序构造解的方法，也包括已有的并行方法（如 MAPDP），用于全面评估 PARCO 在协同能力与并行效率上的优势。

3.2. 结果：

• 解的质量： 在多种任务（如 HCVRP、OMDCPDP、FFSP）中，PARCO 的 gap 显著低于其他学习类方法，并在采样模式下接近甚至达到传统强求解器的水平，其性能提升主要来源于通信机制带来的更强多智能体协同能力，而非单纯模型表达能力提升。

• 推理速度： 相比于逐个智能体构造解的串行方法（需要 ${\sum }_m{T}_m$ 步），PARCO 仅需 ${\max }_m{T}_m$ 步即可完成解构造，因此推理延迟可降低 3× 到 20× 以上，本质上是将时间复杂度从“总和”降低为“最大值”，在大规模多智能体场景（如调度问题）中优势尤为明显。

• 泛化能力： 在测试时将节点数量和智能体数量扩大至训练规模的数倍甚至 10 倍时，PARCO 仍能保持较低 gap，而传统 AR 方法和部分并行方法会显著退化，这表明其结构对agent 数量和问题规模具有良好的泛化性。

3.3. 消融实验

• 加入通讯层（Communication Layer）能显著提升协作效率，因为 agent 能显式建模彼此状态；
• 去掉冲突处理机制或使用随机优先级，模型往往因资源争抢导致解的质量大幅下降，而基于模型输出概率的学习型优先级策略效果最佳，说明冲突处理本身也是一个关键的学习模块。

---

4. 结论

4.1. 结论

PARCO 成功地平衡了自回归模型的“高解质量”与并行生成的“低延迟”。通过 Transformer 通讯层和优先级冲突解决机制，它解决了多智能体协作中的核心难题，在多种 MACO 任务中达到了最先进的性能（SOTA）。

4.2. 限制

1. 动作空间约束： 在某些极其复杂的约束（如具有复杂的窗口时间限制）下，简单的优先级冲突处理可能无法保证解的完全可行性，需要更复杂的逻辑支撑。
2. 智能体同质性： 目前实验主要集中在同质智能体。在异质智能体（不同速度、不同容量限制）场景下的泛化能力仍有待进一步验证。

4.3. 未来方向

• 异质智能体扩展： 优化模型以处理具有不同物理特性的智能体协作。
• 动态环境： 将 PARCO 应用于节点或需求实时变化的动态 CO 问题。
• 大规模扩展性： 探索在成千上万个智能体场景下的高效通讯拓扑结构，以避免全连接通讯带来的计算开销。