-
摘要:
随着人们越来越倾向于使用即时通讯软件进行交流，保障群聊中消息的安全性成为一个亟需解决的问题. 因此，基于国密SM9算法提出了一种基于身份的群组密钥分发方案，并进行了严格的安全性证明；提出的方案相较于Guo等人、Meng等人提出的方案在便捷性和兼容性上更具优势，同时，相较于Wu等人在欧密会上提出的非对称群组密钥协商协议也有群组密钥管理和兼容性方面的优势. 此外，还给出了所提方案在即时通讯群聊及点对点通信场景下的应用示范，进一步证明了所提方案在通信开销和密钥管理方面要优于目前典型即时聊天软件中的安全群聊实现方法.
Abstract:As people are increasingly inclined to use instant messaging software for communication, ensuring the security of messages in group chats has become an urgent issue. Therefore, we propose an identity-based group key distribution scheme based on the national cryptographic algorithm SM9 and provide rigorous security proofs. The proposed scheme has advantages over the ones introduced by Guo et al. and Meng et al. in terms of convenience and compatibility. Additionally, our scheme outperforms the asymmetric group key agreement protocol proposed by Wu et al. at the Eurocrypt in terms of group key management and compatibility. Furthermore, we provide application demonstrations of the proposed scheme in both instant messaging group chats and peer-to-peer communication scenarios, further proving that the proposed scheme outperforms current typical secure group chat implementation methods in terms of communication overhead and key management in instant messaging software.
-
强化学习（reinforcement learning, RL）作为一种机器学习方法，其主要思想是使智能体通过最大化从环境中获得的累积奖励来学习最优策略. Q-learning是单智能体强化学习领域中的经典方法之一，但其难以应对动作空间和状态空间维数较高的环境. 深度Q网络（deep Q-network, DQN）利用深度神经网络逼近价值函数来解决这个困难. 得益于DQN在高维空间中展现出的优越性能，学者们基于此方法提出诸多深度强化学习（deep reinforcement learning, DRL）[1-4]方法.
随着DRL在机器控制[5-7]、人机游戏[8-10]等单智能体领域取得显著成功，许多工作将单智能体DRL方法扩展到多智能体设置并应用到真实环境中，如自动驾驶[11-12]、交通控制[13-14]. 然而，实现高效的多智能体强化学习通常会面临2个主要困难：可扩展性问题和部分可观测性限制. 一方面，利用环境的所有信息进行决策可能会导致大规模的联合状态动作空间. 随着智能体的数量增加，状态动作空间规模将呈指数增长，这导致智能体的规模难以扩展，即产生可扩展性问题. 另一方面，部分可观测性限制要求智能体只根据自己的局部观测历史来选择动作和做出决策. 这虽然提高了决策效率，但也严重限制智能体探索最优动作的能力，同时造成了环境的不稳定性.
为应对部分可观测性限制带来的问题，Lowe等人[15]提出了多智能体深度确定性策略梯度（multi-agent deep deterministic policy gradient, MADDPG）方法. 该方法引入集中训练和分散执行（centralized training with decentralized execution, CTDE）框架：在集中训练阶段，智能体可以访问全局信息；在分散执行阶段智能体只根据局部观测历史选择动作[16-18]. 随着MADDPG方法在应对部分可观测限制情况时展现出的优越性能，基于CTDE框架的多智能体强化学习（multi-agent reinforcement learning, MARL）方法不断涌现，CTDE框架也成为MARL中最常用的框架之一. 此外，为了解决CTDE范式的可扩展性问题，学者们提出了各种价值函数分解方法[19-22].
尽管MADDPG已成为MARL中最常用的基线方法之一，以MADDPG为代表的CTDE方法存在的Q值高估问题没有得到广泛研究. Q值高估问题源于bootstrapping目标中常用的max算子. 具体地，Q-learning中的max算子用最大估计值逼近最大期望值，这将导致价值高估：E[max，其中 {X_{{a_i}}} 表示给定状态下动作{a_i}的Q值的随机变量. Q值高估问题会损害智能体的行为，导致智能体学得次优的策略[23-24].
在CTDE方法中，Q值高估问题同样存在. 具体地，假设有{\kern 1pt} n个智能体，每个智能体有 {\kern 1pt} L{\kern 1pt} 个动作，每个动作的Q值独立地由均匀分布U（0,1）得到，则{\max _{{a_i}}}E[{X_{{a_i}}}] = 1/2.同时 E[{\max _{{a_i}}}{X_{{a_i}}}] = {L^n}/({L^n} + 1 )，由于联合动作空间的大小 {\kern 1pt} L{\kern 1pt} 随智能体的数量呈指数增长， E[{\max _{{a_i}}}{X_{{a_i}}}] 趋向于1，且大于 {\max _{{a_i}}}E[{X_{{a_i}}}] ，由此可得CTDE方法存在Q值高估问题. 在CTDE方法中，个体智能体的决策质量取决于集中训练的评论家网络，评论家网络的价值函数高估问题可能会造成更严重的影响. 因此，研究MADDPG为代表的CTDE方法中存在的价值高估问题显得尤为必要和具有挑战性.
为应对这个挑战，本文提出基于双评论家的多智能体深度确定性策略梯度（multi-agent deep deterministic policy gradient method based on double critics, MADDPG-DC）方法来避免价值函数的过高估计. 本文的核心思想是通过在双评论家网络上的最小值操作来避免价值高估. 此外，为保证学习的稳定性和效率，本文采用延迟策略更新技术. 通过延迟行动者网络更新，减少了使用没变化的评论家网络得到的Q值来指导行动者网络重复更新的可能性，从而实现更高质量的策略更新. 本文的主要贡献和创新点有3点：
1） 从理论和实验层面上分别证明了MADDPG-DC存在严重的高估问题，并通过引入双评论家网络结构避免价值高估，从而促进更好的策略学习.
2） 为保证策略学习的效率和稳定性，在提出的MADDPG-DC中引入延迟行动者网络更新的方法，进一步提高策略更新的质量，使智能体更高效地学习最优策略.
3） 在多智能体粒子环境和交通信号控制环境上对所提出的MADDPG-DC方法进行了实验评估，实验结果表明提出的方法在仿真环境和实际系统上都具有可行性和优越性.
1. 基础理论
1.1 Dec-POMDP
MARL问题一般建模为去中心化部分可观测马尔可夫决策过程（decentralized partially observable Markov decision process, Dec-POMDPs）[25]. 具体地，Dec-POMDPs用元组{\kern 1pt} G = \langle S,A,P,R,O,n,\gamma \rangle 表示，其中部分可观测环境的状态记为{\kern 1pt} s \in S{\kern 1pt} ，智能体{\kern 1pt} i{\kern 1pt} 可获得的局部观测值记为{\kern 1pt} {o_i} \in O{{\kern 1pt} _i}. 智能体{\kern 1pt} {\kern 1pt} i{\kern 1pt} 根据其局部观测值{o_i}决定其动作{\kern 1pt} {a_i} \in A{\kern 1pt} , 联合动作表示为{\kern 1pt} a = ({a_1},{a_2},…,{a_N}) \in A{\kern 1pt},环境状态基于状态转移函数{\kern 1pt} P:S \times A \to S和联合动作转移至下一个状态. 智能体{\kern 1pt} i{\kern 1pt} 的学习目标是最大化其累计折扣奖励值{R_i} = \displaystyle\sum _{t = 0}^T{\gamma\;^t}r_i\;^t，其中{\kern 1pt} \gamma \in [0,1]{\kern 1pt} 为折扣因子， r_i\;^t 表示智能体{\kern 1pt} i{\kern 1pt} 在时间步{\kern 1pt} t获得的奖励值.
1.2 多智能体深度确定性策略梯度
MADDPG方法的关键思想是：在训练阶段，每个智能体都接收全局信息来学习一个集中的Q函数；在执行阶段，每个智能体只使用局部信息来选择动作. MADDPG利用CTDE框架与行动者-评论家结构，其中集中训练的评论家网络获得了全局信息，而分散的行动者网络只能获得个体的局部观测历史.
具体地，假设一个包含 {\kern 1pt} N{\kern 1pt} 个智能体的环境，智能体的策略是连续的，用\mu = \{ {\mu _1},{\mu _2},…,{\mu _N}\}表示，策略的参数是\varphi = \{ {\varphi _1},{\varphi _2},…,{\varphi _N}\}，智能体{\kern 1pt} i{\kern 1pt} 的策略梯度J({\varphi _i}) = E[{R_i}]表示为
{\nabla _{{\varphi _i}}}J({\varphi _i}) = {E_{o,a \sim D}}[{\mu _i}({o_i})\nabla {a_i}Q_i^\mu (o,a)\left| {{a_i} = {\mu _i}({o_i})} \right.] \text{，} (1) 其中 Q_i^\mu (o,a) 是智能体{\kern 1pt} i{\kern 1pt} 的价值函数，函数的输入是全部智能体的联合动作 a = ({a_1},{a_2},…,{a_N}) 和观测信息 o = ({o_1},{o_2},…,{o_N}) ，输出是Q值. 经验回放池 {\kern 1pt} D{\kern 1pt} 由元组(o,o',{a_1},{a_2},…,{a_N},{r_1},{r_2},…,{r_N})组成，记录所有智能体的历史样本. 价值函数通过目标函数进行更新：
L({\varphi _i}) = {E_{o,a,r,o'}}{[Q_i^\mu (o,a) - y]^2} \text{，} (2) \left. {y = {r_i} + \gamma Q_i^{\mu '}(o',a')} \right|{a'_j} = {\mu '_j}({o_j})\text{，} (3) 其中\mu ' = \{ {\mu _{{{\varphi }_1'}}},{\mu _{{{\varphi }_2'}}}…,{\mu _{{{\varphi }_N'}}}\}是目标策略的集合. 值得注意的是，集中的评论家网络只在训练阶段使用，而在分散执行阶段，每个智能体只使用本地信息{o_i}和行动者网络{\mu _{{{\varphi }_i'}}}作出决策.
2. MADDPG-DC方法
在本节中，首先通过理论和实验证明，MADDPG存在过高估计价值函数的问题，然后介绍提出的改进方法，即基于双评论家网络的多智能体深度确定性策略梯度方法.
2.1 MADDPG中的价值函数高估问题
首先，给出理论证明以论证MADDPG中存在价值函数的过高估计问题. 定义策略参数 \varphi ，\varphi _i^{{\rm{ap}}}表示智能体{\kern 1pt} i{\kern 1pt} 的由对应评论家网络 Q_i^\theta (o,a) 指导的行动者网络的近似参数，并用\varphi _i^{{\rm{tr}}}表示由真实价值函数 Q_i^\mu (o,a) 指导的行动者网络的参数：
\varphi _i^{{\rm{ap}}}{\text{ = }}\varphi + \frac{\alpha }{{{Z_1}}}E[{\nabla _\varphi }{\mu _\varphi }({o_i})\nabla {a_i}Q_i^\theta (o,a)\left| {{a_i} = {\mu _\varphi }({o_i})} \right.] \text{，} (4) \varphi _i^{{\rm{tr}}}{\text{ = }}\varphi + \frac{\alpha }{{{Z_2}}}E[{\nabla _\varphi }{\mu _\varphi }({o_i})\nabla {a_i}Q_i^\mu (o,a)\left| {{a_i} = {\mu _\varphi }({o_i})} \right.] . (5) 然后，根据参数\varphi _i^{{\rm{ap}}}和参数\varphi _i^{{\rm{tr}}}定义最优策略{\mu _{{\rm{ap}}}}和{\mu _{{\rm{tr}}}}. 由于策略梯度是局部最大化操作，于是存在一个足够小的 {\varepsilon _1} ，当 \alpha \leqslant {\varepsilon _1} 时，{\mu _{{\rm{ap}}}}的近似值以{\mu _{{\rm{tr}}}}的近似值为下界.
E[Q_i^\theta (o,a)\left| {{a_i} = {\mu _{{\rm{ap}}}}({o_i})} \right.] \geqslant E[Q_i^\theta (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.]. (6) 相反，存在一个足够小的 {\varepsilon _2} ，当 \alpha \leqslant {\varepsilon _2} 时{\mu _{{\rm{ap}}}}的真实值以{\mu _{{\rm{tr}}}}的真实值为上界.
E[Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.] \geqslant E[Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\rm{ap}}}}({o_i})} \right.]. (7) 又因为价值估计的期望不小于对应的真实策略{\mu _{{\rm{tr}}}}的真实值的期望：
E[Q_i^\theta (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.] \geqslant E[Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.]. (8) 因此存在足够小的 {\varepsilon _1} 和 {\varepsilon _2} ，当 \alpha \leqslant \min ({\varepsilon _1},{\varepsilon _2}) 时，MADDPG中的价值函数会被高估:
\begin{split}& E[Q_i^\theta (o,a)\left| {{a_i} = {\mu _{{\rm{ap}}}}({o_i})} \right.] \geqslant E[Q_i^\theta (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.] \geqslant \\& E[Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\rm{tr}}}}({o_i})} \right.] \geqslant E[Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\rm{ap}}}}({o_i})} \right.]. \end{split} (9) 2.2 MADDPG-DC
MADDPG中存在的价值函数过高估计一般会导致2个问题：一方面，价值高估会在多次更新后导致显著的偏差；另一方面，价值估计偏差会进一步导致策略更新的不准确. 评论家网络对次优动作进行过高的评估，从而导致在接下来的策略更新中引导行动者网络对次优动作的选择.
在降低单智能体深度强化学习中的价值函数过高估计问题方面，已有多项工作取得了成功，其中深度双Q网络采用目标值网络和当前值网络结构来进行独立的价值估计，利用当前值网络的价值估计来选择最优动作，利用目标值网络的价值估计来评估最优动作，将最优动作的选择和价值估计分开，降低了对次优动作过高估计价值的可能性[2].
MADDPG方法中的评论家网络也采取相似的目标值网络和当前值网络结构进行更新：
{y_i} = {r_i} + \gamma \left. {Q_i^{{{\theta '}_i}}(o',a)} \right|{a_i} = {\mu _{{\varphi _i}}}({o'_i}) . (10) 然而，由于MADDPG方法的策略变化缓慢，导致目标值网络与当前值网络过于相似，难以进行有效的独立的价值估计，过高估计的问题仍然存在. 如图1所示，本文实验评估了MADDPG中存在的估计偏差问题.
![]()
图 1 MADDPG和MADDPG-DC的估计偏差对比Figure 1. Comparison of estimation biases for MADDPG and MADDPG-DC在多智能体粒子环境（multi-agent particle environment）中的捕食者猎物（predator-prey）环境上，测量MADDPG和MADDPG-DC在学习过程中的价值估计的估计偏差、采样状态和经验回放池的动作，确定真实的和估计的Q值. 结果如图1所示，一个非常明显的过高估计偏差发生在MADDPG的学习过程中，而MADDPG-DC在学习过程中不存在明显的估计偏差.
MADDPG-DC使用双评论家网络结构来避免价值高估，2个评论家网络的目标函数分别为
{y_{i,1}} = {r_i} + \gamma \left. {Q_i^{{{\theta '}_{i,1}}}(o',a)} \right|{a_i} = {\mu _{{\varphi _{i,1}}}}({o'_i}) \text{，} (11) {y_{i,2}} = {r_i} + \gamma \left. {Q_i^{{{\theta '}_{i,2}}}(o',a)} \right|{a_i} = {\mu _{{\varphi _{i,2}}}}({o'_i}) . (12) MADDPG-DC通过在双评论家网络上进行最小值操作，能够避免价值估计过高的问题. 虽然该更新规则可能会导致价值低估，但价值低估不会在策略更新过程中显式传播[26-28]. MADDPG-DC方法的评论家网络的目标函数为
{y_i} = {r_i} + \gamma \mathop {\min }\limits_{k = 1,2} \left. {Q_i^{{{\theta '}_{i,k}}}(o',a)} \right|{a_i} = {\mu _{{\varphi _{i,k}}}}({o'_i}) . (13) MADDPG-DC方法利用目标网络来减少目标更新过程中的误差. 由于高误差状态下的策略更新会导致智能体动作的发散，MADDPG-DC方法引入延迟行动者网络更新的方法，将行动者网络的更新频率设置为低于评论家网络的更新频率，以使得行动者网络的策略更新前的误差最小化. 具体地，设定评论家网络每更新3次后，行动者网络更新1次. 同时为确保误差最小，缓慢地更新目标网络：
{\theta '_{i,k}} \leftarrow \tau {\theta _{i,k}} + (1 - \tau ){\theta '_{i,k}} \text{，} (14) {\varphi '_i} \leftarrow \tau {\varphi _i} + (1 - \tau ){\varphi '_i} . (15) 在评论家网络每3次迭代后，对于智能体{\kern 1pt} i{\kern 1pt} ，基于评论家网络 Q_i^{{\theta _i}} 利用确定性策略梯度方法更新行动者网络 {\mu _{{\varphi _i}}} . 通过延迟行动者网络更新，MADDPG-DC方法减少了使用没变化的评论家网络得到的Q值来指导行动者网络重复更新的可能性，从而实现更高质量的策略更新.
图2展示了MADDPG-DC的网络结构，在训练阶段，只对行动者网络和双评论家网络进行训练，而行动者目标网络和评论家目标网络用于稳定行动者网络和双评论家网络的学习效果. 算法1给出了MADDPG-DC的伪代码.
算法1. MADDPG-DC.
输入：每个智能体 {\kern 1pt} i{\kern 1pt} 的观测 {\kern 1pt} {o_i}{\kern 1pt} , 奖励函数 R ；
输出：评论家和行动者目标网络参数.
初始化：每个智能体 {\kern 1pt} i{\kern 1pt} 的评论家网络 Q_i^{{\theta _1}} , Q_i^{{\theta _2}} ；行动者网络 \mu _i^\varphi ；经验回放池 D .
① for 回合数 = 1 to M （最大回合数）
② for 时间步数 = 1 to T （最大时间步数）
③ for 智能体 {\kern 1pt} i{\kern 1pt}
④ 接收本地局部观测{\kern 1pt} {o_i}；
⑤ 根据策略网络选择动作 {a_i} \sim \mu _i^\varphi ({\kern 1pt} {\kern 1pt} {o_i}{\kern 1pt} ) ；
⑥ 接收奖励值{r_i}和新的局部观测{\kern 1pt} {o'_i}；
⑦ 存储历史样本({o_i},{a_i},{r_i},{o'_i})到 D ；
⑧ 从 D 中抽取小批量样本 S 用于训练；
⑨ 最小化目标函数来更新评论家网络：
L({\theta _{i,k}}) = {S^{ - 1}}\displaystyle\sum {({y_i} - } Q_i^{{{\theta '}_{i,k}}}(o',a){)^2}；
⑩ for 时间步数 mod 3
⑪ 更新行动者网络 {\varphi _{i,k}} ： {\nabla _{{\varphi _i}}}J({\varphi _i}) = {S^{ - 1}}\displaystyle\sum [{\mu _{{\varphi _i}}}({o_i})\nabla {a_i} Q_i^\mu (o,a)\left| {{a_i} = {\mu _{{\varphi _i}}}({o_i})} \right.]；
⑫ 更新评论家目标网络和行动者 目标网络： {\theta '_{i,k}} \leftarrow \tau {\theta _{i,k}} + (1 - \tau ){\theta '_{i,k}} ， {\varphi '_i} \leftarrow \tau {\varphi _i} + (1 - \tau ){\varphi '_i} ；
⑬ end for
⑭ end for
⑮ end for
⑯ end for
2.3 方法复杂度分析
MADDPG-DC方法使用神经网络来促进评论家的训练，其中神经网络使用多层感知器（multilayer perceptron, MLP）架构. 首先，对于使用MLP架构的单智能体强化学习方法而言，其训练复杂度是O(M \times T(S \times H + H \times A)). 其中 M 为回合数， T 是每回合的时间步数； S 表示输入层的大小，也表示智能体的观测集合的大小， H 表示神经网络隐藏层的大小； A 表示输出层的大小，也表示智能体的动作集合的大小.
对于MADDPG-DC的训练阶段，每个评论家网络用单一的值来评估多个智能体的联合动作和观测结果，其复杂度为 O(M \times T(N \times (A + S) \times H + H \times 1)) , N 表示智能体的数量. 在执行阶段的复杂度方面，由于每个智能体都是独立行动，不需要评论家网络和其他智能体的交互，因此每个智能体在给定时间步数上执行1个动作的复杂度为 O(S \times H + H \times A) . MADDPG方法的复杂度与MADDPG-DC一致.
3. 实验结果
本节在各种复杂的平台和任务上进行了实验，以验证MADDPG-DC方法的优越性和有效性. 首先在MARL领域中广泛使用的多智能体粒子环境进行了仿真实验；然后在交通信号控制环境的真实系统中评估MADDPG-DC方法，以证明该方法在真实环境中应用的可行性.
3.1 多智能体粒子环境
首先使用MARL中常用的多智能体粒子环境进行实验. 实验配置如表1所示. 环境是2维连续的，包含K个相互协作的智能体、Z个地标和L个敌对的智能体. 本文在多智能体粒子环境中的3个环境上进行了实验，以验证所提方法的有效性.
表 1 多智能体粒子环境的实验配置Table 1. Experimental Configuration for Multi-Agent Particle Environments环境 动作维度 状态维度 观测维度 （K, Z, L） 捕食-猎物 5 16 62 （3, 1, 2） 物理欺骗 5 10 28 （2, 1, 2） 世界 5 34 200 （4, 2, 1） 1）捕食者-猎物环境. 如图3所示，这个环境包含了3个合作的捕食者，即智能体1，2，3；1个移动速度更快的猎物，即敌方智能体和2个阻碍前进的障碍. 捕食者需要协作来追赶猎物，如果捕食者成功捕获猎物，捕食者得到奖励，而猎物得到惩罚.
![]()
图 3 多智能体粒子环境的场景示例：捕食者-猎物Figure 3. Example of scenario for the multi-agent particle environment: predator-prey2）物理欺骗（physical deception）环境. 该环境包括2个合作的智能体、1个敌对的智能体和2个地标物体. 2个合作智能体的目标是在敌对智能体不知道地标物体的情况下，从一个地标到达另一个地标. 合作智能体的奖励取决于其中一个智能体到达目的地的最小距离.
3）世界（world）环境. 在包含4个移动较慢的智能体和2个移动较快的敌对智能体的世界环境中，较慢的智能体的目标是学会合作以捕获2个移动较快的敌对智能体.
本文将提出的MADDPG-DC方法与多种基线方法在以上3个环境中进行对比实验. 实验选择了MADDPG[15]、反事实的多智能体策略梯度[18] （counterfactual multi-agent policy gradient, COMA）、值分解网络[19] （value-decomposition networks, VDN）方法、QMIX[20]这4种基于CTDE框架的方法作为基线方法. COMA使用一个基于反事实基线的评论家网络结构来推导智能体学习策略的优势函数. VDN和QMIX是价值函数分解方法的代表性方法，使用个体价值函数的组合来估计联合价值函数.
由于这些基线方法全部基于CTDE框架，于是都存在价值函数高估问题. 所有实验在CPU Intel Xeon Silver 4210和GPU Nvidia RTX 2080上使用5个随机种子构建. 对于MADDPG和COMA，使用与MADDPG-DC相同的参数，如表2所示. VDN和QMIX包括更复杂的网络结构，参数如表3所示.
表 2 MADDPG-DC, MADDPG, COMA在多智能体粒子环境上的超参数Table 2. Hyperparameters of MADDPG-DC, MADDPG, COMA on Multi-Agent Particle Environments超参数 取值 评论家网络学习率 10−3 行动者网络学习率 10−4 目标网络更新率 10−2 RNN类型 GRU 批量大小 100 折扣因子 0.95 优化函数 Adam 训练回合 106 表 3 VDN和QMIX在多智能体粒子环境上的超参数Table 3. Hyperparameters of VDN and QMIX on Multi-Agent Particle Environments超参数 取值 学习率 10−4 RNN类型 LSTM & GRU 超网络 Have & None 批量大小 100 折扣因子 0.95 训练回合 106 优化函数 Adam 图4~6展示了各方法的平均奖励值. 在捕食者-猎物环境中，在参数相对一致的情况下，MADDPG和QMIX方法下的智能体未学得稳定的策略，导致平均奖励呈下降状态. 本文提出的MADDPG-DC方法在训练一开始的表现低于价值函数分解方法VDN，但最终收敛到更高的平均奖励值. 在物理欺骗环境下，MADDPG-DC收敛得最快且学得的平均奖励值最高，而MADDPG，COMA，VDN方法未能学得最优的策略. 在世界环境下，除了QMIX以外的大部分方法都采用收敛到稳定的策略，而MADDPG-DC同样取得了最好的表现. 综上，对比其他存在价值高估问题的基线方法，MADDPG-DC方法取得了更好的性能.
此外，为探讨双评论家网络结构和延迟行动者网络更新这2个因素对性能提升的影响，本文设计了消融实验. 实验中使用2个变体：使用双评论家网络结构但不延迟行动者网络更新的MADDPG-D和不使用双评论家网络结构但延迟行动者网络更新的MADDPG-C. 将这2个变体与原始MADDPG方法以及同时使用双评论家网络结构和延迟行动者网络更新的MADDPG-DC进行了比较. 首先，比较MADDPG-D与MADDPG的性能表现. 图7~9展示了不同多智能体粒子环境环境下的消融实验. 实验结果表明，在捕食者-猎物环境和世界环境下，MADDPG-D的学习性能显著，并持续优于MADDPG且收敛到稳定的策略. 在物理欺骗环境下，虽然MADDPG-D的表现持续优于MADDPG，但其学习曲线在后期也呈现下降趋势.
进一步，为验证延迟行动者网络的有效性，首先对比MADDPG，MADDPG-C，MADDPG-D在3个环境中，MADDPG-C的性能相比MADDPG有一定的提升, 但无法超过MADDPG-D的性能. 接下来，对比MADDPG-D和MADDPG-DC的表现. 如图7~9所示，在捕食者-猎物环境和世界环境下，MADDPG-DC收敛更快，且收敛至更高的奖励值. 在物理欺骗环境下，MADDPG-DC相比MADDPG-D，其可以收敛到稳定的最优策略. 由此可见双评论家网络结构和延迟行动者网络更新这2个因素对方法的性能都有提升作用，且同时使用2个改进因素的效果大于单独使用任意1个的效果.
3.2 交通信号控制环境
随着城市化的快速发展，车辆数量的增加不可避免地导致交通拥堵程度的增加. 通过优化管理方法可以实现交通系统的可持续发展[29]. 交通信号控制（traffic signal control, TSC）是一种有效的优化策略，它有助于改善交通状况、减少拥堵、缩短出行时间[30-31]. 为了应对TSC的规模需求，学者们尝试在多智能体系统中使用RL.
在局部观测和通信受限的情况下，将TSC定义为由分散的强化学习智能体控制交叉口的协作MARL问题是一种有效且通用的方法. 其中一种思路是使用独立Q学习（independent Q-learning, IQL）方法建模[32]，在这种方法中，分散的强化学习智能体独立地学习各自的策略，并将其他智能体当作环境的一部分. IQL方法可以解决可扩展性问题，但当其他智能体改变自己的策略[33]时，IQL会出现不收敛和不稳定性问题.
然而，现有的工作包括IQL方法通常采用分散训练和分散执行框架，这个框架通常会存在环境不稳定性问题[34]. 基于CTDE框架的MARL是一种有效的改进，如MADDPG方法. 然而，在TSC中，MADDPG方法的性能表现一般[35]. 其原因可能是在复杂环境下，MADDPG中价值估计的不准确导致了智能体行为的发散或者智能体学得了次优的策略. 同时，MADDPG在分散执行阶段缺乏通信学习机制[36-38]，而通信学习机制对于保证整体交通状态的控制稳定性和效果具有重要意义.
本文应用MADDPG-DC和CTDE框架来处理TSC问题. 为验证MADDPG-DC在实际系统中的可行性和有效性，本文在成都市实际交通网络[39-40]上进行了实验. 利用城市交通平台模拟真实的交通状况. 实验将每个交叉口的交通信号控制器建模为一个智能体，将网络交通状态建模为全局状态.
在真实的交通信号控制环境中，为证明MADDP-DC方法的有效性，选择IQL[32]、MADDPG[15]和最大压力控制（max pressure control）[41]等3种方法作为基线方法. IQL[32]基于分散训练分散执行框架，分散的智能体独立地学习各自的策略，而MADDPG利用CTDE框架. 最大压力控制是TSC领域最先进的控制方法之一，通过选择信号相位，最大化通过交叉口的车辆数量.
评价结果以各交叉口的交通拥堵情况和车辆通行效率为主要评价指标，包括3个主要指标: 平均队列长度、平均延迟和平均行驶时间. 平均队列长度是指在交叉口的所有车辆的平均等待队列长度. 平均延迟是指交通路口的所有车辆的平均等待时间除以队列长度. 这二者的值越高，表示方法的性能越差. 平均行驶时间是指整个交通网络中车辆从起点行驶到终点所花费的平均时间. 同样地，平均行驶时间的值越高，表示该方法的性能越差.
首先，本文从合成道路数据集中随机选取合成交通网络来训练MADDPG-DC方法以及其他基线方法，仿真实验运行了8000回合. 交通信号控制环境下的MADDPG-DC的超参数如表4所示. 基线MADDPG和MADDPG-D也设置相同的超参数进行训练. IQL的超参数如表5所示. 最大压力控制不是一种MARL方法，其参数设置保持和文献[41]一致.
表 4 交通信号控制环境下MADDPG, MADDPG-D, MADDPG-DC的超参数Table 4. Hyperparameters of MADDPG, MADDPG-D, MADDPG-DC Under Traffic Signal Control Environments超参数 取值 评论家网络学习率 10−3 行动者网络学习率 10−4 批量大小 64 折扣因 0.99 训练回合 8000 优化函数 Adam 表 5 交通信号控制环境下IQL的参数Table 5. Hyperparameters of IQL Under Traffic Signal Control Environments超参数 取值 学习率 10−4 批量大小 64 折扣因子 0.99 训练回合 8000 优化函数 Adam 然后，在真实交通网络中对训练后的方法分别进行1h的时变交通流训练. 考虑到计算成本，实验在1h后停止评估. 图10和图11分别展示了各方法下的真实交通网络中的平均队列长度和平均延迟. 从图11可以看出，MADDPG-DC方法的平均队列长度小于其他基线方法. 在模拟时间为2700 s时，MADDPG-DC方法下的平均队列长度达到峰值，约为0.63辆. 而对于其他基线方法，MADDPG方法在2980 s时达到约为1.41辆的峰值，MADDPC-D方法在2980 s时的峰值在0.92辆以上，IQL方法在3010 s时的峰值在2.69辆以上，最大压力控制方法在2730 s时的峰值在1.65辆左右.
![]()
图 10 真实交通网络中不同方法的平均队列Figure 10. Average queues for different methods in real traffic networks![]()
图 11 真实交通网络中不同方法的平均延迟Figure 11. Average delay of different methods in real traffic networks对比图10和图11可以发现，不同方法的曲线大部分都有相似的趋势. 大多数曲线在前期增加，然后在不同的时间到达峰值，最后趋于下降. 因此，可以推断这2个指标是相关的. 随着车辆队列的增加，交叉口的平均延迟也会增加. 值得注意的是，所有方法通过积累的交通数据进行学习后，都不同程度地减少了队列长度.
表6给出了不同方法在实际交通网络中多个的评价指标下的表现. 可以发现，MADDPG-DC的表现优于MADDPG-D，说明延迟行动者网络更新的有效性. 同时MADDPG-D的表现其次，证明双评论家网络结构实现了更准确的价值估计，进而促进更高质量的策略学习.
表 6 不同方法在真实交通网络中的性能Table 6. Performance of Different Methods in Real Traffic Networks方法 平均延迟/（s/辆） 平均队列长度/辆 平均行驶时间/s Max Pressure 40.94 1.82 269.45 IQL 48.61 2.15 285.23 MADDPG 37.73 1.53 253.67 MADDPG-D 24.08 1.21 216.32 MADDPG-DC 21.62 0.82 192.65 注: 黑体数字表示性能最优. 图11展示了所有方法的平均队列长度变化曲线. 如图11所示，MADDPG-DC方法在所有方法中表现最好，且MADDPG-D的表现其次. 2种变体方法在初期的曲线非常接近，但MADDPG-DC在3050 s达到约26.42 s/辆的峰值，而MADDPG-D在时间3250 s达到的峰值超过44.02 s/辆. MADDPG曲线虽然在模拟时间1700~1900 s之间有所下降，但之后一直呈现上升趋势. IQL方法和最大压力控制方法都直到结束时才出现一定程度的下降.
此外，值得注意的是，所有平均延迟曲线在前期均呈平稳上升趋势. 最大压力控制方法和IQL方法在后期仍然呈上升趋势，而MADDPG-D方法和MADDPG-DC方法在前期达到峰值，但在后期趋于下降. 无论是IQL方法还是最大压力控制方法都不能依靠一种可持续的策略来快速恢复拥堵的交通网络. 与MADDPG相比，MADDPG-D受益于更准确的价值估计可以学得更好的策略. 与MADDPG-D相比，MADDPG-DC倾向于一种更稳定和可持续的策略，能够实现更快的交通拥堵恢复. MADDPG-DC的平均队列长度趋于0，说明该方法对于减少交叉口拥堵，提高车辆行驶效率发挥了重要作用.
4. 总结和展望
为更好地估计MARL方法中的价值函数，本文提出基于双评论家网络的多智能体深度确定性策略梯度方法. 通过理论和实验论证MADDPG存在价值高估问题，并提出双评论家网络结构来避免价值高估. 此外，为提高策略更新的质量，延迟行动者网络更新. 实验结果表明，本文提出的方法在多智能体粒子环境的多个环境上的表现显著优于MADDPG等其他基线方法. 此外，交通信号控制环境上的实验结果证明所提方法在真实环境中的可行性.
然而，大多数基于CTDE框架的MARL方法可能都存在价值高估或低估的问题，本文没有对其他基于CTDE的MARL方法进行深入研究，这是未来的一个有趣且有价值的研究方向. 同时，在价值函数分解方法和其他CTDE方法中实现更好的价值估计将是我们下一步的工作.
作者贡献声明：丁世飞提出论文的研究方向及指导论文写作；杜威负责论文的撰写及研究框架设计；郭丽丽、张健、徐晓负责实验指导及论文写作指导.
-
![]()
图 1 群主计算相关参数所需的平均时间
Figure 1. Average time required for the group owner to calculate the relevant parameters
![]()
图 2 每个普通群成员计算出群组密钥的平均时间开销
Figure 2. Average time cost for each ordinary group member to calculate the group key
![]()
图 7 群成员向服务器查询用于计算群组密钥的相关参数
Figure 7. Group members query the server for the relevant parameters used to calculate the group key
![]()
图 9 Signal协议中实现群聊消息加密的流程
Figure 9. Process of implementing group chat message encryption in Signal protocol
表 1 本文方案的存储开销
Table 1 Storage Cost of Our Scheme
身份 存储开销/B 群主 {U_0} \dfrac{ {len} }{8} + (n + 3){ {\rm{lb} }}\dfrac{p}{8} + n + 2 普通群成员 {U_i}(i=1, 2, … , n) \dfrac{ {len} }{8} + 3{ {\rm{lb} }}\dfrac{p}{8} + 2 
下载: 导出CSV
表 2 本文方案的通信开销
Table 2 Communication Cost of Our Scheme
传输的信息 通信开销/B 群主广播的参数 q 和
{a_{n + 2}}, {a_{n + 1}},… ,{a_0}以及 {C_1}, {C_2},… ,{C_n}\dfrac{ {len} }{8} + \dfrac{ {n + 3} }{8}{\rm{lb}}(q - 1)+ n{\rm{lb} }\dfrac{p}{8} + n
下载: 导出CSV
表 3 6种运算各自所需的平均时间
Table 3 Average Time Required for Each of the Six Operations
运算 运算平均所需的时间 群{G_1}上的点乘 37.164 ms 双线性对 82.467 ms 哈希函数 {H_2} 5.071 μs {{\mathbb{Z}}_q} 上的加法 0.302 μs {{\mathbb{Z}}_q} 上的乘法 0.348 μs {{\mathbb{Z}}_q} 上的幂运算 1.010 μs
下载: 导出CSV
表 5 本文方案与文献[13]方案的比较
Table 5 Comparison Between Our Scheme and the Scheme Proposed in Reference [13]
2个比较角度 文献[13]的方案 本文方案 群组密
钥管理密钥类型 非对称密钥 对称密钥 密钥使用
方式需要由某个成员向证书
颁发机构注册群组公钥在本地直接使
用群组密钥参数分发
时成员在
线要求要求所有成员同时在线 只要求群主在线 非群组成员
对群组密钥
的获取能力非群组成员可以冒充
群组内成员与其他成
员协商出群组密钥非群组内成员无法计
算出正确的群组密钥兼容性 与目前在市场中投入使
用且广泛部署的协议
相差较大，兼容性较差利用国密SM9算法进
行构造，可兼容使用
了SM9的算法或协议
下载: 导出CSV
表 6 本文方案和Signal协议采取的方法的对比
Table 6 Comparison Between Our Scheme and the Method Adopted by Signal Protocol
4个比较角度 Signal协议采取的
方法本文方案 每个群成员需要在本地预计算的密钥数量 3 0 每个群成员需预存储的参数或密钥的数量 n + 1个链密钥、
n 个签名公钥、
1对签名密钥对群主：1个长期私钥和n + 1个椭圆曲线点；
普通群成员：1个长期私钥和1个椭圆曲线点每个群成员在会话开始前需发送的携带参数或密钥的报文数 n 群主：1；
普通群成员：0每个群成员发送n条消息时共需计算的消息密钥数 n 1
下载: 导出CSV
-
[1] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 644−654 doi: 10.1109/TIT.1976.1055638
[2] Harn L, Hsu C F, Xia Zhe. Lightweight and flexible key distribution schemes for secure group communications[J]. Wireless Networks, 2021, 27(1): 129−136 doi: 10.1007/s11276-020-02449-2
[3] Hsu C F, Harn L, Zeng Bing. UMKESS: User-oriented multi-group key establishments using secret sharing[J]. Wireless Networks, 2020, 26(1): 421−430 doi: 10.1007/s11276-018-1825-x
[4] 张泽林,王化群. 基于区块链的工业互联网动态密钥管理[J]. 计算机研究与发展,2023,60(2):386−397 Zhang Zelin, Wang Huaqun. Dynamic key management of industrial Internet based on blockchain[J]. Journal of Computer Research and Development, 2023, 60(2): 386−397 (in Chinese)
[5] Xiong Hu, Wu Yan, Lu Zhen. A survey of group key agreement protocols with constant rounds[J]. ACM Computing Surveys, 2019, 52(3): 1−32
[6] Chen C M, Deng Xiaoting, Gan Wensheng, et al. A secure blockchain-based group key agreement protocol for IoT[J]. The Journal of Supercomputing, 2021, 77(8): 9046−9068 doi: 10.1007/s11227-020-03561-y
[7] Braeken A. Pairing free certified common asymmetric group key agreement protocol for data sharing among users with different access rights[J]. Wireless Personal Communications, 2021, 121(1): 307−318 doi: 10.1007/s11277-021-08636-4
[8] Gan Yong, Wang Bingli, Zhuang Yuan, et al. An asymmetric group key agreement protocol based on attribute threshold for Internet of things[J]. Transactions on Emerging Telecommunications Technologies, 2021, 32(5): e4179
[9] Ingemarsson I, Tang D T, Wong C K. A conference key distribution system[J]. IEEE Transactions on Theory, 1982, 28(51): 714−719
[10] Naresh V S, Reddi S, Murthy N V E S. A provably secure cluster-based hybrid hierarchical group key agreement for large wireless ad hoc networks[J]. Human-centric Computing and Information Sciences, 2019, 9(1): 1−32 doi: 10.1186/s13673-018-0162-5
[11] Xu Zisang, Liang Wei, Li K C, et al. A time-sensitive token-based anonymous authentication and dynamic group key agreement scheme for industry 5.0[J]. IEEE Transactions on Industrial Informatics, 2021, 18(10): 7118−7127
[12] Lee T F, Ye Xiucai, Lin S H. Anonymous dynamic group authenticated key agreements using physical unclonable functions for internet of medical things[J]. IEEE Internet of Things Journal, 2022, 9(16): 15336−15348 doi: 10.1109/JIOT.2022.3149117
[13] Wu Qianhong, Mu Yi, Susilo W, et al. Asymmetric group key agreement[C] //Advances in Cryptology-EUROCRYPT 2009: 28th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2009: 153−170
[14] Zhang Lei, Wu Qianhong, Qin Bo, et al. Identity-based authenticated asymmetric group key agreement protocol[C] //Proc of the 16th Annual Int Conf on Computing and Combinatorics. Berlin: Springer, 2010: 510−519
[15] 张启坤,甘勇,王锐芳,等. 簇间非对称群组密钥协商协议[J]. 计算机研究与发展,2018,55(12):2651−2663 Zhang Qikun, Gan Yong, Wang Ruifang, et al. Inter-cluster asymmetric group key agreement[J]. Journal of Computer Research and Development, 2018, 55(12): 2651−2663 (in Chinese)
[16] Li Juyuan, Qiao Zhiqi, Peng Jialiang. Asymmetric group key agreement protocol based on blockchain and attribute for industrial Internet of things[J]. IEEE Transactions on Industrial Informatics, 2022, 18(11): 8326−8335 doi: 10.1109/TII.2022.3176048
[17] Guo Hua, Zheng Yandong, Li Xiong, et al. Self-healing group key distribution protocol in wireless sensor networks for secure IoT communications[J]. Future Generation Computer Systems, 2018, 89(12): 713−721
[18] Meng Keju, Miao Fuyou, Yu Yue. A secure and efficient on-line/off-line group key distribution protocol[J]. Designs, Codes and Cryptography, 2019, 87(7): 1601−1620 doi: 10.1007/s10623-018-0554-6
[19] Li Xinghua, Wang Yunwei, Vijayakumar P, et al. Blockchain-based mutual-healing group key distribution scheme in unmanned aerial vehicles ad-hoc network[J]. IEEE Transactions on Vehicular Technology, 2019, 68(11): 11309−11322 doi: 10.1109/TVT.2019.2943118
[20] Jiao Runhai, Ouyang Hong, Lin Yukun, et al. A computation-efficient group key distribution protocol based on a new secret sharing scheme[J]. Information, 2019, 10(5): 175
[21] Yıldız H, Cenk M, Onur E. PLGAKD: A PUF-based lightweight group authentication and key distribution protocol[J]. IEEE Internet of Things Journal, 2020, 8(7): 5682−5696
[22] Xu Guangquan, Li Xiaotong, Jiao Litao, et al. BAGKD: A batch authentication and group key distribution protocol for vanets[J]. IEEE Communications Magazine, 2020, 58(7): 35−41 doi: 10.1109/MCOM.001.2000118
[23] Shamir A. Identity-based cryptosystems and signature schemes[C] //Proc of the 4th Int Cryptology Conf. Berlin: Springer, 1985: 47−53
[24] Nam J, Choo K K R, Han S, et al. Efficient and anonymous two-factor user authentication in wireless sensor networks: Achieving user anonymity with lightweight sensor computation[J]. PloS One, 2015, 10(4): e0116709 doi: 10.1371/journal.pone.0116709
[25] Chang Chin-Chen, Le Hai-Duong. A provably secure, efficient, and flexible authentication scheme for ad hoc wireless sensor networks[J]. IEEE Transactions on wireless communications, 2015, 15(1): 357−366
[26] 张启坤,王锐芳,谭毓安. 基于身份的可认证非对称群组密钥协商协议[J]. 计算机研究与发展,2014,51(8):1727−1738 Zhang Qikun, Wang Ruifang, Tan Yu’an. Identity-based authenticated asymmetric group key agreement[J]. Journal of Computer Research and Development, 2014, 51(8): 1727−1738 (in Chinese)
[27] GB/T 38635.2−2020《信息安全技术 SM9标识密码算法》第2部分: 算法[S]. 北京: 中国标准出版社. 2020 GB/T 38635.1-2020. Information Security Technology SM9 Identity-based Cryptography Part 2: Algorithm[S]. Beijing: Standards Press of China, 2020（in Chinese）
[28] 文嘉明, 王后珍, 刘金会, 等. Aitps: 基于非对称模格问题的两方协同签名方案[J]. 计算机研究与发展2023, 60（9）: 2137−2151 Wen Jiaming, Wang Houzhen, Liu Jinhui, et al. Aitps: A two-party signature from asymmetry module lattice problem[J]. Journal of Computer Research and Development 2023, 60(9): 2137−2151 (in Chinese)
[29] GB/T 38635.1−2020 《信息安全技术 SM9标识密码算法》第1部分: 总则[S].北京: 中国标准出版社, 2020 GB/T 38635.1-2020. Information Security Technology SM9 Identity-based Cryptography Part 1: General[S]. Beijing: Standards Press of China, 2020（in Chinese）
[30] Alwen J, Coretti S, Dodis Y. The double ratchet: Security notions, proofs, and modularization for the signal protocol[C] //Advances in Cryptology–EUROCRYPT 2019: 38th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2019: 129−158
[31] WhatsApp. Whatsapp encryption overview, technical white paper [R/OL]. (2023-01-24) [2023-04-15].https://scontent-sjc3−1.xx.fbcdn.net/v/t39.8562−6/328495424_498532869106467_756303412205949548_n.pdf?_nc_cat=104&ccb=1−7&_nc_sid=ad8a9d&_nc_ohc=BPmGXFrfbGsAX-A2MQ7&_nc_ht=scontent-sjc3−1.xx&oh=00_AfCYrzsCnuGB8OeWmfTUifmAcQPd1CLh2OlykXi0M_RkMg&oe=643F38BC
[32] Facebook Messenger. Messenger secret conversations, technical whitepaper [R/OL]. (2017-05-18) [2023-04-15].https://about.fb.com/wp-content/uploads/2016/07/messenger-secret-conversations-technical-whitepaper.pdf
计量
- 文章访问数: 282
- HTML全文浏览量: 45
- PDF下载量: 140
