东南大学物联网交通应用研究中心
东南大学物联网交通应用研究中心
北京时间:
无人驾驶汽车运动规划方法研究综述
2018-09-10 15:20   作者:   来源:厚势和厚势公号:iHoushi   推荐人:冒培培   浏览:103   我要评论


1. 引言


  目前随着全球交通事故多发率的不断增长,交通安全和交通拥堵问题日益严峻。截至2017年5月,根据WHO道路交通伤亡分析[1]:每年因道路交通事故死亡125万人。在此背景下,无人驾驶技术受到了世界各方的格外关注,目前该技术己成为国内外研究的热点,最为熟悉的无人驾驶技术当属美国国防部先进研究项目局无人挑战赛(DARPA Grand Challenge)[2]
  路径规划作为无人车定位和导航技术不可或缺的一个环节,成为越来越多学者研究的课题[3]
•在规定一辆车从城市的A点到B点驾驶任务后,首先利用城市的路网信息进行全局静态路径规划,以路程最短原则确定车辆行驶长期路径。
•在车辆运动过程中,由感知系统传感器对周围环境进行检测识别,当检测到动静障碍物时,局部路径规划器根据感知端反馈障碍的信息进行局部运动规划,如果判断前方障碍物无法满足车辆期望速度或预测会碰撞时,局部规划器会规划一条避障路径,并且在避障之后返回原路径,继续向目标点运动。
  图搜索路径规划是路径规划的一种方式,是将车辆周围的连续环境模型转换为适应于所选路径规划算法的离散图,然后运用一定的搜索算法得到基础路径。一般基于图的搜索算法产生的基础路径会出现不连续有节点现象,最后采用光滑处理方法,如 B 样条等。
  车辆从起始点到目标点的规划也可以看作是在有限的时间内满足汽车运动学动力学约束的问题,找到最优路径即是找到代价最小的路径。采用智能优化方法最为关键的是建立路径评估函数,通过安全性、一致性、能量最小等原则选择最优路径。
  本文就环境建模、路径搜索两个方面阐述多种算法,并对路径规划的未来发展趋势作出展望。

2. 环境建模


  当车载雷达和摄像头反馈出当前的环境信息后,局部路径规划器将环境信息处理成规划算法适应的模型。本文将详述一般环境建模所使用的道路路网的可视图法、网格分解的栅格法、势场的人工势场法及随机路图法的基础知识、应用现状及优缺点。


2.1 确定性策略


    可视图法是将环境中的障碍物尺寸加上本车尺寸进行膨胀,然后障碍物描述为多边形,本车描述为质点,将多边形的顶点、起点、终点连接形成无碰路径网络(见图1)。



图1 无碰路径网络

    可视图法适用于静态环境下简单障碍物几何特征的表达,文献[4]对自由空间进行可视图法建模,在寻路上以当前顶点与目标点连线斜率为基准设计目标导向启发概率,运用遗传算法得到全局最优路径。N Tran 等人[5]为处理多障碍物空间的复杂性问题,首先对空间分块采用可视图法构图,然后确定每块空间的起讫点,使用 Dijkstra’算法得到每块最短路径,综合得到全局最优路径。采用并行构图和并行寻路的方法提高了运算效率。对于动态环境需预测下一时步低速障碍物可能行驶的区间,然后生成无碰路网。
    网格分解法一般将环境描述为一种均匀网格,主要为矩形、三角形等[6]。栅格法用大小相同的矩形网格划分环境空间,使用栅格数组表示环境。在栅格数组中,自由空间由0表示,障碍物空间由1表示。对于一部分是障碍物一部分是自由空间的栅格依据其占有比例划分(见图2)。
 
图 2  栅格法示意图

    栅格法使用简单、普适性高且易于实现。其缺点在于栅格分辨率越高,环境表示越精确,然而其运算量成指数上升。SBehnke[7]使用改进的栅格法,在离机器人比较近的地方栅格精度高,远的地方栅格精度不断下降。在实际的应用中,常将机器人大小作为栅格的大小。Hwang J.R[8]等人为解决机器人一般环境建模需要很多单元描述障碍物、自由单元过多会产生次优路径的问题,将基础网格使用三角形表示,使用边缘塌陷的方法简化对障碍物的描述。针对传统栅格法很难处理非完整性约束的车辆系统问题,K chu等[9]将图中栅格的顶点定义为一个车辆状态包括位置和航向信息。二维栅格地图中,VFH[10](向量直方图)算法是机器人避障可靠方法。二维栅格表征环境,每个栅格包含一个概率值,表示该栅格存在障碍的可信度。概率值越大,说明此处有障碍的概率也比较大,并以此来规划路径。VFH是一种简单的反应式避障算法,缺少对选择避障方向的通行性评价,在空间狭小的地方进行路径规划时易出现抖动现象。

    势场法的主要思想是将周围的环境表达为具有引力和斥力的势场,主要描述为障碍物势场和道路势场,以障碍物为中心对本车具有一定梯度的排斥市场,目标点对本车具有引力作用(见图3)。
 
图 3  势场力示意图

    人工势场法以其简单建模、快速高效的优点已成熟运用于工业机械手臂、机器人及智能车路径规划上,但其不足在于会陷入局部最优、在目标点附近存在障碍时不可达、狭窄通道出现抖动现象等问题。同济大学[11]根据以往智能汽车路径规划中的不足,提出整合侧向规划满足车辆非完整性约束、得到最佳路径以及对不同传感器的普适性,使用人工势场描述车辆周围环境,包括障碍物、道路边界、车道线,建立风险环境,规划层首先满足汽车运动学和动力学约束的状态,对基本状态进行扩展可得到多候选路径,利用启发式搜索最佳路径。文献[12]提出通过在障碍物的斥力函数中增加最小安全距离,同时考虑机器人与目标点的相对距离解决了障碍物附近目标不可达。通过以人工势场为主、栅格法为辅的方式解决了陷入局部极小的情况。

    对于传统势场法不足有以下改进措施:

① 通过修正引力函数解决可能碰到障碍物的问题,避免由于离目标点太远导致引力过大


        改进的引力函数增加了机器人与目标点的阈值范围d_goal^*。

② 引入新的斥力函数解决目标点附近有障碍物导致目标点不可达问题



 改进的斥力函数增加了目标和物体距离的影响,当机器人靠近障碍物时斥力场增大,但相对距离减少一定程度上减弱了斥力作用。
③ 扩展势场法在基础势场上附加转动势场和任务势场,转动势场的作用是当机器人与障碍物同向时减少斥力。任务势场考虑机器人当前速度,排除了根据近期势能对机器人速度无影响的障碍物,使轨迹更加平滑。

2.2 随机性策略


    随机路图法(PRM)核心思想包括得到自由空间的随机采样点是在已知信息的环境内采样分成若干个点,然后舍弃处于障碍物区域与边界中的采样点,加入起始点和目标点,连接各点,最后除去与障碍物相交的线段构成随机路图,采用遍历式搜索算法可以得到最短路径(见图4)。
 
图4  随机路图法示意图

    当采样点太少或者分布不合理时得到路径不是最优的,随着采样点的增加可以达到最优但效率会下降。传统PRM算法在处理狭窄通道时,由于采样点很少能落在通道,导致寻到次优路径甚至不能寻到路径。文献[13]对落在障碍物区域的采样点施加势场力,使之移动到自由空间,增大的落在狭窄通道采样点的可能。Matthew等人[14]设计的基于视觉的随机路图法(VBPRM)应用在机器人手臂运动规划上,目标点和障碍物要求在机器人的视觉范围内,改进的 PRM 增加了目标点边的权重。PRM适用于比较固定的场景,可以解决高维空间和复杂约束的路径规划问题,但具有较大不确定性,得到次优路径。


3. 路径搜索算法


  寻路的方法是在环境构建完成的情况下,选择适合的搜索算法以期达到避障及使用能量最小的目的,可分为图搜索算法、树搜索算法、智能优化算法,本文对算法原理及应用现状展开论述。


3.1 图搜索算法


    遍历式Dijkstra算法从物体所在的初始点开始,访问与它相邻的所有的边,采用的是一种贪心策略,总是试图选择当前看来的权值和最大的边,限制条件是所有的边必须是非负代价值。
    相比于遍历式做法,启发式 A* 算法采用靠近初始点和靠近目标点的做法,以代价函数表达每一步的花费,表达式为:f(n)=g(n)+h(n),其中g(n)表示从当前点到初始点的代价值,h(n)表示当前点到目标点的代价值,f(n)表示总的代价值。代价值可以是曼哈顿距离或者欧氏距离,当 h(n)为0时就变为Dijkstra算法。

    A* 算法常适用于静态全局路径规划,而卡耐基梅隆大学A Stenz[15]基于A*算法设计的D*算法则适应于动态环境的路径规划。卡耐基梅隆大学 K Chu,M Lee[16]等研究了公路环境上和非公路环境下的路径规划问题,采用激光雷达构建局部栅格代价地图,障碍区域被分配为无限代价值,自由空间代价最低,根据车辆当前位置、航向信息,给车辆规划不同长度弧长的离散路径集合[17],根据代价函数寻找最优路径。非公路下的路径规划采用D* 算法。


3.2 树搜索算法


    基于采用点的RRT思想是在当前环境进行随机采样工作,RRT算法分为初始化、生长树和生成路径三个阶段。

    初始化时首先定义起始点和终点,向环境中随机撒点,如果采样点不在障碍物区域,则连接起始点移动一定的距离得到新的节点。生长树阶段时对于无障碍区域的采样点,找离它最近的树上的一点,然后移动一定距离得到新的子节点。规划阶段时目标点已被添加到树上,找到一条从起点到目标点的最短路径(见图5)。
 
图 5  快速随机树示意图

    RRT算法路径规划的优点在于高维空间可行,而且可以得到安全无碰的路径;缺点是由于采样的随机性导致前后规划的路径有可能不一致,得到路径曲率连续性差。马亮等人[18]针对 RRT 的不确定性做出改进,首先规划符合车辆动力学原则的直线,向左、向右、U 型的离线多路径模板,根据当前驾驶员决策选择其中一个模板,在此模板上利用改进 RRT 算法完成避障操作。J Bruce[19]提出将采样点概率分为三部分,分别是趋向目标点采样概率,参考路径点采样概率及随机点的概率,运用启发式搜索使得规划速度比传统快 40%。


3.3 智能优化算法


    基于优化寻路的算法是将寻路看作是集安全、边界和距离最短的约束。传统优化方法包括蚁群算法,遗传算法[20]和细菌觅食法[21](见下页图6)。
 
图 6  智能优化算法框图

    智能水滴法的原理是水流对河床的冲刷在其表面会形成沟壑,往往含泥沙量相对较少的河床其泥沙被带走的更多。湖南大学潘鲁彬[22]利用智能水滴法实现无人驾驶汽车避障功能,并与同类的 PSO、AFSA 等群落算法对比,表现出算法优越性。优化算法易出现过早收敛或者收敛速度慢、陷入局部最优的缺点。为此国防科技大学 Q Chen[23]将机器学习方法SVM用于寻路上,亮点在于「路径细分的做法」得到多条路径,通过曲率约束找到最佳路径,其中寻找最佳超平面是工作的难点。

    仿生学在路径规划中比较经典的是触须法[24],触须法是模拟自然界中的昆虫触(试探),不同的触须分布于车辆坐标系空间中形成扇形区域,为不同的驾驶路径提供选择(见图7)。触须法成功应用于DARPA 的大众汽车,并能完成GPS路径跟踪和避障等任务。
 
图 7  触须法示意图

    此外,韩国汉阳大学汽车电控实验室和机械通信控制实验室开发的 A1[25],将全局路径拟合为三次样条曲线,在此基础上定义曲线坐标系,车辆在此坐标系中有不同的横向位移产生候选路径,最后通过安全、平顺、一致性评价指标选择路径。Morphin算法的思想是按照一定的时间间隔生成有转角等机械结构限制的一组运动轨迹。南京理工诸葛程晨[26]针对单层Morphin算法对距离较近的障碍能进行有效避障,而未考虑远处障碍位置问题,提出多层Morphin规划算法。无人驾驶汽车在动态环境下,面对多障碍物避障时效性低的问题,文献[27]提出使用速度障碍法(VOM),建立碰撞时间的代价函数,在可行速度矢量集中评价出最优的速度矢量。D Dang[28] 在智能汽车路径规划建立以道路、障碍、交通规则(限速)、驾驶意图的行驶风险模型,以速度和转角作为使风险最小的输出变量,得到较为理想的路径。


4. 结束语


  目前图搜索的路径规划需要依赖精确的感知信息,且大部分时间花在构建路网上,随着障碍物的增多导致运算量增加,因此适用于二维空间的全局路径规划。对于三维空间的规划,RRT 算法表现出较好的运算效率,被许多学者用于无人车路径规划,但其规划路径会导致随机性及曲率不连续的缺点。智能优化算法随着智能技术的发展而得以发展,它以车辆运动学为基础,建立代价函数寻最优的控制变量。
  无人车路径规划技术多用于满足车辆及道路约束条件下的避障功能,未来应该考虑实际交通环境下的法规要求以及其他驾驶者的意图,做出更合理的路径规划。


参考文献

[1]MediacentreRoadtrafficinjuries, http://www.who.int/mediacentre/factsheets/fs358/en/
[2]C Urmson, J Anhalt, D Bartz et al. A Robust Approach to High-Speed Navigation for Unrehearsed Desert Terrain[M]. Springer Berlin Heidelberg,2007,23(8):467-508
[3]杜明博. 基于人类驾驶行为的无人驾驶车辆行为决策与运动规划方法研究[D]. 中国科学技术大学.2016
[4]许斯军,曹奇英. 基于可视图的移动机器人路径规划[J]. 计算机应用与软件, 2011,28(3):220-222
[5]N Tran, DT Nguyen, DL Vu, NV Truong, Global path planning for autonomous robots using modified visibility-graph[J]. International Conference on Control, 2014:317-321
[6]SOUISSI O, BENATITALLAH R, DUVIVIER D,et al. Path Planning: A 2013 Survey [C]//IEEE, Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM).New York:IEEE 2013:1-8
[7]S Behnke. Local Multiresolution Path Planning [M]. Springer Berlin Heidelberg, 2004, 3020:332-343
[8]Hwang J.R.&J.S.Kim&S.S.Lim&K.H.Park. A Fast Path Planning by Path Graph Optimization [J].IEEE.2003,(33):121-128
[9]K chu, J Kim, K Jo, M Sumwoo. Real-time path planning of autonomous vehicles for unstructured road navigation[J]. International Journal of Autonomous Technology, 2015,16(4):653-668
[10]I Ulrich, J Borenstein. VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots[J].IEEE International Conference on Robotics & Automation systems, 2002,2:1572-1577
[11]Y Ruan, H Chen, J Li. Longitudinal Planning and Control Method For Autonomous Vehicles Based on A new Potential Field Model[J].SAE. Tongji University.2017
[12]欧阳鑫玉,杨曙光. 基于势场栅格法的移动机器人避障路径规划[J],控制工程, 2014,21(1):134-137
[13]刘洋,章卫国. 基于改进 PRM算法的路径规划研究[J],计算机应用研究, 2012,29(1):104-106
[14]M Baumann, EA Croft, JJ Little. Path planning for improved visibility using a probabilistic road map[J]. IEEE Transactions on Robotics,2010,26(1):195-200
[15]A Stentz. Optimal and Efficient Path Planning for Partially-Known Environments[C]. IEEE International Conference on Robotics and Automation,2002,4:3310-3317
[16]S Kolski. D Ferguson et al. Autonomous Driving in Structured and Unstructured Environments. IEEE, Intelligent Vehicles Symposium,2006:558-563
[17]A J Kelly. An Intelligent, Predictive Control Approach to the High-Speed Cross-Country Autonomous Navigation Problem[M]. ACM,1995,36-44.
[18]Liang Ma. Efficient Sampling-Based Motion Planning for On-Road Autonomous Driving[J]. IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2014,1-16.
[19]J Bruce, MM Veloso. Real-Time Randomized Path Planning for Robot Navigation[J], Springer, Lecture Notes in Computer Science.2002,3:2383-2388
[20]张毅,代恩灿,罗元 .基于改进遗传算法的移动机器人路径规划[J]. 计算机测量与控制,
2016,24(1):313-316
[21]陈东. 智能车辆局部避障路径规划及横向运动控制研究[D]. 湖南大学,2016
[22]潘鲁彬. 无人驾驶汽车路径规划与跟随控制算法研究[D],湖南大学,2016
[23]Q Chen ,Z Sun, D Liu et al. Local Path Planning for an Unmanned Ground Vehicle Based on SVM[J]. ResearchGate, International Journal of Advanced Robotic Systems,2012,9:1
[24]F Von Hundelshausen, M Himmelsbach etal. Driving with Tentacles: Integral Structures for Sensing and Motion[C]. Wiley: Journal of Field Robotics, 2010, 25(9):640-673
[25]K Chu, M Lee , M Sunwoo. Local Path Planning for Off-Road Autonomous Driving With Avoidance of Static Obstacles [J]. IEEE Transactions on intelligent Transportion systems, 2012,13(4):1599-1616
[26]诸葛程晨,塘镇民,石朝侠. 基于多层Morphin 搜索树的 UGV 局部路径规划算法[J]. 机器人,2014,36(4):491-497
[27]J Choi. Kinodynamic Motion Planning for Autonomous Vehicles[J]. International Journal of Advanced Robotic Systems,2014,11:1
[28]D Dang. Motion Planning of Vehicle Obstacle Avoidance in Complex Traffic Scenarios[J]. SAE:Intelligent & Connected Vehicles Symposium,2017













相关阅读
发表评论
姓名:
联系方式:
评论专区
东南大学 东南大学交通学院 清华大学 同济大学 西南交通大学 北京航空航天大学 上海交通大学 浙江大学
University of Wisconsin - Madison University of Michigan Rensselaer Polytechnic Institute Santa Clara University Rutgers University
交通运输部路网监测与应急处置中心 江苏省交通运输厅 南京智库联盟 江苏交通控股有限公司 江苏高速公路联网营运管理有限公司
中心概况研究动态新闻中心合作交流加入我们
Copyright © 2015 东南大学物联网交通应用研究中心 All Rights Reserved.