聚类与信息共享的多智能体深度强化学习协同控制交通灯

杜同春 王 波* 程浩然 罗 乐 曾能民

①(安徽师范大学计算机与信息学院 芜湖 241008)

②(哈尔滨工程大学经济管理学院 哈尔滨 150001)

1 引言

交通拥堵增加能源消耗和碳排放。本文根据交通状况进行多个路口协同地、动态地调节信号灯相位和时长，以减少车辆在路口的延迟、提高整体通行率。交通信号灯智能控制方法大致可分为3类：

第1类是时序控制转化成优化问题的方法，例如线性规划[1]、神经网络[2]等在一定程度上不能适用实时多变的多路口交通灯控制中，在实践中导致有限的可扩展性或最优性。

第2类是强化学习的方法，在设计好奖励函数、动作、状态的前提下，能够从样本数据中学习最优控制策略，工作包括文献[3–5]等。虽然在单路口交通信号控制场景下，减少了车辆等待时间，但是传统的强化学习方法由于对高维复杂状态的表达能力有限，而且通常仅适用于有限离散状态和动作空间的马尔可夫决策过程，因此其局限性很明显。

第3类为结合了深度学习的特征提取[6]能力和强化学习的序列决策能力[7]的深度强化学习方法，是目前最为合适的交通信号灯控制方法。多数工作以深度Q网络(Deep Q-learning Network, DQN)为基础，选择更合理的观测，设计奖励函数，以及设计更好的特征提取网络，例如文献[8–11]。多路口交通信号灯协同控制具有巨大的状态与动作空间，造成维度爆炸、计算缓慢等问题，因此不能仅用单智能体深度强化学习方法解决。多智能体深度强化学习(Multi-Agent Deep Reinforcement Learning,MADRL)则更适用于解决分布式交通信号控制问题。MADRL的目标是提高多个智能体之间的协同效果，当前的主流框架是中心化训练去中心化执行(centralized training and decentralized execution)，其关键是设计协同训练的框架和方法，根据协同方法分为：(1)全局值函数分解方法，例如混合式多智能体Q学习(Q-value MIXtures, QMIX)[12]、Q变形分解多智能体强化学习(Q-value TRANsformation, QTRAN)[13]；(2)基于中心化的评判(Critic)方法，例如多智能体深度确定性策略梯度(Multi-Agent Deep Deterministic Policy Gradient, MADDPG)[14]、反事实多智能体策略梯度(COunterfactual Multi-Agent policy gradient, COMA)[15]等。MADRL用于交通信号灯控制的研究工作包括[16]：因果推理的MADRL[17]，基于生成对抗网络(Generative Adversarial Networks, GAN)的交通数据恢复法和MADRL相结合的信号灯控制[18]，引入注意力机制和领域认知一致性来解决智能体之间的合作问题[19]，广义强化学习提高智能体之间的有效交互[20]等。可见，目前工作的主要目的是提高智能体之间的通信和合作水平。

目前MADRL研究的实验都是在少量智能体的仿真游戏上进行的，对于多智能体马尔可夫决策过程(Markov Decision Process, MDP)问题，智能体之间共享的信息量非常巨大，导致通信延迟。实际上，对于距离较远、观测差异大的智能体共享信息的意义很小，甚至可能是噪声。如何共享有限且高效信息共享以提高协同水平是值得研究的问题。为此，针对建模成多智能体马尔可夫决策过程的多路口交通信号灯控制的实际问题，本文贡献如下：

(1)提出基于生长型神经气(Growing Neural Gas, GNG)的智能体聚类方法，对多路口的智能体进行聚类，目的是减少信息共享的数据量并找出具有相似位置和观测的智能体以实现更好的协同；

(2)提出全局值函数分解与观测共享的多智能体深度循环Q网络(Multi-Agent Deep Recurrent Q-Network, MADRQN)中心化训练算法，实现对聚类内部多路口的交通信号灯控制模型的训练；

(3)提出最优智能体参数分析的方法。在训练过程中，借鉴粒子群算法，将评价值最高的智能体的策略网络的参数分享给其它智能体，目的是加快训练速度并且使得全部智能体向最优参数协同进化。

本文的所有仿真实验均在城市交通仿真软件(Simulation of Urban MObility, SUMO)下进行，更接近真实路况。

2 智能体聚类

具有相似认知的智能体才能更好地协同完成任务。本文以位置和观测构成的混合特征，使用GNG对智能体聚类。GNG是一种动态自组织算法，不需要指定类别数，根据竞争的赫布(Hebbian)学习规则不断地更新网络的节点和连接，以学习输入矢量分布的拓扑结构[21]。交通路网可视为图结构，而车流量是动态变化的，因此每隔1 000个时间步对智能体重新聚类1次。使用迭代的生长型神经气算法对混合特征聚类，得到具有一致或相似认知的多个智能体，如图1(b)中的上面两个灰色圆和下面两个灰色圆分别是两个聚类内的智能体。然后在聚类内部进行信息共享和中心化训练，由此减少共享的数据量、提高协同效果。智能体聚类算法，如算法1中第5～14行所示。

图1 MADRQN算法框架

3 观测信息共享与最优参数分享的MADRQN中心化训练

仅在聚类内进行信息贡献极大地缓解了由环境变化造成的算法收敛困难的问题。在中心化训练阶段，设计如图1(a)，在t时刻，智能体能够以全局状态st和全部智能体上一时刻的隐状态ht-1为输入，拟合状态动作值Qi(τi,ai)，其中GRU为门控循环单元，用于提取时间维度上对交通状态的观测特征。智能体采用ε- 贪婪策略选择动作ait。图1所示是聚类内智能体的中心化训练，而且多个聚类之间可以并行训练，由此加速了多个智能体训练的速度。st为全局状态，即聚类内全部智能体的观测构成的联合观测，如式(1)，at为聚类内全部智能体的动作构成的联合动作，如式(2)。在去中心化执行阶段，依然可以采用共享观测的方法，而不用担心数据量大造成的通信延迟问题。得到Qit(st,at)之后，第i个智能体的损失函数表示如式(3)

式(3)中M为训练样本的批数量，训练样本表示为{st,at,st+1,rt}。采用时序差分 (Temporal Difference, TD)法计算误差，yj表示状态s′=st+1和动作a′=at+1在第j个样本的目标网络的值函数，如式(4)，rj表示第j个样本的立即奖励

中心化训练时，式(3)中误差反向传播以更新状态动作值函数网络的参数。式(5)是对一个批次样本的TD误差计算梯度，并根据式(6)进行参数更新，α表示学习率

如图1(b)所示，将智能体看作探索参数空间的粒子，每轮训练结束聚类内每个智能体的训练网络和目标网络的参数分别朝着全局和个体最优参数移动，以提高训练速度

按式(8)和式(9)移动参数， pbestθi和 gbestθ分别是单个智能体和全局的最优值函数网络参数。全局参数是获得最高评价值的值函数网络的参数，如式(10)。

整个算法的伪代码如算法1，注意在第15行和第20行、第16行和第21行，虽然对聚类和智能体进行遍历，但其实与环境的交互和模型训练，在不同的聚类以及聚类内的智能体之间，都是并行的。

4 实验环境与参数设计

将芜湖弋江区部分路网导入到SUMO，如图2(a)，将路口映射至图2(b)。

图2 路网拓扑图及路口映射图

将交通信号灯控制建模成马尔可夫决策过程(Markov Decision Process, MDP)，对于MDP的6元组 ，其中S表示为智能体对路口交通状况的观测，具体如图3所示，观察的车道长度是400 m，设置车辆的长度是5 m，将进入路口的4个车道的车辆构成的向量相加得到最终的向量，1表示对应的位置有车，0表示无车；A表示动作空间，包括4个动作，{南北直行，南北左转，东西直行，东西左转}。绿灯的时长设置为10 s，红绿灯切换间隙执行4 s的黄灯。奖励函数R设置为路口全部车辆在两个相邻时间步的平均等待时长之差，因此奖励是负数。P表示状态转移概率，是由环境决定的，因此是未知的。γ表示立即奖励的折扣因子，设置为0.9。

算法1 MADRQN算法伪代码

图3 路口状态定义

实验设置整个路网的车流量为1 000 辆/s，在实验中随机分配给所有路口，为了展示聚类算法的效果，算法参数设置如表1。

表1 实验及算法参数设置

5 实验结果与分析

对于算法1中的智能体聚类、基于观测共享的中心化训练、参数移动等方法，开展实验并对结果进行分析。

5.1 根据位置和观测对智能体聚类

在表1参数设置下，截取算法1中随机训练过程中的一轮聚类结果，如图4所示。其中图4(a)是中间过程的GNG网络拓扑，图4(b)是最终的聚类结果，将智能体聚成了4类，分别用红色点、绿色点、蓝色点、深蓝色点表示。由此可得，聚类结果主要由路口位置决定，同时受到车流量的影响，当距离过远即便交通流相似也不会被聚为一类。由于交通状况是不断变化的，聚类结果也将变化。

图4 根据表2参数设置的智能体聚类结果

5.2 信息共享的MADRQN独立训练

在对全部路口的交通信号灯控制智能体聚类的基础上，采用观测与动作共享的MADRQN算法对智能体的值函数网络进行中心化训练，并在每一轮训练结束，将每个智能体的训练网络和目标网络的参数分别朝着全局和个体最优参数移动。以下分别从整体的算法效果与其它多智能体深度强化学习算法的效果对比、聚类与不聚类的实验结果、聚类与不聚类的训练时间3个方面进行分析，验证本文的假设。

5.2.1 MADRQN算法整体的控制效果与分析

图5是本文提出的信息共享与参数分享的MADRQN算法与其它典型的多智能体深度强化学习算法，包括QMIX、值分解网络(Value Decomposition, Network, VDN)、深度循环Q网络(Deep Recurrent Qlearning Network, DRQN)，对15个路口的交通信号灯控制时计算的每轮平均奖励的对比。横坐标是训练的轮数，共100轮，纵坐标是计算的每一轮的平均奖励，即对一轮中全部步数的负立即奖励求和，得到累积负奖励，然后再对每个算法运行3遍(每一遍都是100轮，每轮步数Ti=300)，对3遍的累积负奖励求平均，得到平均每轮奖励 aer，如式(11)所示，目的一是为了观察算法的稳定性，二是可以计算标准差(如图5中曲线的上下着色部分)。

图5 算法对比图

从图5(a)和图5(b)可以看出，MADRQN略优于VDN，原因是使用GRU提取了时间维度上的相关特征，对Q值的预测更加准确。相比DRQN进行独立训练，MADRQN的效果更好，原因是通过聚类将具有相似位置和观测的智能体进行观测共享，解决了环境部分可观测并缓解了环境非静态的问题，以及通过中心化训练，提高了智能体之间的协同水平。相比于QMIX以全局状态进行参数化超网络的值函数分解，由于MADRQN采用了聚类并在聚类内部进行观测共享，智能体的环境更相似而且信息共享更加准确，因此，MADRQN的效果优于QMIX。

5.2.2 智能体聚类对控制效果的影响与分析

本文一个重要假设是在聚类内部共享的信息数据量少，而且信息的相关性和作用更大，更有利于提高中心化训练效果。

为验证该假设，将MADRQN算法分别应用于全部15个路口的智能体以及GNG算法得到的4个聚类的智能体，计算方法与4.2.1中相同，如图6所示，蓝色曲线(有GNG)是做聚类后分别中心化训练的效果，而橙色曲线(无GNG)是对全部智能体直接用MADRQN算法的效果，如图6(a)、图6(b)可见，不做智能体聚类时的每轮累积奖励更小、平均每轮累积延迟更大。因为不做聚类时在所有智能体之间进行信息共享与参数分享，状态空间大导致训练缓慢。此外，距离较远路口分享的参数与共享的观测不合适导致了整体算法性能下降。图6(c)反应了多个聚类并行训练的训练时长，明显低于不做聚类的训练用时。由此，验证了本文对智能体聚类作用的假设。

图6 聚类算法对比图

5.2.3 最优参数分享的影响与分析

如图7，橙色曲线(参数共享)表示在每轮训练结束时将Q值最大的值函数网络的参数分享给其它智能体。蓝色曲线(无参数共享)表示不做参数分享。由图7(a)可见，参数分享能够降低训练时间。但由图7(b)可得参数共享的方式可能会牺牲一定的性能。

图7 最优参数实验对比图

6 结束语

本文对智能体根据位置和观测等信息聚类，提高了信息共享的效率和可行性，解决了环境部分可观测和非静态的问题，提出的最优参数分享对于加速训练有明显效果，本文方法对于缓解城市拥堵也存在一定意义。本文不足之处在于，对智能体聚类所用特征需要进一步研究，聚类的依据应该还包括智能体对自身任务的理解，如何表示任务目标并将任务、观测、位置等进行融合，以表示智能体的认知，是值得研究的课题。