许多现实生活问题可以被建模为多智能体任务并尝试使用多智能体强化学习技术解决. 尽管近期工作已经在诸多领域取得了显著进展，例如自动车驾驶^[1]、交通控制^[2-4]、机器人群体控制^[5]、量化交易^[6]和传感网络^[7]等，但是对于复杂多智能体任务而言，利用多智能体强化学习算法为智能体学习有效的协作策略仍然充满挑战. 一个主要问题是多智能体强化学习算法学习效率低下，通常需要成百上千万次试错才能学习到最优策略^[8]. 此外，在多智能体任务中，多智能体强化学习算法需要在智能体联合动作空间中搜索最优联合策略. 因为智能体联合动作空间随智能体数量呈指数级增长，所以这进一步加剧了多智能体强化学习算法的效率低下问题，导致其难以实现多智能体任务中智能体协作策略的高效学习.

提升多智能体强化学习算法学习效率的一种有效手段是建模多智能体任务中潜在的智能体间交互结构，并且利用该结构信息去指导智能体策略学习，从而提升算法的学习效率. 基于这一思路，本文假设多智能体任务存在近似可分解结构^[9]，并旨在针对该类多智能体任务实现智能体间的高效协作. 具体而言，近似可分解结构假设相同交互集合内智能体间交互强度大，而不同交互集合内智能体间交互强度小，但不可忽视. 这一结构广泛存在于现实生活场景中，例如在公司员工管理中，相同部门内的员工间交互相比不同部门员工间交互更加频繁. 同样，在足球比赛中，距离相近的球员间交互强度相比距离较远的球员间交互强度更大. 显而易见，对于具有近似可分解结构的合作型多智能体任务，智能体间协作包括相同交互集合内部分智能体间的局部协作以及不同交互集合全部智能体间的全局协作. 基于任务的近似可分解结构来设计协作机制以有效地建模智能体间局部和全部协作，可以缓解多智能体强化学习算法在智能体联合动作空间搜索带来的效率低下问题，进而提升协作策略的学习效率.

设计协作机制有效建模智能体间局部和全局协作需要解决2个问题：1）如何识别智能体交互集合；2）如何实现智能体间局部和全局协作. 目前主要有三大类工作尝试解决该问题.

第1类工作主要包括值函数分解算法^[10-13]和多智能体策略梯度算法^[14-20]. 该类算法忽视智能体间局部协作，直接优化智能体联合策略来实现智能体间全局协作. 然而，直接在智能体联合动作空间上搜索最优联合策略通常会导致算法学习效率低下，影响智能体间高效协作.

第2类工作^[21-25]通过将全局动作值函数分解为定义在局部智能体联合动作上的局部值函数，并允许智能体间通信来实现智能体间局部和全局协作. 然而，该类算法严重依赖于智能体间通信，导致其无法适用于通信受限甚至不可用的现实生活多智能体场景.

第3类工作利用邻域^[26]、分组^[27-30]、角色^[31-32]和子任务^[33-36]等概念来识别智能体交互集合，并且限制相同交互集合内智能体遵循相似约束来实现智能体间局部协作. 同时该类算法通过学习全局动作值函数来实现智能体间全局协作. 然而，该类算法仍存在2个问题：1）当局部协作约束与任务目标相悖时，可能会影响智能体间协作性能；2）当智能体协作行为缺乏导致任务回报稀疏时，仅根据任务回报学习全局动作值函数可能会导致智能体间全局协作效率低下.

为设计高效协作机制来有效建模智能体间局部和全局协作，本文提出智能体动态协作图来建模多智能体任务中的近似可分解结构，并刻画随时间变化的智能体间交互关系，如图1所示. 其中节点表示智能体，节点间的边表示智能体间交互关系. 当智能体处于相同交互集合中时，其间交互强度较大；而不同交互集合智能体间交互强度小. 基于该形式化，多智能体强化学习算法可以通过有效建模智能体动态协作图中智能体间交互集合，并着重利用相同交互集合内相关智能体信息辅助其内每个智能体策略学习，从而提升智能体间协作策略学习效率. 根据这一观点，本文提出协作子任务行为（coordinated subtask pattern，CSP）算法. 具体而言，CSP算法利用子任务来识别智能体交互集合，并采用双层策略结构来协调智能体间的动作选择. 其中，上层策略将所有智能体周期性地分配到多个子任务中，而下层策略基于智能体子任务分配为其输出原子动作. 该上层策略受益于较小的联合子任务空间以及时序抽象的任务回报，因此可以实现有效的子任务分配，从而准确刻画智能体动态协作图上智能体间的交互关系. 基于这种子任务分配，CSP算法提出子任务内行为约束确保相同子任务内的部分智能体间可以预知彼此动作选择，之后每个智能体基于其局部信息和相同子任务内其他智能体动作预测信息选择动作来最大化任务回报，由此提升相同子任务内智能体间局部协作；同时，针对智能体间全局协作，CSP算法将智能体上层联合策略相应的时间差分误差作为子任务间行为约束指导智能体协作策略学习. 该约束可以为智能体下层策略提供稠密的监督信息，鼓励所有智能体选择优异的联合动作来最大化该约束和任务回报，由此实现智能体间全局高效协作.

图  1  对于多智能体任务中近似可分解结构的动态协作图

Figure  1.  Dynamic coordination graph of the nearly decomposable structure in multi-agent tasks

下载: 全尺寸图片 幻灯片

本文在星际争霸^[37]环境下对CSP算法进行评估. 实验结果表明该算法在多个地图上性能明显优于多个对比算法. 此外，消融实验也验证了CSP算法所提子任务内和子任务间行为约束的有效性.

本文主要贡献包括3个方面：

1）利用智能体动态协作图来建模多智能体任务中的近似可分解结构，并指出需要同时刻画智能体间局部和全局协作来实现协作策略的高效学习；

2）提出协作子任务行为算法，该算法通过分配子任务来识别智能体间交互关系，并提出子任务内和子任务间行为约束增强智能体局部和全局协作；

3）在星际争霸环境多个地图上的实验结果验证了本文所提算法的学习效率明显优于对比算法，且消融实验验证了本文所提约束的有效性.

1.   相关工作

在本节中，我们根据目前多智能体强化学习算法实现智能体间协作的方式将其划分为三大类，并简要介绍每一类工作的代表性算法.

大部分多智能体强化学习算法属于第1类工作，该类算法通过直接学习智能体最优联合策略来实现智能体间全局协作. 其中值函数分解算法VDN^[10]，QMIX^[11]，QTRAN^[12]和QPLEX^[13]等通过学习一个可分解的全局动作值函数来更新所有智能体的去集中式效用函数（效用函数对应智能体的去集中式策略）. 多智能体策略梯度算法例如MADDPG^[14]，COMA^[15]，DOP^[16]，FACMAC^[17]，MAPPO^[18]，HAPPO^[19]以及MADDPG-DC^[20]等利用集中式值函数指导智能体去集中式策略的学习. 尽管这一类算法可以克服多智能体任务中策略学习的非稳态问题，但是它们并未显式利用多智能体任务中存在的近似可分解结构. 此外，直接在智能体联合动作空间上搜索最优联合策略会导致策略学习效率低下，影响智能体间高效协作.

第2类工作通过将全局动作值函数分解为定义在成对或局部智能体联合动作上的局部值函数来隐式地协调智能体局部和全局动作选择，以增强智能体间局部和全局协作. 例如协同强化学习算法^[21]通过学习一组定义在局部智能体联合动作上的局部值函数来近似全局动作值函数，并利用通信传递技术来决定最优联合动作. 文献[22]将该算法扩展到网络化分布式部分可观测马尔可夫决策过程，其利用分布式约束优化技术来协调多个预定义智能体交互集合的分布式学习. 随后，文献[23]通过定义交互度量来动态识别智能体交互集合，从而降低智能体间通信开销. 近期通信算法^[24-25]在特定智能体间进行通信，隐式地构建智能体间交互集合，因此也属于这一类工作. 尽管这类算法利用通信实现智能体间有效协作，但是当智能体间通信受限甚至不可用时，该类算法难以生效.

第3类工作利用邻域、分组、角色和子任务等概念来识别智能体交互集合，并限制相同交互集合内智能体服从相似约束来实现智能体间局部协作. 具体而言，NCC^[26]预定义智能体邻域并约束相同邻域内智能体生成相似认知后验. GoMARL^[27]通过学习分组效用值函数对智能体进行动态分组，同时鼓励智能体生成组内相似、组间差异的分组表征以及相应策略参数，由此提升相同分组内智能体间局部协作. DCN^[28]首先利用图神经网络输出智能体观测表征，随后利用K-Means聚类对智能体进行分组，最后学习分组效用函数来刻画智能体间局部协作. GPLight^[29]利用图卷积网路编码智能体观测，随后对齐具有相似轨迹的智能体相应观测表征，由此实现相同组内智能体观测表征相似，从而提升智能体间局部协作. AVGM^[30]将每个智能体可视范围内智能体集合视为其所属分组，并构建分组效用函数协调组内智能体动作选择.

除邻域、分组外，角色概念也被用于刻画智能体局部交互集合. 例如ROMA^[31]为具有相似轨迹的智能体生成相似角色变量，由此实现智能体交互集合划分. 同时，该算法通过最大化相同集合内智能体彼此角色和轨迹间互信息来实现局部协作. 随后，RODE^[32]基于动作语义显式定义角色，并限制智能体仅能执行其分配角色内所含动作. 除以上算法，近期算法通过为智能体分配子任务来协调其动作选择. LDSA^[33]通过学习差异化子任务表征和定义在这些表征上的子任务策略来约束相同子任务内智能体行为相似. ALMA^[34]基于分层框架将所有智能体分配到预设子任务中，并分别学习可分解的子任务值函数来实现各子任务内智能体协作. MACC^[35]将任务中实体视为子任务，并为智能体学习子任务表征重构相应实体轨迹，由此实现对相应子任务的隐式关注. CDS3^[36]基于智能体观测构建差异化子任务表征，并设计面向智能体编号的行为多样性内在激励和部分共享的网络结构来提升探索，由此实现子任务策略的高效学习.

尽管第3类工作通过邻域、分组、角色和子任务等概念来增强智能体间局部协作，但是仍存在3个问题：1）NCC，ALMA，MACC等算法需要任务先验信息才能识别智能体交互集合；2）NCC，GoMARL，GPLight，LDSA，ROMA，RODE等算法约束相同交互集合内智能体认知或策略相似，该局部约束可能与任务目标相悖并影响智能体协作性能；3）当智能体协作行为缺乏导致任务回报稀疏时，该类算法仅根据任务回报学习全局动作值函数来实现智能体间全局协作这一做法可能会导致智能体全局协作效率低下. 相比之下，本文算法预设子任务数量并基于双层策略结构实现智能体子任务自适应分配和识别，无需任务先验信息. 同时，相同子任务内智能体以彼此动作预测作为额外信息选择动作来最大化任务回报，此时子任务内优化目标和任务目标一致，因此保证智能体间局部协作能够提升任务整体性能. 此外，针对任务回报稀疏问题，本文算法基于上层策略设计稠密监督信息，鼓励所有智能体选择优异的联合动作来最大化该约束和任务回报，由此有效增强智能体间全局协作.

综上所述，目前多智能体强化学习算法无法有效实现智能体间局部和全局协作. 为解决该问题，本文提出子任务内和子任务间行为约束来增强智能体间局部和全局协作. 因此，本文算法可以作为一种智能体间高效协作机制辅助多智能体强化学习算法，由此提升智能体协作策略的学习效率.

2.   背景知识

在本节中，我们形式化本文拟解决的多智能体任务，并对值函数分解算法进行简要概述.

2.1   去集中式部分可观测马尔可夫决策过程

对于要求智能体进行去集中式决策的合作型多智能体任务，通常将其建模为去集中式部分可观测马尔可夫决策过程（decentralized partially observable Markov decision process，Dec-POMDP）. Dec-POMDP可以用多元组$( N,S,{\boldsymbol{A}},R,P,\gamma,{{Z}},{{O}})$表示，其中N={1, 2, …, n}表示智能体集合，S表示状态空间. A=A¹ × A² × … × Aⁿ代表智能体联合动作空间，其中Aⁱ代表智能体i∈N的局部动作空间. 在每一时间步t，每个智能体i∈N根据其局部观测函数${O^i}(o_t^i|{s_t}) \in {{O}}$获取其局部观测$o_t^i \in {Z^i} \in {{Z}}$，随后根据其局部策略${\pi ^i}$选择动作$a_t^i$. 基于所有智能体的联合动作${{\boldsymbol{a}}_{\boldsymbol{t}}} = (a_t^1,a_t^2,. . . ,a_t^n)$，多智能体任务环境$s_t$根据状态转移函数$P({s_{t + 1}}|{s_t},{{\boldsymbol{a}}_{\boldsymbol{t}}})$转移到下一状态${s_{t + 1}}$，同时根据回报函数$R({s_t},{{\boldsymbol{a}}_{\boldsymbol{t}}})$反馈给所有智能体共享回报${r_t}$. 为应对部分可观测问题，目前算法利用智能体动作-观测历史$\tau _t^i = (o_1^i,a_1^i,o_2^i,a_2^i,. . . ,o_t^i)$进行动作选择，即智能体学习局部策略${\pi ^i}(a_t^i|\tau _t^i)$. 在Dec-POMDP中，所有智能体的目标为学习最优联合策略${\boldsymbol{\pi }} = ({\pi ^1},{\pi ^2},. . . ,{\pi ^n})$，该联合策略可以最大化期望累计折扣回报${\mathbb{E}_{{\boldsymbol{\pi }},P}}\left[\displaystyle\sum_{t = 0}^\infty {{\gamma ^t}{r_t}} \right]$，其中$\gamma$为折扣因子.

2.2   值函数分解算法

本文基于的值函数分解算法为智能体学习去集中式策略. 值函数分解算法如VDN、QMIX、QTRAN等将全局动作值函数${Q^{\rm total}}$分解为每个智能体的去集中式效用函数${Q^i}({\tau ^i},{a^i})$（效用函数定义在智能体局部动作-观测历史${\tau ^i}$和局部动作${a^i}$上，对应每个智能体的去集中式策略${\pi ^i}$），由此可以通过${Q^{\rm total}}$来更新${Q^i}$. 为保证${Q^{\rm total}}$和${Q^i}$最优动作的一致性，其两者间分解关系需要满足局部-全局最大化（individual-global max，IGM）原则. IGM原则定义为：

其中${\boldsymbol{\tau }}$代表智能体联合动作-观测历史. 基于IGM原则，${Q^{\rm total}}$对应智能体联合动作空间上的贪婪联合动作，其可以通过对每个智能体${Q^i}$进行局部贪婪操作得到.

以QMIX算法为例，该算法通过提出单调性约束来遵循IGM原则. 其单调性约束定义为：

并通过学习一个混合网络$f$来计算${Q^{\rm total}}$，计算公式定义为：

QMIX算法以状态$s$作为超参网络输入来生成混合网络$f$的参数，并且限制混合网络$f$的权值非负以满足单调性约束. 在计算得到${Q^{\rm total}}$后，所有智能体的去集中式效用函数${Q^i}$即可利用${Q^{\rm total}}$相应的时间差分损失（temporal difference loss，TD-loss）进行更新.

3.   协作子任务行为算法

本节详细介绍CSP算法. 我们首先使用智能体动态协作图建模多智能体任务中的近似可分解结构，并利用双层策略结构进行子任务分配. 之后提出子任务内和子任务间行为约束来增强智能体间局部和全局协作. 最后总结算法整体学习目标及流程.

3.1   图多智能体任务建模

本文提出智能体动态协作图建模多智能体任务中的近似可分解结构，其中节点代表智能体，节点间的边表示智能体间的交互关系. 如图2所示，对于一个6智能体任务，在某一时间步时，相同交互集合内智能体间交互强度大，而不同交互集合智能体间交互强度小，且智能体间交互关系随时间发生变化. 智能体动态协作图具体定义为：

图  2  一个6智能体任务在某一时间步的智能体动态协作图

Figure  2.  Agent dynamic coordination graph of a 6-agent task at certain timestep

下载: 全尺寸图片 幻灯片

定义1. 智能体动态协作图. 给定一个无向图$G=(N,\boldsymbol{E},T)$，其中$N$代表节点集合，$E_t\in\boldsymbol{E}$代表时间步$t \in T$时的边集合. 在节点集合$N$中，每个节点$i \in N$代表智能体实体. 对于任意2个智能体节点$i,j \in N$，如果在时间步$t$时2节点间存在边${e^{ij}} \in {E_t}$，则表示相应智能体$i$和$j$在当前时间步$t$存在交互关系，且边的权重代表智能体间的交互强度.

建模智能体动态协作图可以准确描述多智能体任务中智能体间的实时交互关系，并由此识别智能体交互集合. 此时，每一智能体在更新策略时需要更多考虑相同交互集合内其他强交互智能体信息，而较少考虑不同交互集合内弱交互智能体信息，由此提升智能体间协作策略的学习效率. 文献[38]所提的算法通过遍历所有成对智能体并考虑每一智能体对另一智能体局部状态转移和累积折扣回报的影响来衡量智能体间交互强度. 文献[23]所提的算法通过定义每个智能体在缺失另一个智能体子集协作时的效用损失来衡量其间交互强度. 然而，当多智能体任务中智能体数量过多时，该类算法遍历所有可能的智能体组合会导致复杂度较大，阻碍智能体协作策略高效学习.

为实现智能体动态协作图的高效建模，CSP算法使用子任务来识别智能体交互集合，并利用双层策略中的上层策略将智能体周期性地分配到预设的子任务中. 其中去集中式上层策略可以实现智能体去集中式子任务分配，由此克服之前算法需要遍历所有可能的智能体组合带来的可扩展性差的问题. 此外，上层策略可以利用时序抽象的任务回报实现子任务高效分配，从而最大化任务回报. 因此，CSP算法可以实现复杂多智能体任务中智能体交互集合的高效识别，由此近似刻画智能体动态协作图中智能体间交互关系.

3.2   双层策略结构

CSP算法为每个智能体i学习2部分策略：1）子任务分配策略${\beta ^i}:{\mathcal{T}^i} \to {C^i}$：基于智能体i局部动作-观测历史${\tau ^i} \in {\mathcal{T}^i}$选择子任务${c^i} \in {C^i}$；2）子任务执行策略${\pi ^i}:{\mathcal{T}^i},{C^i} \to {A^i}$：基于智能体i局部动作-观测历史${\tau ^i} \in {\mathcal{T}^i}$和所属子任务${c^i} \in {C^i}$输出原子动作${a^i} \in {A^i}$.

对于每个智能体i，CSP算法利用双层策略结构中的上层策略实现其子任务分配策略${\beta ^i}:{\mathcal{T}^i} \to {C^i}$，而子任务执行策略${\pi ^i}:{\mathcal{T}^i},{C^i} \to {A^i}$使用下层策略来实现. 当在多智能体任务中进行交互时，上层子任务分配策略${\beta ^i}$每隔k个时间步将智能体i分配到某一子任务${c^i} \in {C^i}$中；之后，智能体i遵循该子任务并利用下层子任务执行策略${\pi ^i}$选择并输出原子动作${a^i} \in {A^i}$.

3.2.1   子任务分配策略

为解决子任务空间未知问题，CSP算法引入参数m来指定子任务数量，并使用独热编码（one-hot encoding）表示子任务. 如图3所示，本文通过学习一个子任务效用函数${Q^{i,\,\beta }}({\tau ^i},c)$来实现每个智能体i的子任务分配策略${\beta ^i}$. ${Q^{i,\,\beta }}({\tau ^i},c)$以智能体i局部动作-观测历史作为输入并输出所有可能子任务$c \in {C^i}$相应的Q值. 每隔k个时间步，智能体i基于这些Q值选择子任务${c^i}$，并将其发送给下层子任务执行策略.

图  3  CSP算法结构

Figure  3.  Architecture of CSP algorithm

下载: 全尺寸图片 幻灯片

同时，为协调所有智能体的子任务分配策略，CSP算法引入一个混合网络${f^{\,\beta} }$，该混合网络根据所有智能体的子任务效用函数${Q^{i,\,\beta }}$来计算全局子任务值函数${Q^{{\rm total},\,\beta }}$，进而${Q^{i,\,\beta }}$可以通过${Q^{{\rm total},\,\beta }}$利用任务回报进行更新，其损失函数定义为：

其中${{\boldsymbol{c}}_t} = (c_t^1,c_t^2, … ,c_t^n)$表示时间步$t$所有智能体的联合子任务分配，而${\boldsymbol{c}}'$表示下一时间步$t + k$所有智能体的联合子任务分配. 相比下层策略，上层策略遵循更快的时间尺度，即每隔k个时间步执行1次子任务选择. ${\theta ^{\,\beta} }$和${\omega ^{\,\beta} }$分别代表${Q^{i,\,\beta }}$和混合网络${f^{\,\beta} }$的参数，并且所有智能体共享${Q^{i,\,\beta }}$网络参数. ${\bar Q^{{\rm total},\,\beta }}$表示一个周期性更新的目标全局子任务值函数. 此外，本文通过从经验回放池$\mathcal{D}$中采样数据来近似计算期望.

3.2.2   子任务执行策略

在接收到上层子任务分配策略输出的子任务${c^i}$后，智能体i在之后的k个时间步内遵循该子任务并利用下层子任务执行策略选择原子动作. 如图3（b）所示，CSP算法通过学习效用函数${Q^i}({\tau ^i},{c^i},{a^i})$来实现智能体i的子任务执行策略${\pi ^i}$. ${Q^i}({\tau ^i},{c^i},{a^i})$以智能体i局部动作-观测历史${\tau ^i}$和所属子任务${c^i}$为输入，输出所有可能原子动作${a^i} \in {A^i}$相应Q值并由此选择动作.

3.3   行为约束

仅将子任务${c^i}$作为每个智能体i子任务执行策略额外输入无法保证智能体间协作行为增强. 为解决该问题，CSP算法提出子任务内和子任务间行为约束来增强智能体间局部和全局协作.

3.3.1   子任务内行为约束

对于每个智能体$i$，本文使用$\mathcal{C}(i)$表示其所处子任务${c^i}$的智能体集合. 为增强$\mathcal{C}(i)$内智能体间局部协作，CSP算法对$\mathcal{C}(i)$内其余智能体$j \in \mathcal{C}(i),j \ne i$进行行为建模，并利用该行为信息辅助智能体$i$的子任务执行策略进行动作选择. 具体而言，CSP算法为每个智能体$i$学习一个队友建模函数${f^i}({\tau ^i},{d^j})$，其以智能体$i$动作-观测历史${\tau ^i}$和待建模队友编号${d^j}$为输入，输出一个多元高斯分布的均值${\mu ^{i,j}}$和方差${\sigma ^{i,j}}$. 随后，CSP算法从相应高斯分布$\mathcal{N}({\mu ^{i,j}};{\sigma ^{i,j}})$中采样变量${z^{i,j}}$作为智能体$i$对$\mathcal{C}(i)$内其他智能体$j$的行为表征.

为保证该变量${z^{i,j}}$能够准确刻画智能体$j$的策略信息，CSP算法最大化变量${z^{i,j}}$和智能体$j$的动作${a^j}$间互信息，该优化目标定义为：

其中$I( \cdot {\text{ }};{\text{ }} \cdot )$代表互信息，$H( \cdot )$代表信息熵. 直观来说，如果${z^{i,j}}$与${a^j}$相关性小，则${a^j}$无法提供${z^{i,j}}$相关信息，此时$H({z^{i,j}}|{\tau ^i},{d^j},{a^j})$衰退为$H({z^{i,j}}|{\tau ^i},{d^j})$，相应地，${z^{i,j}}$和${a^j}$间互信息$I({z^{i,j}};{a^j}|{\tau ^i},{d^j})$趋近于0. 相反，若两者间关联性大，$H({z^{i,j}}|{\tau ^i},{d^j},{a^j}) <$$H({z^{i,j}}|{\tau ^i},{d^j})$，导致$I({z^{i,j}};{a^j}|{\tau ^i},{d^j})$变大. 因此，通过最大化互信息$I({z^{i,j}};{a^j}|{\tau ^i},{d^j})$可以增强变量${z^{i,j}}$与智能体$j$的动作${a^j}$间的相关性，实现${z^{i,j}}$对${a^j}$的准确建模.

针对互信息项$I({z^{i,j}};{a^j}|{\tau ^i},{d^j})$，本文将其重写为：

其中$p({z^{i,j}}|{a^j},{\tau ^i},{d^j})$为未知条件概率分布. 本文引入变分概率分布${q^\phi }({z^{i,j}}|{a^j},{\tau ^i},{d^j})$对其近似：

由于队友建模函数${f^i}({\tau ^i},{d^j})$以${\tau ^i}$和${d^j}$作为输入来输出${z^{i,j}}$，因此当给定${\tau ^i},{d^j}$时${z^{i,j}}$与${a^j}$相独立，此时：

因此，本文定义损失函数作为子任务内行为约束：

其中${\theta ^{\rm team}}$表示队友建模函数${f^i}$的参数，$\phi$表示变分概率分布${q^\phi }$的参数. 通过优化该损失，每个智能体$i$可以通过变量${z^{i,j}}$实现对相同子任务集合$\mathcal{C}(i)$内其他智能体行为的准确建模. 随后对于每个智能体$i$，CSP算法合并其局部动作-观测历史${\tau ^i}$和相同子任务中其他智能体$j$相应${z^{i,j}}$来计算${Q^i}({\tau ^i},{c^i},{a^i})$. 通过行为建模，相同子任务内智能体间可以准确预知彼此动作选择，由此实现相同子任务内智能体间局部协作增强.

3.3.2   子任务间行为约束

对于子任务间智能体全局协作，之前算法根据任务回报学习全局动作值函数来实现该目标. 然而，当学习过程中智能体协作行为缺乏导致任务回报稀疏时，全局动作值函数学习效率低下，影响智能体间全局协作. 为解决该问题，CSP算法提出子任务间行为约束辅助全局动作值函数高效学习. 具体而言，CSP算法利用上层子任务分配策略每个决策间隔相应的时间差分误差（temporal difference error，TD-error）为下层子任务执行策略生成内在回报，其定义为：

其中$\delta _{t:t + k - 1}^{\,\beta}$表示上层智能体联合子任务分配策略在其单个决策间隔$(t,t + k - 1)$对应的TD-error，定义为：

其中各元素定义与式（4）相同. 根据式（10），对该决策间隔内的每个时间步$h \in \{t,t + k - 1\}$，CSP算法将$\delta _{t:t + k - 1}^{\,\beta}$按$k$等分，由此为下层智能体联合子任务执行策略生成每一个时间步的内在回报$r_h^{{\rm intrinsic} }$.

在CSP算法的双层策略结构中，相比下层策略，上层策略受益于较小的联合子任务空间以及时序抽象回报，因此上层策略可以在更大的决策尺度上识别下层策略学习进度. 当$\delta _{t:t + k - 1}^{\,\beta} \geqslant 0$时，其表示智能体下层联合策略在该时间间隔内执行了优异的联合原子动作并收到了较大任务回报，进而导致上层策略值函数的大幅度更新. 因此，本文利用上层策略的TD-error识别优异的下层联合原子动作并将其作为内在回报指导下层策略学习，有助于提升下层联合策略的学习效率，实现子任务间智能体全局协作增强.

3.4   总体学习目标

对于上层子任务分配策略，CSP算法根据式（4）对其进行更新. 对于下层子任务执行策略，CSP算法利用任务回报${r_t}$和内在回报$r_t^{{\rm intrinsic} }$对其进行更新，其相应损失函数定义为：

其中$\alpha$是一权重系数，$\theta$表示下层子任务执行策略相应效用函数${Q^i}({\tau ^i},{c^i},{a^i})$的参数（智能体间共享该效用函数参数）. 对于下层策略，CSP算法也利用一个混合网络$f$（参数为$\omega$）来组合所有智能体${Q^i}({\tau ^i},{c^i},{a^i})$得到全局动作值函数${Q^{\rm total}}({\boldsymbol{\tau }},{\boldsymbol{a}})$. ${{\boldsymbol{a}}_{t + 1}}$表示下一时间步$t + 1$所有智能体的联合原子动作，${{\boldsymbol{a}}_t}$表示当前时间步$t$所有智能体的联合原子动作. ${\bar Q^{\rm total}}$基于${Q^{\rm total}}$参数进行周期性更新. 基于经验回放池$\mathcal{D}$中样本，CSP算法利用式（12）实现对${Q^i}$以及$f$的更新.

总而言之，CSP算法的损失函数定义为：

其中$\lambda$表示权重系数. 通过优化式（13）损失函数，CSP算法实现相同子任务内和不同子任务间智能体局部和全局协作增强，从而提升智能体策略学习效率.

CSP算法运行流程如算法1所示. CSP算法首先需要初始化参数设置以及各模块网络参数，然后行①~②表示每一智能体利用双层策略与多智能体任务环境交互采集数据并存放到经验回放池$\mathcal{D}$中，其中上层策略每隔$k$个时间步为智能体$i$分配子任务${c^i}$，下层策略接收${c^i}$作为额外输入选择原子动作$a_t^i$输出. 行②~⑤表示当训练回合开始时，CSP算法从经验回放池$\mathcal{D}$随机采样批训练数据$\mathcal{B}$，随后基于$\mathcal{B}$利用式（13）计算损失函数$\mathcal{L}$，最终利用梯度下降方法对相关模块参数进行更新. 以上流程重复进行，直到算法运行回合数满足预设最大回合数终止.

算法1. CSP算法.

输入：初始化算法参数设置、各模块参数；

输出：所有智能体去集中式策略.

① while 未完成最大训练回合数时

②　for 每个回合中的每一个时间步$t$

③　　for 每一智能体$i$

④　　If $t\%\ k=0$

⑤　　利用子任务分配策略${\beta ^i}$选择${c^i}$；

⑥　　利用子任务执行策略${\pi ^i}$选择$a_t^i$；

⑦　　end if

⑧　　end for

⑨　end for

⑩　采集数据存入$\mathcal{D}$中；

⑪　If 训练回合

⑫　从$\mathcal{D}$中随机采样批训练数据$\mathcal{B}$；

⑬　根据式（13）计算损失函数$\mathcal{L}$；

⑭　利用梯度下降更新相关模块参数；

⑮　end if

⑯ end while

4.   实　　验

在本节中，我们设计实验来回答2个问题：1）CSP算法是否可以通过增强智能体间局部和全局协作来提升智能体协作策略学习效率（见4.2节）；2）如果CSP算法能够实现协作策略的高效学习，那么哪个模块对其性能提升贡献较大？（见4.3节）. 此外，本节对实验中所采用的测试任务、对比算法以及算法参数设置给予简要概述（见4.1节和4.4节）.

4.1   测试任务和对比算法

为测试算法有效性，本文在星际争霸^[37]环境（SMAC）的多个地图上将CSP算法与多个基准算法进行比较. 测试任务场景和基准算法的简要描述如下.

4.1.1   测试任务

在星际争霸环境中，本文选择6个作战地图3s5z、1c3s5z、3s_vs_5z、5m_vs_6m、2c_vs_64zg和MMM2作为测试任务. 这些任务包含2方单元，其中友方单元由本文算法控制，而敌方单元由内置规则控制. 友方单元需要协作击杀敌方单元来获胜. 这些地图根据友方和敌方单元配置被划分为容易、困难和超级困难3种难度，本文在表1中对这些地图进行概述.

表  1  星际争霸环境下选用地图的描述

Table  1.  Descriptions of Selected Maps in SMAC

地图信息	难度	作战单元配置
3s5z	简单	友方：3 Stalkers, 5 Zealots 敌方：3 Stalkers, 5 Zealots
1c3s5z	简单	友方：1 Colossus, 3 Stalkers, 5 Zealots 敌方：1 Colossus, 3 Stalkers, 5 Zealots
3s_vs_5z	困难	友方：3 Stalkers 敌方：5 Zealots
5m_vs_6m	困难	友方：5 Marines 敌方：6 Marines
2c_vs_64zg	困难	友方：2 Colossi 敌方：64 Zerglings
MMM2	超级困难	友方：1 Medivac, 2 Marauders, 7 Marines 敌方：1 Medivac, 3 Marauders, 8 Marines

下载: 导出CSV 

| 显示表格

4.1.2   基准算法

为回答问题1，本文将以下6个算法作为基准算法.

1）GoMARL^[27]. 该算法通过学习分组效用值函数对智能体进行动态分组，同时鼓励智能体生成组内相似、组间差异的分组表征以及相应策略参数，由此增强相同分组内智能体间的局部协作.

2）LDSA^[33]. 该算法学习差异化子任务向量表征，并将子任务策略定义在其相应表征上，由此实现相同子任务内智能体间局部协作增强.

3）ROMA^[31]. 该算法基于智能体局部动作-观测历史轨迹生成角色，并为行为相似的智能体生成相似角色变量来实现智能体间局部协作增强.

4）RODE_ND. RODE^[32]基于动作语义划分角色，并利用双层策略结构实现角色分配. 然而，该算法需要利用任务先验知识来实现角色有效划分（例如在星际争霸中，RODE强制将6个移动相关动作包含在所有角色中）. 本文通过移除该操作来验证其通用性.

5）MAVEN^[39]. 该算法在回合开始时生成一个全局变量并约束所有智能体生成相应联合轨迹，由此实现智能体联合行为多样化. 该算法忽视智能体间局部协作，直接在智能体联合动作空间开展全局协作，本文将其作为基准算法来验证刻画局部协作的必要性.

6）QMIX^[11]. 该算法通过学习可分解的全局动作值函数来更新智能体去集中式效用函数（策略），并未显式刻画智能体间局部协作结构. 因此本文也将其作为基准算法来验证刻画智能体间局部协作的必要性.

4.2   对比实验结果

CSP算法与以上基准算法的对比实验结果如图4所示. 具体而言，CSP算法在地图2c_vs_64zg，MMM2以及5m_vs_6m上明显优于其他基准算法，并且在其他地图3s5z、1c3s5z和3s_vs_5z上也表现出优异性能. 相比之下，LDSA算法尽管可以在地图3s5z、1c3s5z和3s_vs_5z上学习到有效策略击败敌方单元并实现较高的测试胜率，但是其性能仍弱于CSP算法.

图  4  星际争霸环境6个地图上本文算法与多个基准算法的对比结果

注：图中实线代表5个随机种子设定下所有算法的平均测试胜率，而阴影区域代表标准差.

Figure  4.  Comparison results of our algorithm against multiple baselines on six maps in SMAC

下载: 全尺寸图片 幻灯片

因为LDSA算法仅根据任务回报学习全局动作值函数来保证智能体间全局协作，所以这一结果验证了有效增强智能体间全局协作有利于提升智能体协作策略学习效率. 在困难地图2c_vs_64zg、5m_vs_6m和超级困难地图MMM2下，地图难度大导致联合协作动作较难出现，因此任务回报稀疏. 此时LDSA算法仅利用全局动作值函数保证智能体间全局协作的做法无法令其快速学习到有效的协作策略. 这一结果进一步验证了高效增强智能体间全局协作的必要性.

QMIX算法通过学习可分解的全局动作值函数来直接实现智能体间的全局协作，并且在地图3s5z、1c3s5z和3s_vs_5z上表现出优异性能. 这可能归因于QMIX算法提出的混合网络能够实现隐式的信度分配，由此隐式刻画智能体交互集合并实现智能体间局部协作增强. 然而，QMIX算法对于智能体局部协作的隐式刻画严重依赖于任务回报，当任务难度较大导致任务回报稀疏时，其难以生效. QMIX算法在地图2c_vs_64zg、MMM2以及5m_vs_6m下的实验学习效率低下验证了这一观点.

GoMARL算法通过学习分组效用值函数对智能体进行分组，同时鼓励智能体生成组内相似、组间差异的分组信息和策略参数以增强相同分组内智能体间局部协作. 然而，该算法仍然依赖于任务回报学习全局动作值函数以实现智能体间全局协作. 当任务回报稠密时，该算法可以高效学习分组效用值函数和全局动作值函数，由此提升智能体协作策略学习效率，因此在地图3s5z，1c3s5z下可以快速学习到有效策略并实现较高胜率. 然而，当地图难度大导致任务回报稀疏时，这些值函数无法有效更新，导致智能体间局部和全局协作效率低下，因此GoMARL算法在地图3s_vs_5z、5m_vs_6m和MMM2上表现较差. 此外，GoMARL算法在地图2c_vs_64zg上优于LDSA算法与QMIX算法，这可能是因为该算法通过学习分组效用值函数能够为智能体实现更优的信度分配，由此提升智能体协作策略学习效率.

MAVEN和ROMA算法在所有地图上都无法实现策略的高效学习. 这可能是因为MAVEN中提出的全局行为多样化约束和ROMA中提出的局部协作约束与原始任务目标冲突，导致智能体策略优化偏移任务目标，无法实现智能体间高效协作. RODE_ND算法同样无法学习到有效策略实现较高测试胜率，这一结果表明RODE算法严重依赖于任务先验知识，当任务先验知识不可用时，其无法实现有效的角色划分.

4.3   消融实验结果

针对问题2，本节开展消融实验来评估CSP算法中各模块对其性能的影响，这些模块包括：子任务内行为约束、子任务间行为约束、双层策略结构、预设子任务数量和子任务分配间隔. 对于前3个模块，本文引入以下基准算法对其影响进行评估：

1）CSP_L. 该基准算法通过移除子任务间行为约束（即设置$\alpha=0$将$r_t^{{\rm intrinsic} }$从式（12）中去除）来评估子任务间行为约束对于CSP算法性能的影响.

2）CSP_G. 该基准算法通过去除子任务内行为约束${\mathcal{L}_{{\rm local} }}$来评估其对CSP算法性能的影响.

3）CSP_H. 该基准算法同时去除${\mathcal{L}_{{\rm local} }}$和$r_t^{{\rm intrinsic} }$来评估CSP算法性能提升是否归因于双层策略结构.

本文在地图3s5z和2c_vs_64zg上将CSP算法与以上基准算法进行比较，实验结果如图5（a）（b）所示. 在地图3s5z上，CSP_G算法性能明显弱于CSP算法，这一结果表明子任务内行为约束可以通过建模其他智能体行为来提升子任务内智能体间协作，移除该约束会导致协作策略学习效率低下. CSP_L算法性能介于CSP和CSP_G之间，表明通过子任务间行为约束增强智能体间全局协作可以有效提升协作策略学习效率. 值得注意的是CSP_G和CSP_H性能相近，这可能是因为3s5z难度较低导致任务回报稠密，此时全局动作值函数可以被高效学习来增强智能体间全局协作，因此子任务间的行为约束效果并不显著.

图  5  地图3s5z和2c_vs_64zg下CSP算法主要模块的消融实验

注：图中实线代表5个随机种子设定下所有算法的平均测试胜率，而阴影区域代表标准差.

Figure  5.  Ablation studies regarding major modules of CSP algorithm on maps of 3s5z and 2c_vs_64zg

下载: 全尺寸图片 幻灯片

在地图2c_vs_64zg下，CSP_G算法性能略弱于CSP算法，表明当智能体数量较少时，利用子任务内行为约束实现智能体行为建模作用较小. CSP_L算法性能相较CSP算法明显下降，表明子任务间行为约束对算法实现协作策略高效学习具有重要影响. 相比之下，CSP_H算法效果最弱，表明CSP算法性能提升主要归因于所提出的子任务内和子任务间的行为约束，而非双层策略结构.

对于预设子任务数量和子任务分配间隔模块，本文将CSP算法中的子任务数量参数$m$设置为3，5，7，子任务分配间隔参数$k$设置为3，5，7，10，其他模块保持不变. 在这些参数设置下，本文在地图3s5z和2c_vs_64zg下运行CSP算法. 如图5（c）~（f）所示，当地图中智能体数量较多时，CSP算法在$m = 5$时效果较优；当地图中智能体数量较少时，CSP算法在$m = 3$时效果较优. 此外，CSP算法在$k = 5$时效果稳定且较优. 因此，本文在所有地图下默认设置$m \leqslant 5$以及 $k = 5$，如表2所示.

表  2  所有地图下CSP算法超参数设置

Table  2.  Hyper-Parameter Settings for CSP Algorithm on All Maps

地图	$m$	$k$	$\alpha$	$\lambda$
3s5z	5	5	0.001	1.0
1c3s5z	3	5	0.001	1.0
2c_vs_64zg	3	5	0.001	1.0
3s_vs_5z	3	5	0.001	1.0
5m_vs_6m	3	5	0.001	1.0
MMM2	3	5	0.001	0.1

下载: 导出CSV 

| 显示表格

4.4   算法参数设置

对于基准算法，本文利用其论文中的开源代码来开展实验，其中算法参数已经在星际争霸环境下微调. 本文基于PyMARL^[37]框架实现所有算法以保证算法间的公平对比. 对于CSP算法，实验所用服务器包括一台配置为2×22-core Intel^® Xeon^® Gold 6238 CPUs、512 GB RAM, 8 NVIDIA GTX2080Ti GPUs的服务器和一台配置2×12-core Intel^® Xeon^® CPU E5-2650 v4 CPUs、256 GB RAM、8 NVIDIA GTX1080Ti GPUs的服务器.

5.   结　　论

本文使用动态图来建模多智能体任务中广泛存在的近似可分解结构并提出协作子任务行为算法来实现智能体间高效协作. 该算法利用子任务来识别智能体交互集合，并提出子任务内和子任务间行为约束来实现智能体间局部和全局协作增强. 星际争霸下的对比实验验证了本文算法能够有效提升智能体协作策略学习效率，消融实验验证了所提约束的有效性.

未来工作主要包括3个方面：

1）本文所提智能体动态协作图可以有效刻画多智能体任务中的近似可分解结构. 未来工作将尝试使用子图分割算法、图信息传递等技术来实现智能体动态协作图的高效建模，进而提升智能体协作效率.

2）本文算法需要预设子任务数量，其中子任务并无实际意义且引入额外的算法参数. 未来工作将尝试利用计算机视觉领域的语义分割模型来识别多智能体任务中已有实体，并将部分实体作为子任务，由此利用实体相关信息指导子任务内智能体协作.

3）本文算法依靠双层策略结构实现子任务分配策略和子任务执行策略学习. 然而，上下层策略同时更新会导致非稳态问题并影响策略学习. 未来工作将聚焦于预训练智能体间局部协作策略，随后将其固定作为下层子任务执行策略并单独学习上层子任务分配策略来实现具体多智能体任务中的协作策略学习.

作者贡献声明：李超提出算法思路，完成实验并撰写论文；李文斌和高阳提出指导意见并修改论文.