第51卷第1期山东大学学报（工学版）
J O U R N A L O F S H A N D O N G U N I V E R S I T Y (E N G I N E E R I N G S C I E N C E)2021年2月Feb. 2021
Vol.51 No.l
文章编号：1672-3961 (2021}01-0100-08D O I： 10.6040/j.i s s n. 1672-3961.0.2020.247
实际环境中基于深度2学习的无人
肖浩1，賡祝华1’2**，刘毅志1’2，刘思林1，刘建勋1’2
(1.湖南科技大学计算机科学与工程学院，湖南湘潭411201; 2.知识处理与网络化制造湖南省普通高校重点实验室，湖南 湘潭 411201)
摘要：实际交通环境规划最优路径的重要问题是无人车智能导航，而无人车全局路後规划研究主要在于模拟环境中算法求解速度的提升，考虑大部分仅路径距离最优或局限于当前道路的自身状况，本研究针对实际环境中的其他因素及其未来的变化和动态路网中无人车全局路径规划的复杂任务，基于预测后再规划的思想提出面向实际环境的无人车驾驶系统框架，并结合深度G学习和深度预测网络技术提出一种快速全局路径规划方法（deep prediction network and deep 0 network, D P-D Q N)，从 而利用时空、天气等道路特征数据来预测未来交通状况、求解全局最优路径,：基于公开数据集的试验和评价后发现，本研究提出的方法与Dijkstra、A•等算法相比，行车时间最高降低了17.97%。
关键词：路径规划；交通环境；城市路网；深度2学习；深度预测网络
中图分类号:TP311 文献标志码：A
引用格式：肖浩，廖祝华，刘毅志，等.实际环境中基于深度！3学习的无人车路径规划j].山东大学学报（工学版），2021,51(1):100-107.
X I A O H a o,L I A O Z h u h u a,L I U Y i z h i,e t al. U n m a n n e d v e h i c l e p a t h p l a n n i n g b a s e d o n d e e p Q l e a r n i n g i n r e a l e n v i r o n m e n t[ J].J o u r n a l o f S h a n d o n g U n i v e r s i t y( E n g i n e e r i n g S c i e n c e), 2021,51(1)：100-107.
Unmanned vehicle path planning based on deep Q learning in real environment
XIAO Hao1, LIAO Zhuhua12*, LIU Yizhi1'2, LIU Silin', LIU Jianxun1'2
(1. School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, Hunan, China；
2. H u n a n Provincial K e y Laboratory of Knowledge Processing and Networked Manufacturing, Xiangtan 411201, Hunan, China)
Abstract ：I t was an important problem for the intelligent navigation of unmanned vehicles that planning the optimal path in the actual traffic environment. At present, m a n y researches about global path planning of unmanned vehicle mainly focused on the improvement of algorithm solution speed in the simulation environment. Most of them just only considered the optimal path distance or the current road conditions, also ignored other factors and future changes in the actual environment.
In order to complete the complex task that competing global path planning of u n m anned vehicle in dynamic road network, this research put forward a framework of unmanned vehicle driving system for practical environment based on the thought of planning after prediction, and put forward D P-D Q N which was a fast global path planning method combined with deep Q learning and deep prediction network technology. This method used the road characteristic data such as time and space, weather et a l to predict the future traffic situation, and then competed the global optimal path. Finally, experimental results based on open datasets showed that the proposed method reduced driving time 17.97% at most than Dijkstra, A* ,algorithm et a l.
K e y w o r d s：global path planning；traffic environment；urban road network； deep Q learning； deep prediction network
收稿日期：2020-06-28；网络首发时间：2020-丨()-丨6丨5:29:24
网络首发地址：h t t p://k n s.c n k i.n e t/k c m s/d e t a i l/37.1391 .T.20201015.1717_002.h t m l
基金项目：国家科学自然基金资助项目（61370227)；湖南省自然科学基金资助项目（2017J J2081，2018J J4052)；湖南省教育厅重点资助项目(17A070,19A172，19A174)；科学研究资助项目（17C0646,19C0755)
第一作者简介：肖浩（1995_)，男，四川成都人，硕士研究生，主要研究方向为机器学习和路径规划.E-m a i l:x i a o h a o l217@ f o x m a i l.c o m
*通信作者简介：廖祝华（1977—)，男，湖南株洲人，副教授，硕土生导师，主要研究方向为数据挖掘和移动计算.E-m a i l:Z h l i a〇@ h m i s t.e d u.c n
第1期肖浩，等：实际环境中基于深度2学习的无人车路径规划
101
〇引言
无人驾驶技术在学术界和工业界都受到了极 大的关注，已有商业公司实现了小范围的道路试
验，如Google 无人驾驶汽车和特斯拉的Autopilot 系统[1]等，但在实际环境中的无人车路径规划方法 研究仍然存在很多技术挑战和困难。例如，在面对 城市级别的地图网络时，搜索的空间非常庞大。并 且随着城市不断发展，交通系统变得日益复杂和拥 堵，最优路径通常并不是最短路径[2]，而是最快 路径。
针对庞大地图中路径规划算法复杂度问题， 目前的研究有启发式搜索、地图预处理或优化搜 索空间的
数据结构。而针对最快路径问题通常利 用实际环境中的传感器，通过监测时变路网的路 况变化来求解。然而，上述优化算法复杂度的路 径规划方法是基于静态路网的，基于时变路网的 方法又需要额外的开销，也没有考虑影响交通环 境的潜在因素。
为了解决上述问题，本研究提出结合深度预测 网络和深度2学习的深度强化学习路径规划方法
(deep prediction network and deep Q network, DP-
DQN )，利用现有的庞大数据，无需额外布置传感 器，分析路网运行规律，先预测道路通行时间然后 高性能地快速求解全局最优路径。这样不仅避免 了在大型路网中基于搜索的路径规划方法时间复 杂度高的问题，还能很好地利用现有综合不同影响 因素的交通行为数据，预测未来道路情况的复杂变 化并求解出最短行车时间的路径。对此，本研究的 主要贡献如下：
(1)
提出了面向实际环境的无人车驾驶系统框
架，从而使无人车驾驶系统更好地适用于实际多因
素变化环境。
(2) 提出了 DP -D QN 路径规划方法来计算最
优路径，综合各种交通相关因素预测实际环境中
的路况变化，为无人车快速规划最短行车时间 路径。
(3)
在DP -DQN 算法中，设计一个向量转换层 以保证特征向量的编码在深度预测网络和2网络 中的一致性，使得2网络可以利用深度预测网络的
输出作为奖励设置来优化寻路策略。
(4) 通过映射动作空间进一步优化0网络的 结构，使得2网络收敛速度加快，训练完成后，能够 在较短时间内计算最优路径。
1相关工作
近年来，城市路网环境中的无人车全局路径规
划研究主要集中在优化算法运行性能上。例如
Hart 、Nilsson 和Raphael 提出的A *算法i 3]，相比于 最短路径问题的标准解决方案Dijkstra 算法14]，该 算法利用启发式函数缩减了搜索空间，将原本无方 向的广度优先策略变成了朝着目标的搜索。随后， 文献[5 ]优化了 A ^算法中对被遍历节点排序时所 用的数据结构，基于二进制堆、斐波那契数列、优先 级桶和二级桶等数据结构进一步提升算法的运行 速度。另一种加速全局路径规划算法性能的方法 是对地图进行预处理，例如基于地标和三角形不等 式图论下界的A #搜索技术（A * search landmarks and the triangle inequality ，ALT )丨6，它使路径规划 算法在长距离搜索过程中可以跳过部分顶点，以此 来缩短算法时间。还有一种方法是深度2学习 (deep 0 network , DQN )[7]，它可以使得路径规划 算法在运算过程中以贪心策略选择节点，无需对遍 历节点排序。
虽然这些方法提高了求解最短路径的速度，但 是它们大多数考虑的还是路网距离等浅层信息，在 实际的交通网络中，道路的状况往往取决于当前的 时刻、天气和人员流动等交通相关因素W 。例如某 些主干道路在高峰时间会持续拥堵，市区省界进出 口道路在节假日期间车辆会排起数小时的长龙，当 某些路段大雾或者大雪结冰时，行车速度将被限制。基于路况变化的全局路径规划研究方面， Thomas 等[9]使用高斯过程回归估计传感器覆盖率
低的区域的交通流量，基于离散概率图形模型的中 间预测的空间回归条件来合并历史数据，提出了基 于实时交通预测的动态全局路径规划方法。Wan
等[1<)]在传统交通预测方法的基础上，提出了一种移 动体感应技术，以支持希望避免拥堵的驾驶员进 行动态路线选择。文献[11]提出了动态A •地标三 角形算法，它是一种基于面向地标和最短路径树的
方法。当路网的边权重发生改变时动态更新最短
路径树，重新计算最优路径。上述研究采取先感知 后预测的方法来估计交通流再进行全局路径规划
的办法，一定程度上解决了路网动态变化的问题， 但它们都依赖短期内交通速度传感器的数据，需要 额外的硬件布置，并没有考虑影响路网通行时间的 其他因素，也没有解决动态规划的时间复杂度问题。
102
山东大学学报（工学版)
第51卷
图2 D P -D Q N 算法框架 Fig.2 D P -D Q N method framework
3.1城市路网拓扑图的建立
在城市中进行无人车全局路径规划时，通常将 城市路网地图视为一个有向加权图，图定义为
G ^(V ,E ,W ),
( 1)
式中：v , e V 表示道路交点e £表示道路，v v , e V V 表示对应道路权重。W K T 文档中的道路是通过经 纬度坐标点来标记的多线段，其中每条道路还具有
唯一的id 标记。而路网拓扑的建立主要是通过匹 配不同道路重合的标记点出交叉路口，交叉路口 即为图G 上顶点V ，如图3所示。
而对于城市路网拓扑来说，当使用道路长度表 示其对应权重W 时路网是静态的，使用道路通行时
间表示其对应权重W 时路网是动态的。因此，最短 行车时间路径规划问题应将道路通行时间A 作为权
重设置，即W =/i 。
103.975 104.000 104.025 104.050 104.075 104.100 104.125 104.150 104.175
经度/(°)
(a)整体路网拓扑图
道路拓扑图
2面向实际环境的无人车驾驶系统
交通变化通常是由多种因素造成的，文献[8]
指出道路基础、天气状况和人员流动是主要的3大 因素。而在本研究的相关数据中，城市路网拓扑描 述了道路基础的空间分布，历史天气记录了城市的
气象变化，兴趣点（point of interest , POI )分布表明 了人员流动的潜在规律。因此，本研究基于这3个 方面的数据提出面向实际环境的无人车驾驶系统 框架，如图1所示，以满足无人车系统对计算最短行 车时间路径的需要，使无人车避开未来可能出现的 拥堵
，一
定程度上地减缓交通压力，应对道路资源
无法短时间内增长的情况。
在图1所示的框架中，首先，无人车的目的地 被传人到驾驶系统的全局路径规划部分，通过DP - D QN 算法利用天气、P O I 和道路数据汁算出一条 最优路径；其次，无人车的决策系统获取自身感知 和定位信息；然后，无人车运动规划模块生成一个 满足完整约束、沿着既定路线前进的轨迹；最后， 进行运动、反馈控制、重定位以纠正行驶时的误差 和偏移。
3 DP-DQN 路径规划方法
DP -DQN 路径规划方法主要包括3个部分：城 市路网拓扑图的建立、道路通行时间的预测和最 短行车时间路径的规划。整个路径规划方法框架 见图2。在地图建立的过程中，通过处理滴滴数据 集的WKT ( well-known text )文档，对照空间参照 系统转换其中的矢量几何对象，生成城市路网 拓扑。
®处理路况向量
向
1转
换
第1期肖浩，等：实际环境中基于深度2学习的无人车路径规划103
图3成都市路网拓扑图
Fig.3 Topology of Chengdu R oad Network
本研究使用文献[12]中提出的适合路网的存 储结构（带有前向关联边的邻接表）来存储城市路 网拓扑。该数据结构包含了边的具体信息，还可以 额外记录交通禁则关系（如禁止左转、掉头，限速 等）。路网存储转换如图4。
图4路网存储转换示例图
Fig.4 Road network storage conversion example diagram 3.2道路通行时间的预测
对于该预测过程，本研究从路网拓扑、天气数据、POI数据和交通指数数据中提取每条道路的相关特 征，然后生成由路况向量表示的训练样本。其中，提 取道路id、天气、时刻、道路通行时间的详细步骤见3.1。
兴趣点分布
dp,.= (e,'，”,.），(2)式中:e，表示兴趣点分布所在的具体道路，《，表示 对应道路附近兴趣点总数。
对于POI分布特征的提取，本研究使用基于距 离的聚类算法f M eans处理PO I数据，以得到道路 附近的兴趣点数量《。具体的距离度量
dis= l^p-^l+ l^p-^l ,(3)式中：为P〇I经纬度坐标，表示的是道 路段的经讳度标记。聚类个数&为道路段经纬度标记数量，确定的&使得聚类结果比较直观可靠，如图5。
104.00 104.02 104.04 104.06 104.08 104.10 104.12
经度/(°>
图5 P O I聚类结果
Fig.5 Example of PO I clustering results
最终得到的路况向量包含特征向量•》：和目标向
量包含的特征为
[x = (idx,t,dip,m)
U，(4)式中：idx为道路下标，f为时刻为对应天气,/I是
道路通行时间。它们共同构成特征向量，表示在某 道路、某时刻、对应天气下的道路通行时间。
本研究面对的预测道路通行时间是一个回归问题。一般地，冋归常用损失函数为均方误差(mean squared error, MSE)和平均绝对误差（mean absolute error, MAE)[13]。除此之外，分类网络的评 价指标不适用于回归网络，本研究采用了平均相对 偏差（average absolute relative deviation, AARD)作 为评价指标。回归网络架构与分类网络也不同，网络的最后一层只有一个单元，没有激活函数，是一 个线性层。因为激活函数会限制输出范围，不适用 于回归网络。MSE、M A E和A A R D的公式为
M SE=丄f (兄.->〇2,(5)
M A E=丄免I(乃-y:)I，(6)
n y.—y r-
AARD = 100 x Y|------1 /«, (7)式中:y,.是原始的正确数据，是神经网络计算出的 预测值。本研究为了更好地分析路网运行规律，使 用了深度神经网络（deep neural network,DNN)、普通循环神经网络（recurrent neural network，RNN)、长短期记忆网络（long short-term memory, LSTM)、门控循环单元网络（gated recurrent unit, GRU)作为深度预测网络对比估计道路权重W，并 且定量分析了 M AE与M SE两种loss函数对上述不 同网络回归结果的影响，见表2。最终本研究根据 预测误差和开销择优选择了使用M A E作为lo ss函 数的DNN
网络，城市路网拓扑有向图边的权重用网
104
山东大学学报（工学版)
第51卷
图6 深度预测网络回归预测结果示例
Fig.6 D e e p prediction network regression prediction result
络回归估计的结果表7K
W ； =
h t
=
f
(
X i )
=/(
idi ,/,.,dip ,.,m i)0
(
8)
3.3 最短行车时间路径的规划
城市路网拓扑图中的无人车全局路径规划可定 义为尸=丨即在城市路网拓扑图G 中求解无人 车路径请
求《=(K f 〇，dip 0，m 。），其中分别代 表起终点,?。、_。爲代表起点时刻、P O I 分布和天 气，此定义下即使是相同出发点和目的地，其规划结 果可能不相同。最终无人车全局路径规划问题的解 可表示为户=i VoWo ’V , ，v 2，V …丨，其中V 。 是起点,v …是终点，j
，…，
|是无人车。
沿规划路径行驶经过的各条道路，则总行车时 间//为对应行车边的权重之和：
n
n
w
= 2>, =
(9)
/=0 1=0
式中?…为无人车到达终点时的时刻。在本研究智能 体与环境交互的路径规划任务中算法目标就是最 小化总行车时间。对此，本研究基于D Q N 算法，建 立了一个2网络来逼近无人车系统的状态动作值函 数。该网络的输入是通过预处理后的车辆状态向 量，输出是无人车每个可能动作的2值。
DQN 使用神经网络来近似Q 值函数，神经网络 的输人是状态s 和动作a ，输出是0(s ，a )D 当通过 神经网络计算2后，DQN 使用s -greedy 策略来选择 动作。环境接收到此动作后会给出一个奖励及下 一个状态。这是一个步骤，此时根据去奖励更新值 函数网络的参数。接着进入下一个步骤。如此循 环下去，直到训练出了一个稳定的值函数网络。DP -DQN 方法中向量转换层的主要功能是将实 际环境中的时间、天气、P O I 分布、路网顶点和道路
—
真实值
进行同样的编码，确保特征向量在2网络和深度预 测网络中正确地相互转换。本研究还在DP-DQN 算法的状态表示中加人了起始和目的地位置，以阐 释在实际的时变条件下，道路的2值在同样路况下 随起终点的变化而不同。DP -DQN 算法中的状态和 奖励等相关设置如下：
(1) 状态设置
状态空间是智能体从环境中获取的路径规划 信息集合，它是DP -D Q N 算法中0网络的特征向 量，其表达式为
s , = (id ,, id 0, id …, /；) D (10)
式中:id ；表示当前所在顶点编号，idQ 和id …分别表
示起点和目标点编号，卩是当前时刻。
(2) 奖励设置
DP -DQN 算法即时奖励设置为深度预测网络回 归结果的负数，以此来正确运行最大化奖励的强化 学习机制完成规划总行车时间最少路径的任务6 奖励设置函数表达即为
〇，状态\为终点
(I I )
-/u ,_)，其他情况
(3) 动作设置与优化
本研究将算法运行过程中可扩展的邻接道路 作为智能体在每个状态下的合法动作，但所有道路 的下标都是唯一的，对此，本研究根据城市路网拓 扑图通过序列映射路网中每一个顶点为可选序列湖南汽车网
|1，2,…，々丨，专5，而且在路网中通过索引都可以 查出对应的道路。而按照原始动作空间设置，将 所有道路作为可选动作会使得网络结构复杂，而且 在迭代初期,Agent 大概率会选择无效动作。对比 结果见图6。
—*实值 —估韻
.s U I /
I f f l -f e
l t i r
oodlm
i s (N
o o o o
d o I
000 亡
曰0000:3
〖刻 M
时；=：
(b
0000"60
—
00_€0
00000
o o .f t N
o o o s (N
0000:81
00:i
0000:31
# 月
c £r
3
(a )
00000<0
O O H i o
01
000000
.s s /f a f l t i
F
发布评论