1. 引言
近年来,新型城镇化取得重大进展,它带来机遇动力的同时,也使我们面临一些问题和挑战。其中,城镇有限的道路资源和汽车数量的持续增长导致交通效率持续低下、拥堵日益严重。随着大数据和人工智能技术的快速发展,交通信号的智能控制已经在许多大城市推广,并且都获得了令人满意的效果。例如,上海市在浦西世博园区、黄浦泛外滩地区等试点应用的智能交通信号灯管理系统,使道路通行效率平均提升10% [1] 。据统计,近年来上海道路交通事故数、死亡人数、受伤人数持续下降,2018年同比分别下降了6.3%、5.2%和6.8%,创历史新低,日均交通类110警情同比下降12.4% [1] 。与传统的交通信号控制方法,如Webster固定配时系统 [2] 、MOVA [3] 、SCATS [4] 等相比,智能交通信号控制可以根据交通流量和需求自动调整交通信号,实现交通的高效运行。
其中,强化学习(Reinforcement Learning, RL) [5] 作为一种最为可行的机器学习技术在智能交通信号控制领域被广泛应用。强化学习可以直接与环境交互,根据学习到的策略选择最佳动作。具体的方法就是将路网的交叉口建模为智能体,智能体观察周围环境的状态(交通状况),根据状态执行动作(改变交通信号),此时环境会转移到一个新的状态,同时将刚才动作所获得的奖励(车辆的队列长度、车辆的等待时间、车辆数目等)反馈给智能体,智能体会根据奖励的好坏优化自己的策略。这个过程会被反复执行,直到智能体学习到最优策略。近年来,已经有一些有效的方法将强化学习应用到智能交通信号控制中 [6] 。一开始大部分研究人员将注意力放在了单个交叉口上,例如,Li等人 [7] 将Q-learning与深度堆叠自动编码器(Deep Stacked Autoencoders, SAE)神经网络结合,其中,输入状态和奖励是根据进站车道的排队长度来定义的,仿真结果表明,与传统的强化学习方法相比,深度强化学习方法可以将平均交通延迟减少14%。Luo等人 [8] 提出了一种自适应道路划分策略和基于深度Q网络(Deep Q Network, DQN)的改进神经网络模型。改进了传统的交通信号控制模型,考虑到车辆与交通灯之间的距离对智能体决策的影响,提出了一种基于Fibonacci序列的自适应道路划分方法,以获得更真实的状态。Wang等人 [9] 提出了一种基于3DQN的交通信号控制方法,使用了基于高分辨率事件的数据,该方法以两种常用的交通信号控制策略为基准进行对照实验,即固定时间控制策略和驱动控制策略,实验证明所提出的基于事件数据的状态表示优于一般状态表示。虽然上述工作在单交叉口的信号控制上取得了很好的效果,有效地缓解了交通拥堵情况,但是忽略了其他交叉口对当前交叉口的影响,即多交叉口之间的协调问题,也难以在实际中应用。因此,越来越多的研究者开始关注多交叉口信号控制问题。
对于多个交叉口的交通信号控制问题,在强化学习的基础上,一个简单的想法就是将每个交叉口都建模为一个智能体,每个智能体都能以试错的方式与其所在环境和相邻的智能体交互,学习全局最优策略。这种方法称为多智能体强化学习(Multi-Agent Reinforcement Learning, MARL) [10] 。在最近的一些成果中,研究者们将深度学习(Deep Learning, DL)与多智能体强化学习结合起来,形成了多智能体深度强化学习(Multi-agent Deep Reinforcement Learning, MADRL)。深度学习能够使用神经网络高效地表示和存储高维状态、动作和奖励,从而使MARL快速收敛。Haddad等人 [11] 在DQN的基础上提出了一种多路口协同控制的方法,每个智能体通过接收相邻智能体的状态、动作和奖励来实现合作。Chu等人 [12] 提出了一种新的基于优势演员评论家(Advantage Actor Critic, A2C)的MARL算法(MA2C),通过邻居的指纹信息提高观测性,同时引入了空间折扣因子降低了学习维度,该算法在合成交通网络和现实世界路网中均被证明是有效的。Wu等人 [13] 在深度确定性策略梯度(Deep Deterministic Policy Gradient, DDPG)算法的基础上,提出了一种新的多智能体递归深度确定性策略梯度(Multi-agent Recurrent Deep Deterministic Policy Gradient, MARDDPG)算法,它是通过车辆网络收集时空交通信息实现智能体之间的合作,使用集中学习、分散执行的策略,还利用LSTM来捕获隐藏的状态信息,实验证明该算法适用于中等规模的流量网络。但是,上述研究中都存在一个问题,即维数诅咒问题——离散状态-动作空间中状态和动作变量的数量呈指数增长。在MARL中,由于存在多个智能体,每个智能体都会将自己的变量添加到联合状态–动作空间中,所以MARL中的维数诅咒比单智能体强化学习更加严重。除此之外,由于所有的智能体都在同时学习,它们的最优策略都在随着其他智能体的策略变化而变化,所以在MARL中还存在着非平稳性问题。最后,探索和利用的权衡问题也应该特别关注,这种权衡是需要在线强化学习算法在利用智能体已学到的知识和为了提升该知识而采取的探索性之间取得平衡。尤其是在MARL中,为了适应其他智能体的动作,智能体不仅要探索环境信息,还要探索其他智能体的信息。但是,过多的探索又会破坏其他智能体的稳定,从而使探索智能体的学习任务变得更加困难。
为了应对在MARL中面临的上述挑战,Wang等人 [14] 采用了基于双Q学习和上置信界(Upper Confidence Bound, UCB) [15] 算法的探索策略,在保证探索的同时消除了传统独立Q学习的高估问题。将多个智能体之间的交互基于平均场理论 [16] 建模,使智能体能够学习到更好的合作策略,降低了动作空间的维度和计算复杂度。Hu等人 [17] 也在双Q学习的基础上结合MFT降低联合动作空间的维度,其使用Boltzmann策略来平衡探索和利用之间的关系。该方法还将递归神经网络与改进的传统交通方法相结合,动态确定相位持续时间,显著提高了交通性能。但是上述研究都没能有效的解决Q值的高估问题,只关注到了智能体及其相邻智能体的动作,缺少对交通环境在时间和空间上的观察。
本文在上述研究的基础上提出了一种新的带有注意力机制的平均场双决斗深度Q网络算法(MF3DQN-TF)。首先,我们使用Transformer模型 [18] 中的注意力机制对交通环境更全面的观察,为智能体提供更高效的表征结果。然后引入平均场理论,将多个智能体之间的交互近似为单个智能体与其邻居智能体的平均场虚拟智能体的二元交互,以降低联合动作空间的维度。接着使用3DQN算法能够有效的解决先前研究对Q值的高估问题。最后使用SUMO作为仿真平台,在具有多交叉口的交通路网中模拟真实世界中的交通流,验证本文所提出的算法,根据设计的性能指标与几种最先进的MARL算法进行对比实验。综上所述,本文的主要贡献如下:
1) 对DQN算法进行一些改进,包括双重网络结构、经验池抽样策略和优势函数,有效地解决了Q值的高估问题,从而使得模型快速收敛;
2) 引入了平均场理论,与3DQN算法相结合,将先前研究中与所有邻居智能体交换知识(如奖励、动作、状态、Q值等)改进为与所有邻居智能体的平均知识进行共享,大大降低了智能体的状态动作空间的维度,解决了MADRL中收敛困难的问题;
3) 添加了自注意力层分析交叉口处的交通信号灯与各个入站车道之间的关联规则,将分析的结果作为状态输入,有助于智能体从分析后的数据中更快的学习到控制交通信号的策略;
4) 在SUMO中建立了包含多个交叉口的交通网络,模拟了更加符合现实世界的交通流,有利于扩展到真实交通网络,实验结果证明,提出的交通信号控制模型优于现有的流行方法。
2. 研究背景
2.1. 多智能体深度强化学习
多智能体强化学习的实质就是一个基于马尔可夫决策过程的随机博弈,多个智能体通过合作或者竞争获取最大利益的过程。假设共有N个智能体,多智能体系统可以建模为
,其中,
表示系统的联合状态空间,
表示系统的联合动作空间,P表示联合状态转移函数,
表示每个智能体的奖励函数,
代表折扣因子。与单智能体强化学习类似,它们的目标都是学习到最优策略
,使得累积预期回报最大化。不同的是在多智能体强化学习中,每个智能体都有自己的策略
,所以每个智能体都必须要考虑其他智能体的动作,在顾全大局的情况下,学习到最优策略,即
,这就是纳什均衡 [19] 。
假设环境的初始状态为s,那么智能体k在联合策略
下的价值函数被定义为累积期望折扣奖励:
(1)
根据贝尔曼方程,智能体k的动作价值函数,也称为Q函数定义如下:
(2)
其中,
是在当前状态s下所有智能体的联合动作,
是下一个时间步长时环境的状态,
为智能体k的奖励函数。因此,价值函数
可通过等式(2)中的Q函数表示:
(3)
由等式(1)和等式(2)可以看出每个智能体的价值函数与所有智能体的联合策略
有关,根据纳什均衡有:
(4)
等式(4)说明在这种情况下,只要其他智能体保持自身策略不变,任何智能体都不能通过改变其策略而获得更好的累积期望奖励。其中,
表示除了智能体k以外,其他智能体的最优联合策略。同时,Q函数最终也会收敛到纳什Q值
。
在单智能体强化学习系统中,就因为状态空间和动作空间的维数增加引入了深度学习,利用深度神经网络去近似Q函数,形成了深度强化学习。那么在多智能体强化学习系统中,随着智能体数目的增加,系统的状态空间和动作空间的维数都呈指数型增长,环境变得更加复杂,在这种情况下,深度强化学习方法仍然是一种可行的方法。但是,对每个智能体直接近似Q函数并不能解决维数灾难问题,反而会使系统难以收敛。因此,本文将引入平均场理论来降低动作空间的维数,以处理MADRL中收敛困难的问题。
2.2. 平均场理论
在物理学和概率论学中,平均场理论通过研究一个简单的模型来表示高维随机模型的行为,通过对原始模型的自由度取平均来近似得到。文献 [16] 最先将MFT与多智能体强化学习算法相结合,利用平均场近似方法解决大规模群体问题。其核心思想是将环境中的多个智能体之间的相互作用转化为一个智能体与其相邻智能体的平均值之间的相互作用。该方法大大降低了联合动作空间的维度。具体的,可以将智能体k的Q函数分解为:
(5)
其中,
是智能体k的邻居智能体的索引集合,
是邻居智能体的个数,
代表智能体k的邻居智能体的平均动作。等式(5)的详细证明过程可以参考文献 [16] 。
2.3. 平均场双决斗Q学习
迄今为止,深度学习和深度强化学习领域都有了最新进展,为了实现等式(5)中的平均场Q函数,可以使用深度神经网络去近似。目前存在许多先进的深度强化学习算法,大致可以分为两大类:基于价值的方法和基于策略的方法。具有代表性的如DQN、DDPG [20] 、PPO [21] 等。由于本文的动作空间是离散的(关于动作空间的定义将在下文详细说明),所以本文选择了基于价值的方法。在基于价值的方法中,DQN被认为是深度强化学习的开山之作,但是原始的DQN算法会导致Q值的高估,还会影响训练过程的稳定性。因此本文中使用一些技巧去解决上述问题,即双决斗深度Q网络。首先利用Double DQN去计算智能体k目标网络的Q值:
(6)
其中,
是智能体k主网络的参数,
为下一个时间步长时智能体k的邻居智能体的平均动作,
是智能体k目标网络的参数。接着改变网络结构使学习过程更加稳定,即双决斗网络结构:
(7)
最后可以通过最小化损失函数训练平均场双决斗Q函数,损失函数定义为:
(8)
3. 结合注意力机制的平均场双决斗深度Q网络交通信号控制模型
多智能体系统环境复杂,大多数文献只提取了道路环境的表面特征,缺少对交通特征之间关系的深入分析。因此,利用Transformer中的注意力机制捕获每个交叉口的交通特征之间的相关性,并将其作为模型的输入状态,使智能体全面了解环境信息。此外,本节中还定义了模型的动作空间、奖励函数以及所提的MF3DQN-TF算法。
3.1. 状态空间
从道路环境中提取的观测值必须能帮助智能体获得足够的信息,以做出正确的决策。对于第k个交叉口,它的部分观测值为
,其中
是第
条入站道路的观测信息,
,
表示第i条入站道路中l车道上第一辆车的累积延迟时间(s),
表示第i条
入站道路中l车道上的车辆数目(veh),
是交叉口k当前观测下的交通相位。接下来使用Transformer中的自注意力机制(Self-Attention)对交叉口k的部分观测值进行处理,结构如图1所示。本文将
作为计算查询向量的输入值,是为了捕获当前相位对于每条入站车道的注意力系数,然后将这些注意力系数分配给每条入站车道。注意力值高的入站车道,就会获得智能体的重点关注。
Figure 1. Single intersection observation value processing model based on Self-Attention
图1. 基于Self-Attention的单交叉口观测值处理模型
具体的,假设存在三个线性变换矩阵
,交叉口k的第i条入站道路的观测值
用来计算键值向量和值向量:
(9)
(10)
查询向量计算方式如下:
(11)
交叉口k的当前相位对入站道路i的注意力得分为:
(12)
其中,
是键值向量
的维度。为了提高可解释性和平滑性,使用Softmax函数对所有的注意力得分进行处理,最终得到了所有入站道路的注意力系数:
(13)
然后将这些注意力系数和值向量点乘,就得到了所有入站道路的注意力值:
(14)
(15)
这些入站道路的注意力值就作为智能体进行决策的输入状态:
(16)
除了将交叉口k自身的状态作为输入状态外,本文还将交叉口k的所有邻居交叉口的状态的平均值作为附加输入。所以交叉口k的联合状态为:
(17)
3.2. 动作空间
根据模拟实验的道路环境,本文设置了如图2所示的交通相位。其中,NSG表示南北方向的车辆可以直行和右转,NSLG表示南北方向的车辆可以左转和右转,EWG表示东西方向的车辆可以直行和右转,EWLG表示东西方向的车辆可以左转和右转。为了保证司机在切换相位之前有时间反应,所以在切换相
位之前设置了黄灯时间。基于此,定义动作空间为
,智能体可以直接从A中选择合适的相位,同时采用独热编码的形式表示相应的动作。例如,在时间步长t时智能体k选择了NSG相位,此时的动作表示为
。
如果将要选择的动作与当前动作相同,那么继续保持当前动作
s。如果不相同,则需要先执行
s的黄灯时间,再继续执行所选择的动作
s。
3.3. 奖励函数
奖励函数的定义非常重要,它可以直接反映所提的算法是否有效。为了直观的展示交通拥堵状况,本文利用入站道路上车辆的排队长度和等待时间定义奖励函数:
(18)
其中,
是指入站道路i上车辆的队列长度,
是指入站道路i上车辆的等待时间。
是权衡系数,为了使
和
在同一范围内。
3.4. 交通信号控制模型
本小节主要介绍基于MF3DQN-TF算法的交通信号控制模型,模型的结构如图3所示。首先,需要对Self-Attention Layer进行预训练,使其具有捕获当前相位对于每条入站道路的注意力系数的能力。然后将从Self-Attention Layer获得的交叉口的联合状态输入给智能体,其中每个智能体通过MF3DQN学习选择最优动作。MF3DON将交叉口的联合状态和邻居交叉口的平均动作作为联合状态动作对,其网络结构如图4所示,用于估计Q值。为了使估计的Q值更加精确,本文使用了双估计器,即Double DQN,此时智能体k目标网络的Q值为:
(19)
并且通过最小化损失函数训练智能体k的
值,使用均方误差定义损失函数:
(20)
Figure 3. Structure diagram of traffic signal control model
图3. 交通信号控制模型结构图
Figure 4. Network Structure of MF3DQN
图4. MF3DQN的网络结构
其中,M是指从经验池中随机抽取的样本数量。为了最小化损失函数,本文使用自适应矩估计(Adaptive Moment Estimation, Adam)优化器更新主网络的模型参数
。对于目标网络的参数
,我们采用软更新的方法,即目标网络的参数缓慢地向主网络的参数靠近,而不是直接复制当前主网络的参数。具体更新方式如下:
(21)
其中,
,用于控制更新速度,使
更加平滑的更新,从而提高模型的稳定性。
另外,在智能体学习的过程中,探索与利用的平衡问题也需要特别关注。一些比较经典的探索与利用算法包括
贪婪策略、上界置信算法(Upper Confidence Bounds, UCB)。文献 [22] 已经证明UCB算法在基于多智能体强化学习的交通信号控制上优于
贪婪策略,基于此,本文选择使用UCB算法去选择智能体k执行的动作:
(22)
其中,
表示访问状态
的次数,
表示目前为止在状态
下动作c被选择的次数。
因此,提出了MF3DQN-TF算法,伪代码如算法1所示。
算法1:MF3DQN-TF算法
输入:为所有智能体
初始化主网络参数
、目标网络参数
和平均动作
;初始化经验回放器
。
a) 预训练Self-Attention Layer模块。
b) for
to E do
c) 初始化所有交叉口的观测值
d) while
do
e) 利用Self-Attention处理交叉口的观测值,得到交叉口的联合状态
f) 根据公式(22)为每个智能体k选择动作
g) 执行联合动作
,观察得到的奖励
和交叉口的新观测值
,并利用Self-Attention得到新的联合状态
h) 计算平均联合动作
i) 将样本
存储到经验回放器
中
j) for
to
do
k) 从经验回放器
中随机取出
个样本
l) 根据公式(19)计算智能体k的目标值
m) 通过最小化公式(20)更新主网络的模型参数
n) 每隔C次迭代,根据公式(21)更新目标网络的模型参数
o) end for
p) end while
q) end for
4. 模拟实验
本节中,在多交叉口的情景下评估本文所提模型,并与其他流行的多智能体深度强化学习算法进行对比实验。实验仿真平台是在交通信号控制领域中广泛使用的SUMO。
4.1. 实验设置
为了更加准确的验证本文所提模型,本实验参考现实世界中的城市道路网络,在SUMO中设计了一个包含49个交叉口的交通网络环境,如图5所示,其中每条道路的长度为200米。每个交叉口详细地车道划分以及交通相位设置如图2所示,
,
。网络中车辆的长度为5米,加速度为5 m/s2,减速度为10 m/s2。在仿真环境中,交通流量的设计非常重要,为了模拟现实世界中的车流量,设置了四组不同的交通流,每组交通流的峰值分别为1100 vec/h、660 vec/h、925 vec/h、555 vec/h。由于实验中每个回合的模拟时间为60 min,所以每个时间段设置不同的交通流,前两组交通流在前40 min每隔5 min模拟一次,模拟的交通流分别为峰值的[0.4, 0.7, 0.9, 1.0, 0.75, 0.5, 0.25]倍,后两组交通流在15~55 min内每隔5 min模拟一次,模拟的交通流分别为峰值的[0.3, 0.8, 0.9, 1.0, 0.8, 0.6, 0.2]倍。
实验中对每一种MARL算法都训练了700个回合,每个回合包含3600个时间步长,详细的算法参数见表1。除此之外,对于预训练Self-Attention Layer模块,采用了Transformer的结构去训练。数据集为仿真交通网络中随机生成的一个回合的数据,共720 × 49组数据,这些数据按照8:2的比例分为训练集和验证集。共训练200个回合,在训练的过程中,损失函数使用均方误差函数计算,选择了学习率为0.0001的Adam优化器。训练好的Self-Attention Layer模块用来预测当前相位下每条入站车道的注意力值,为MF3DQN-TF的联合状态提供观测值。
4.2. 对比方法
为了证明本文所提模型的正确性和有效性,本实验将MF3DQN-TF算法与下列流行的MARL算法在相同的流量场景下进行比较。对于所有的算法,状态空间、动作空间和奖励函数的设置和本文定义的完全相同。
DQN:最原始的DQN算法,所有超参数的设置和本文完全相同,和MF3DQN-TF算法相比,网络架构和目标Q值的计算方法都不一样,而且没有注意力模块处理观测值。
Figure 5. Traffic network simulation environment
图5. 交通网络仿真环境
Table 1. Parameters of the algorithm
表1. 算法的参数
DDPG:结合了深度强化学习和确定性策略梯度方法,由Actor网络和Critic网络组成,Actor用来生成动作,Critic网络用于估计状态价值函数。除了Actor网络的优化器学习率为0.0001,Critic网络的优化器学习率为0.001外,其余超参数和本文设置的相同。
MA2C [12] :在交通信号控制领域中一种比较先进的基于策略梯度的MARL算法,智能体之间通过共享经验以学习全局最优策略。其网络结构与文献 [12] 中完全一致,其余超参数设置和本文设置的相同。
4.3. 实验结果与分析
在多智能体深度强化学习算法中,除了奖励函数这一评价指标外,本文还设置了车辆等待时间、车辆行驶速度和交叉口队列长度作为交通性能指标。
图6展示了各算法在训练过程中的奖励曲线(阴影部分表示标准差),本文的算法目标是为了最大化奖励函数。从图6中可以发现,在复杂的交通环境中,DQN算法表现最差,整体曲线呈现下降趋势,大部分奖励值一直处于小于−2500的范围,说明DQN算法并没有完全学习到环境的规则,其简单的算法结构无法适应复杂的交通环境。相比之下,DDPG算法和MA2C算法的奖励曲线远远优于DQN算法,其中,MA2C的奖励值范围在−2000到−1000之间,DDPG算法的奖励曲线在整个训练过程中都比较平稳,奖励值一直维持在−1500左右,也就说明它无法找到更好的策略,遇到更加复杂的环境难以学习最优策略。较为先进的MA2C算法相比于DDPG并没有明显的优势,这是由于MA2C算法对于智能体的数量非常敏感,而且涉及到的超参数也非常多,寻找到所有的最优超参数非常困难。本文提出的MF3DON-TF算法在训练开始阶段学习到的奖励就优于其他对比算法,奖励值直接上升到了−1000左右,此后一直在大于−1000的范围,虽然在训练后期有些波动,但是这些波动表明了算法仍然在探索,试图寻找更好的策略,从曲线的650回合到700回合中可以看到,MF3DQN-TF算法收敛到了−500,证明MF3DQN-TF算法确实找到了比之前更好的策略,说明本文提出的算法是有效的,且优于其他对比算法。
Figure 6. Reward curves of each algorithm during the training process (larger is better)
图6. 训练过程中各算法的奖励曲线(越大越好)
除了奖励曲线外,一些交通指标也能说明本文所提算法的正确性和有效性。图7展示了训练过程中各算法下车辆的等待时间。DQN算法的表现仍然是最差的,车辆的等待时间超过了100 s,相较于其他算法来说非常久。DDPG算法下的车辆等待时间一直维持在50 s左右,没有比较明显的改善。MA2C算法在训练初始阶段时车辆的等待时间比较短,达到了45 s,但是到了后期,有可能是遇到了比较拥堵的情况,无法执行正确的动作,导致车辆的等待时间增加到了50 s以上。虽然MF3DQN-TF算法也遇到了这种情况,但是该算法的学习能力非常强,有了这种经验后,很快就将车辆的等待时间缩短到了正常水平,而MA2C算法却很难使车辆再回到较短的等待时间。
Figure 7. Waiting time curves of each algorithm during the training process (smaller is better)
图7. 训练过程中各算法的等待时间曲线(越小越好)
此外,本文还总结了各算法的平均交通性能指标,如表2所示。本文所提出的MF3DQN-TF算法的平均车辆等待时间相较于DQN减少了69.80%,相较于DDPG减少了22.28%,相较于MA2C减少了28.13%。就平均车辆速度来说,MF3DQN-TF相较于DQN增加了15%,相较于DDPG增加了27.92%,相较于MA2C增加了30%。对于平均队列长度,MF3DQN-TF相较于DQN和DDPG减少了33.33%。
Table 2. Average traffic performance metrics of each algorithm
表2. 各算法的平均交通性能指标
5. 结论
本文中,提出了一个基于MF3DQN-TF算法的交通信号控制模型。实验结果证明,在3DQN算法的基础上引入平均场理论,大大降低了状态动作空间的维数,从而使得模型在训练的过程中同其他算法相比收敛速度加快。同时,在模型中添加的自注意力机制对交通数据之间内在联系的分析,从交通性能指标上看,确实帮助了智能体快速的了解到交通信号控制规则。具体的,本文所提出的算法在奖励值、平均车辆等待时间、平均车辆速度、平均队列长度等指标上均优于DQN、DDPG、MA2C算法。对于多交叉口交通信号控制的研究不仅能在一定程度上有效缓解城市道路的交通拥堵问题,而且会伴随着经济增长和环境改善等优势。未来的工作中,需要继续研究更加先进的、更加实用的多智能体强化学习算法,并应用在现实世界中,为我们不断发展的社会解决城市交通拥堵问题。