交通场景下基于深度强化学习的感知型路径分配算法

曹 欢

(中国科学技术大学 信息科学技术学院，安徽 合肥230026)

0 引言

目前我国交通环境日益复杂，现有交通体系的服务能力难以满足城市居民的出行期望，城市面临日益严峻的交通管理挑战。研究者们希望借助交通数字孪生技术，通过数据驱动、精准建模，实现交通的模拟、预测诊断和优化[1]。然而在交通仿真模拟层次，现有的路径分配模块不能反映出现实交通的多变状况。在人-车-路的核心体系中，天气气候、交通管制、突发事故等影响因子将时刻影响驾驶员的判断以及路网的状态[2]。

在当前的交通数字孪生系统中，现有的路径分配方法主要分为两类，第一类为用于实现静态全局路径最优的传统算法，如经典的蚁群算法、Floyd 算法、A-Star、粒子群算法、Dijkstra 及其改进算法等，本质为基于图论中重要的最短路径问题所提出的各种方案，也即在一个加权有向图中，按一定要求寻找一条权重总和最短的路径[3]。如Xu[4]等基于二叉树结构，通过双向搜索方法加快搜索效率，作为A-Star 改进算法；Lee[5]等基于遗传算法实现蚁群算法中的参数调节优化。在路网信息发生变化时，该类算法难以做出及时反馈。如果需要满足动态路径规划的需求，则需要施加额外的更新优化和重规划机制。第二类指的是通过机器学习、时空神经网络、强化学习等技术来实现路径分配。这一类更加强调数据的搜集、分析和处理，通过提取海量历史数据的价值信息，为解决路径规划问题提供了一个新的思路[6]。

本文的中心工作是研究了一种基于传统路径算法与深度强化学习的感知型路径分配算法，首先通过改进版Dijkstra 算法为所有车辆分配初始路径，路网中的车辆在不断感知当前位置、行驶轨迹以及目标路网中各路段的车流等信息后，通过DDQN(Double DQN)将自动选择是否重新进行全局的路径规划，实现路径更新。与现有的经典路径规划方法相比，本文提出的规划方案填补了传统模型在路况变化下的泛化性、拓展性不足，优化了深度学习型方法的资源损耗，同时基于强化学习模型在长期收益方面的优越性，本文模型更加满足路径分配模型对当今城市路网交通出行的各种需求。

1 理论基础

1.1 动态交通路网下的路径分配问题

交通路网可以看作一个有着时序变化的有向图网络，将其作为一段时间内的状态集合，即为：

其中，T 指的是时间周期，在规定的T 内，可以将动态交通路网拆成静态的网络即G。网络G 由路段集合以及路网节点集合构成：

其中，vi∈V 指的是路网节点，i 为节点编号，ej∈E指的是有向边路，j 为边路编号。可以看到，不同的时间周期T 下，路网也会动态变化得到随时间更新的网络G1，G2，…，Gi，表征不同T 下的路网状态。同时，路径L 正是由路网节点中的多个节点组成的联通路径构成的，而重要的两个节点——起终点(Origin-Destination，OD)同样来源于集合V。因此，L 可视为(v0，v1，v2，…，vd)这一相邻节点集[7]。

为衡量路径选择的优劣，可通过定义道路代价函数的具体表达式来实现，假设(va，vb)是取自路径L 中的任一邻接节点集，则该集对应的代价函数为：

不同于常见的距离度量如欧式距离、马氏距离，上式中的δ 是与时间相关的时序函数即δt，因此路径L 经过相邻节点集(v0，v1，v2，…，vd)的总代价为：

上式中的n 为时间步，因此动态路径分配的问题可以理解为在路径连续邻接边的集合上的代码函数min(WL1，WL2，…，WLn)，优化目标为总代价最小。进一步沿着时间步展开，即基于时间t 的OD 路径分配优化问题如下：

上式指明行驶个体在每一个特定周期T 中，都将以最小化代价函数的策略原则移动。其中的[·]表示T 时刻内的出行路线，l 指的是路径中的各相邻路段[3]。

1.2 强化学习在动态路径分配中的应用

为提升动态路径分配的拓展性和真实性，目前的一些动态模型大多以路网中的重要交叉口为决策点，不断更新全局路径分配结果，同时与车辆行驶线路进行比较，判定是否需要路径更新。亦或是通过对路段设置阈值参数比如拥堵系数、排队时长等，如果感知到车辆即将面临严重拥堵，系统将更新路线。以上的解决方案具备一定的感知性和动态拓展能力，但有着难以忽略的缺陷。前者由于大量冗余的复杂运算造成资源损耗，后者往往只依据相邻路段的拥堵状况来决策，未能考量到路网中路径分配是一个需要最大化长期收益的问题[8]。

车辆在前进过程中，到达靠近路口前的一段区域时，就需要重新进行线路规划，然后决定行驶方向。当前时刻的车辆状态以及选择的工作决策会影响下一时刻行驶车辆的状态，故上述问题是一种较为典型的马尔可夫决策过程(MDP)，具备引入强化学习的潜在优势[9]：一方面可以提升全局路径分配的长期收益，另一方面可以高效地开展分析和决策，实现动态路线更新。

考虑到本次任务较为离散的动作空间以及动态路网环境下状态空间的连续性，本文最终采用了DQN 的优化模型DDQN，后文会详细介绍。

2 基于深度强化学习的路径分配模型建模

2.1 模块设计

图1 展示的是整体的模块设计，主要分为两个阶段：阶段一是通过改进版Dijkstra 实现初始路径分配决策，阶段二则是在阶段一的基础上实现强化学习训练，完成决策更新。具体如下：

(1)路网静态信息获取模块需要获取相应路网结构信息、路网中路段信息以及连接关系等。

(2)路网动态信息获取模块需要获取建模区域内各路段的车流数据，包括平均车流密度等。

(3)行驶车辆信息集成模块的任务是确定车辆行驶中的具体信息，包括起终点路段ID、当前路段ID 以及邻接路段ID。

(4)State Space(状态空间)模块整合路网信息和车辆自身行驶信息，并对其进行数值化转化，将编码后的向量作为车辆状态。

(5)Action Space(动作空间)模块负责明确Agent(智能体，在本任务中指的是路网中的车辆)和环境交互过程中所有潜在行为的Action 集合。同时，在这一部分需要制定马尔可夫决策过程中Agent 选用不同Action 的策略规则，较为常见的包括Q 值最大化策略以及贪心策略(ζ-greedy 或UCB)等。

(6)Reward 反馈模块则主要定义了强化学习问题中的学习目标，在每个时间步，环境向Agent 发送一个称为Reward 的反馈，进而实现训练。Agent 的唯一目标是最大化其长期收到的总收益。

(7)Agent 设计/动态路径分配模块便是具体的学习、训练、预测部分。

2.2 算法设计

2.2.1 Dijkstra 算法及改进

区别于仅使用深度学习等技术的复杂动态分配算法，本文算法以Dijkstra 改良算法为基础进行强化学习决策前的初始化路径分配工作。

Dijkstra 算法基于贪心的思想，以当前点为圆心不断向四周扩展进行路径搜索，搜索寻优过程没有考量目标点的位置以及方向，因此在这一寻优过程中所有点被搜索的概率一致。而交通路网中，往往会有起终点过远、可选点众多这一问题，因此，将Dijkstra 直接用于动态交通条件下的路径分配问题时，会出现效率低下、资源损耗严重的挑战。这种计算延迟也同样不符合实时性的要求。

因此本文希望提升Dijkstra 算法在路径分配方面的运算效率，减少计算时长。Dijkstra 算法时间复杂度是O(n2)，以城市交通路网为例，将其视为若干带权有向图，其中大多数城市交叉口数目远大于1 000，在此数量级上，资源损耗时长将呈现指数增长，产生大量冗余运算。

在此本文设定优先目标区域，在优先区域内路径寻优，假设起终点a，b 坐标依次为(x0，y0)，(x1，y1)，以a，b 为圆心绘制圆形区域，再对上述两圆形区域分别做外切线，形成优先搜索区域矩形，如图2 所示。如未能搜索到最优结果，将在此基础上拓展圆形区域半径，在新的优先区域上实现搜索。

图1 基于深度强化学习的路径分配模块设计

2.2.2 状态空间

在基于DDQN 的模型中，智能体进行判断的主要依据为车辆自身信息和感知区域内路网中各路段的车辆密度数据，在对单个路段进行编号后，需要通过信息整合实现状态描述。本文最终选取一维向量进行状态s 的表达，这种表示方式有利于提升模型训练效率和表示的准确性。

Agent 在t 时刻的状态定义为：

其中cart表示前面提到的车辆当前时刻t 的自身信息变量，包括出发点、当前点、当前路线预计的下一到达点以及目标点对应的路段ID，即：

同时，roadt指的是路网中各路段的交通流密度数据变量，表达式如下：

其中n 为路段总数目，ρi表示第i 条路段对应的平均车流密度。在上述基础上继续开展动作空间设计。

2.2.3 动作空间

鉴于本文中的DDQN 模型是在改良版本的Dijkstra上进行路径优化，即车辆依据当前状态判定是否需要更新路径分配结果，因此这里的动作空间得以极大简化，可以定义为：A=[a0，a1]。a0表示无需进行路径更新，当前路线即为最优；a1表示当前路线需要优化，需重新调用路径分配模型实现更新。

值得强调的是，为了防止系统回溯这一冗余操作，减少历史选择路线对现有模型的噪声干扰，必须记录历史途径信息，防止Agent 趋于过度判断。同时考虑到强化学习的Exploration & Exploitation(探索与利用机制)，模型选用的动作选择策略如下：

该策略既能以较大概率选择Q 值大的动作，也保留了较小概率的探索能力。

2.2.4 奖励函数

强化学习的标准交互过程如下：每个时刻，智能体根据其策略(Policy)，在当前所处状态(State)选择一个动作(Action)，环境(Environment)对这些动作做出响应，转移到新状态，同时产生一个奖励信号（Reward)，这通常是一个数值，奖励的折扣累加和称为收益/回报(Return)，这是智能体在动作选择过程中想要最大化的目标[10]。

图2 优先搜索区域示意图

本模型的优化目标着眼于最小化车辆到达目标点的行驶总时长。Agent 采取动作后，状态开始转移，即在当前决策点/区域进行路径重分配判断后，将花费一定时间到达下一个决策点/区域，因此Agent的行驶总时长可以视为每相邻决策点的时间间隔总和，再加上额外的路口等待时长、拥堵排队时长等。因此定义奖励函数为：

其中ti为从第i-1 个决策点到达第i 个决策点的时间间隔，tdelay为对应时期的各种等待时长，琢为自定义等待权重系数，可根据实际需要调节。该奖励函数能够保证模型会趋于行驶时间短的邻接路线，获得短期激励。通过取相反数也能够综合考量等待时长对决策的影响，符合长期收益原则。

2.2.5 DDQN 训练模型

DDQN 是Double DQN 的缩写，是在DQN 的基础上改进而来的。DDQN 的模型结构基本与DQN 的模型结构一样，唯一不同的就是它们的目标函数：

DDQN 与DQN 结构类似，其模型结构如图3 所示。DDQN 包含两个结构完全相同但是参数存在差异的网络，预测Q 估计的主网络MainNet 使用的是最新的参数，而预测Q 现实的目标网络TargetNet 使用的是较早前的参数。主网络MainNet 的输出Q(s，a；兹i)用来评估当前状态-动作对的值函数。目标网络TargetNet 的输出Q(s，a；)可以用来求解目标Q值。当智能体对环境采取动作a 时就可以根据上述式 (12) 计算出Q 值并根据损失函数更新主网络MainNet 的参数，每经过一定次数的迭代，将主网络MainNet 的参数复制给目标网络TargetNet。这样就完成了一次学习过程[9]。

基于模型状态空间设计，本文通过一维多元向量描述智能体状态，同时采用了多层感知机(Multilayer Perceptron，MLP)作为Q_value 网络，MLP 中隐藏层数目为3，每一层包含2×(N+3)个神经元。最终的训练模型包括输入层、3 层全连接隐藏层以及输出层等结构。基于图3 所示神经网络模型结构进行训练，Loss 函数见式(12)，模型可输出两个Q 值。当前值网络用于更新现有参数，再经过时间间隔N 后将参数复制给目标值网络进行参数更新。

3 实验结果及分析

3.1 仿真场景

从开源网站Open Street Map 官网下载北京市部分路网，包括13 020 个路段以及9 873 个节点。在ArcGIS 软件中对获取的osm 地图文件进行读取修改，鉴于直接下载的路网文件存在大量低质量路段，因此将其编码成可读取的矢量地图文件(.shp)，然后进行数据清洗和分析，最终的路网呈现效果如图4 所示。同时，为进一步进行实验，提取了所在区域的所有路段编号ID、长度位置信息以及对应拓扑关系等。此外另采集了一天内该区域近3 000 辆浮动车的行驶数据。实验环境为Intel®I7-8750H CPU@2.20 GHz，64 GB 内存，Windows10 64 位操作系统。

图4 北京市路网文件

3.2 实验方案

将本文提出的路径动态分配方法分别与Dijkstra、A*、动态A*算法进行实验对比。其中DDQN的训练参数如表1 所示。

表1 DDQN 训练参数

为了捕捉路网动态信息对路径规划造成的影响,本文针对北京市路网开展两个时间点下的对比试验，选取的时间点依次为8:00 以及13:00。实验首先确定待观察的OD 点对，接着针对OD 点对分别在两个时间点上开展路径请求，各模型平均访问遍历节点数目如表2 所示。

表2 OD 点对访问节点数

从表2 可以看出，在算法搜索效率上，传统Dijkstra 算法效率最低，依据贪心策略展开搜索的Dijkstra 由于其复杂度为o(n2)，导致需要遍历的节点数最多，达到4 728 和4 435。A*以及动态A*算法相较于传统的Dijkstra 遍历节点数目分别下降32%以及61% ，这是基于这两个算法启发式的搜索策略[12]。本文模型的遍历访问节点数分别为1 430和1 230，相较最差的Dijkstra 分别有70%和72%的明显提升，均为最优，符合实验预期。另外由于8：00处于上班高峰期，因此拥堵现象会加重，模型感知到的信息更加复杂，会趋于做出更多尝试性的路径分配。

为进一步验证模型中深度强化学习在路径分配性能上的作用，实验综合纳入行驶时间、行驶距离以及延迟等待时间(车速小于1 m/s 的时长)作为具体的指标因子[13]。在这里本文额外加入了依据分层理论的CH 路径算法，指标记录如表3 所示。

表3 性能对比表

从表3 可知，本文提出的结合深度强化学习和传统静态路径分配算法的优化模型在行驶耗费时间以及等待延误时间上表现突出，其中行驶时间相较A*缩短14.91%，等待时间更是较于A*大幅减少35.93%。值得注意的是，在行驶距离这一指标上，本文模型表现略差于其他对比模型，这是由于在强化学习的奖励设计阶段，延误等待时间权重较高的影响，这也从另外一方面验证了本文模型出色的动态路径分配性能和深度强化学习在长期收益方面的优越性[14]。

4 结论

针对复杂多变的动态交通路网，本文提出了一种结合传统路径算法与深度强化学习的感知型路径分配算法，模型依据改进的静态路径分配算法生成路径分配的初始化结果，之后Agent 感知路网变化，包括当前位置、行驶轨迹以及目标路网中各路段的车流等信息后，通过DDQN 网络模型进行动作选择，完成状态转移，实现路径分配再更新。

经过大量仿真实验表明，相较于经典的路径分配模型，本文模型无论是在搜索寻优效率上，还是在最终的性能指标(行驶时间以及等待时间)上都表现出色，这一方面是由于对动态信息的搜集和感知学习，另一方面是基于深度强化学习独有的提升系统长期收益能力。