无人驾驶汽车局部路径规划研究综述

徐瑞 李军

摘  要：文章针对近年来的无人驾驶汽车路径规划算法进行总结和归纳。首先对目前主流的环境建模方法进行阐述;其次对路径规划算法进行介绍，通过分析其优缺点，指出融合轨迹规划算法具有最好的适用性;最后总结当前研究挑战并提出了相关建议。

关键词：无人驾驶汽车;环境建模;路径规划;搜索算法

中图分类号：U462     文献标识码：A     文章编号：1005-2550（2020）05-0084-06

Abstract： Autonomous vehicle path planning latest algorithms have been investigated in this paper. Firstly， the current mainstream environmental modeling methods are described; Afterwards， corresponding path planning algorithms are introduced， by analyzing their advantages and disadvantages to pointed out that the fusion trajectory planning algorithm has the best applicability. Finally， by summarizing the current research challenges and proposes relevant suggestions.

Key Words： Autonomous Vehicle; Environment Modeling; Path Planning; Search Algorithm

引言

无人驾驶汽车将先进的环境感知、路径决策规划、车辆控制技术融合到传统车辆载体中，旨在提高汽车及道路交通的安全性能。路径规划技术作为无人驾驶汽车最为核心的技术之一，其技术核心在于：根据特定的道路环境模型，定义车辆的起始点和目标点，提供方位引导。然后，通过定量化的性能指标及规则，设计出一条相对安全而又快捷的有效路径。

路径规划主要包含全局路径规划和局部路径规划。全局路径规划需依赖于全局道路高精度地图信息，并基于路径规划算法求解出车辆从当前位置到目标位置的最优可行路径;而局部路径规划属于全局路径规划的实时补偿规划，其基于多传感器获得的外界环境信息及驾驶人的状态，对当前道路中出现的障碍物和特殊情况进行局部重新规划，从而提高轨迹的合理性及安全性。

无人驾驶路径规划的选择引导车辆的行驶方向，对车辆行驶安全起到至关重要作用，其技术原理如图1所示。通过建立包含障碍区域与自由区域的环境地图;然后，根据当前环境信息及相关成本函数，判断出最优的路径搜索算法，从而达到实时精准的对多条可行性路径进行搜索。

1    环境建模

当感知系统传递周围环境信息后，局部路径规划处理器将信息融合为相应的环境地图，环境建模的方法有：栅格法、可视图法、维诺图法、拓扑法等，文中将详述环境建模所常用的栅格法、可视图法的应用现状。

1.1   栅格法

栅格法作为目前最成熟的轨迹规划算法，由W.E.Howden于1968年率先提出[1]，其原理是将外界环境图像信息进行单元分割，并利用等尺寸二值信息的矩形栅格来表征。而栅格的尺寸是影响规划算法鲁棒性的重要指标，栅格越小环境分辨率越高。相对而言，存储空间占用率会增大，路径规划决策效率将会收到干扰;若栅格越大，便会降低在高密度多目标等复杂场景中的路径识别能力。

文献[2]针对传感器测量的不确定性问题，将概率推理思想用于栅格地图的建立，采用不同的算法驗证发现，原始的贝叶斯推理算法和Dempster融合算法在实时更新栅格地图和运动目标检测性能表现更优。文献[3]提出针对全局环境的完全遍历栅格法静态环境建模和针对局部环境的边走边测的栅格法动态环境建模，并利用实时更新的信息对模型进行辨识，以提高模型的准确性。文献[4]首先对栅格地图进行编号，方便快速获取障碍物位置，然后建立栅格关联矩阵对候选栅格进行概率计算，并利用栅格方向向量进行走向引导，有效提高路径识别能力，提升规划效率。

1.2   可视图法

可视图环境建模法，是将外界环境中的障碍物转换为凸多边形物体，将障碍物位置的顶点、本车当前位置、目标点这些节点用直线连接，若两点连接的线段不与任何障碍物多边形相交，则称两点“可视”，该线段称为可视线[5]。基于此原理构建路线图的方法，称为可视图法。但是应对于复杂场景时，运算效率不佳。

基于此，文献[5]基于A*路径搜索算法来构建可视图，并建立可视图节点判断机制，仅需构建与最优路径匹配度较高的可视边，从而提高了算法的运行效率。文献[6]将路径规划中的障碍物进行规则化筛选，排除相关度较低的障碍物，并通过简化可视图的边数，减少候选参考路径的数量，从而提高算法的运算效率和可靠性。针对于复杂场景中的多目标障碍工况，文献[7]提出了一种基于小型障碍物进行分组、重新组合的路径规划方法，对并行处理的运行环境进行划分，如图2所示，大大地缩短算法的计算量，提高运算效率。文献[8]采用可视图法生成多边形规则体，并通过最优控制算法来合并多边形作为中间目标，从而减少规划目标受到局部极小值影响。

2    路径搜索算法

路径搜索作为路径规划的主要步骤，负责在建立好的环境模型中计算最优的轨迹方案。目前研究较为广泛局部路径规划算法主要包括：人工势场法、A*算法、快速搜索随机数法、蚁群算法。

2.1   人工势场法

人工势场法是将无人驾驶车辆的运动简化为在受力场中的运动，如图3所示，由于受斥力的作用，可规避周围的障碍物。此外，在引力的激励下向目的位置移动，从而构成的合力控制的运动方向[9]。该种算法无须对全局进行搜索，且鲁棒性较强，被广泛应用于路径规划中。但是，当斥力大于引力时，方向矢量会无法进行判别，导致无法到达目的地;当斥力和引力相等，即合力为零时，无人驾驶车辆无法继续前进，即陷入局部最小点。

为解决斥力与引力之间的冲突问题，文献[10]引入调节因子来计算无人驾驶汽车与目标位置的相对距离，并建立的斥力势场函数来缓解引力和斥力冲突。此外，针对于车辆被困在局部最小值问题，提出了APF-FC融合算法，有效地解决了传统人工势场法的相关缺陷。文献[11]通过建立障碍物和车辆约束的目标函数，并采用高斯组合隶属函数调节系数修正路径曲率，从而避免汽车陷入局部最小点。文献[12]将人工势场法和最优控制结合，提出一种模型预测路径规划控制器，利用车辆动力学规划最优路径的同时，对不同的障碍物和道路结构进行分布处理。文献[13]采用人工势场法对障碍物和道路边界建立势场函数，对可行区域进行网格划分并分配电阻值，然后根据起点和终点之间各节点的局部最大电流方向，选择无碰撞路径。

2.2   A*算法

A*算法作为一种启发式的搜索算法，主要通过建立节点估价函数来决定搜索方向，估价函数f（i）表达式[14]为：

f（i）=g（i）+h（i）                                （1）

g（i）表示从起始節点到i节点的实际代价，主要决定搜索范围，搜索节点增多，效率越低。h（i）表示从i节点到目标节点的估计代价，当估价代价与实际代价相近时，节点数将会减少，搜索效率便会提高。

A*算法的估价函数决定open list中各节点的次序，将会自动选择代价最小的节点作为下一个扩展节点，用open list记录所有的被考虑的最小代价节点。但是，考虑到在搜索路径时访问节点的更新频率较快，当遇到较复杂场景时，会加大计算量，严重消耗内存，影响搜索效率。针对此问题，文献[15]基于A*算法提出了一种跳点搜索方法，从而减少在环境地图中的扩展节点，提高搜索效率。文献[16]通过优化分割A*算法规划的路径中的步长，将当前位置的各节点相连接，并剔除没有交集的冗余点，从而缩短了路径长度，减小了转折角度。文献[17]以电动车能耗为平台，建立车辆总能耗的实际代价函数和估计代价函数，并综合考虑电动车剩余电量和充电桩位置，寻找可达目的地能耗最小的路径。文献[18]通过计算碰撞前的计算估价函数值来优化A*算法，根据起点和目标点间的直线斜率进行算法切换，缩减了目标位置的距离和算法的运算时间。文献[19]提出了矩形展开算法（REA*），以无障碍矩形为单位探索地图，将矩形的边界用作搜索节点，剔除矩形内不必要的点，相应访问的节点比A*少，优化了运算效率。

2.3   快速搜索随机树算法

快速搜索随机树（Rapidly exploring Random Tree，RRT）算法，是基于增量采样的树结构算法，以起始点为随机树的根节点，向四周环境搜索随机节点，当叶子节点包含了目标点或进入了目标区域，便求解出一条由从起始点到目标点的最优路径[20]。此算法省略了环境建模，搜索范围全、速度快;但在搜索时，均匀分配的随机采样点利用率低，且搜索缺乏导向性，规划路径的耗费时间长且不规则。

文献[21]针对人机交互时连续曲率的路径问题，提出一种基于RRT*算法的代价函数来调整路径曲率的方法，去除路径冗余点，从而获得连续路径，并实时更新路径以防环境突变，避免了重复计算。文献[22]提出了基于驾驶员视觉行为的快速搜索随机树算法（DV-RRT），根据驾驶员视觉的近点和远点，在高斯分布引导采样过程中考虑节点间距离、转角的度量函数及b样条的连续曲率平滑度，通过实车试验，如图4所示，验证了实时性、稳定性和舒适性的要求。文献[23]通过高斯分布函数建立随机采样区域，使其分散在期望路径周围，并采用启发式搜索来增加调节因子，对采样点施加导向，使其向目标点靠近，从而改善了算法的泛化性。文献[24]提出一种基于神经网络的最优的RRT算法（NoD-RRT）来解决具有非线性动力约束的路径规划问题，并根据随机搜索树重构方法，实现了状态空间的近似最优解。

2.4   蚁群算法

蚁群算法（Ant Colony Algorithm，ACA）是根据蚂蚁群体的觅食行为的一种正反馈智能优化算法[25]，将规划问题的可行路径用蚂蚁的行走路径表示，蚂蚁通过感知环境的信息素浓度，会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，整个蚂蚁群会在正反馈的作用下集中到最佳的路径上，此时对应的便是路径规划问题的最优解。蚁群算法在搜索过程采用并行计算方式，但算法的计算能力较差限制了它在求解最短路径问题上的应用。

基于此，文献[26]提出蚂蚁回退策略来避免算法陷入局部最优点，通过改进启发式搜索信息和释放的信息素，来判断两者优先级和节点信息，根据临时规避或重新寻路策略来解决冲突和避碰问题。文献[27]通过设计搜索的区域信息素初始值，引入自适应调节因子，对优质蚂蚁和劣质蚂蚁所经路径的信息素进行判别，同时增加避障因子，改进转移概率，避免盲目搜索，提高算法的全局性和搜索效率。文献[28]通过非均匀分配初始信息素，引入带有方向的选择策略，减少搜索的盲目性，并采用信息素覆盖和更新规则，对蒸发系数进行分割和调整，有效地提高算法的收敛速度和搜索能力。文献[29]通过改进的激励函数和信息素更新策略，调节蚂蚁对目标节点的感知时分泌的信息素浓度，有效引导蚂蚁移动，减少搜索时间。

2.5   多种算法融合

面对复杂的交通状况和无人驾驶汽车多源异构的需求，通过对比各算法的特点，单一的轨迹规划算法难以满足目前的安全和速率需求。因此，各算法之间的融合能有效提高规划能力和运算速率。

文献[30]将模糊决策树算法与人工势场法进行融合，首先通过引入环境矩阵改进势场法，并利用势场法提供的权值，然后应用模糊决策树算法来寻求局部最优值。文献[31]提出了一种基于A*算法和势场法相结合的路径规划方法，利用模糊逻辑控制器对地形进行特征描述，根据A*算法确定的全局路径，并使用势场法作为局部规划器进行反馈修正，从而保证在动态粗糙地形下的鲁棒性和灵活性。文献[32]将模糊图像处理算法、细菌算法、遗传算法和A*算法四种算法进行融合，首先利用模糊图像处理算法对图像边缘进行检测;然后根据细菌算法规则对隶属函数和模糊规则进行优化，最后通过改进的遗传算法和A*算法生成最优路径，该方法具有良好的边缘检测，安全性高。

2.6   算法对比分析

本文采用加权分析法对各种路径规划算法的性能指标（规划效率、简便性、泛化能力、路径效果、搜索能力）进行分析：

其中，E表示算法的综合评价;Le表示算法规划效率等级;Lc表示算法简便性等级;Lg表示算法泛化性等级;Lr表示算法路径效果等级;Ls表示算法搜索能力等级;λ表示各个指标的权重值，均为20%。

如表1所示，依据综合分析评价结果，融合算法综合评分为90分，搜索能力强，规划路径效果好，在针对于复杂场景，拥有较好的算法泛化能力，并有利于提高轨迹规划的鲁棒性。

3    结论

本文重点分析了目前主流的路径规划算法，并具体分析了不同算法之间优劣性，得出结论：融合算法雖较为繁琐，但凭借其良好的鲁棒性及泛化能力，已经成为目前路径规划中的最重要的研究方法。此外，目前的研究仍然面临着严峻的挑战，主要包括易陷入局部最小值、路径的连续曲率问题、收敛速度慢、未考虑系统的振动和噪声影响，及复杂环境中的导航问题等等。

为实现安全、鲁棒的自主车辆路径规划，提出以下几点建议：在未来的研究中，应考虑车辆的动力学和可能影响规划的系统性或非系统性错误;注意系统振动和噪声对可靠性和执行方法产生影响;此外，环境感知的设备，如雷达，传感器和摄像头的局限性也需要加以考虑;最后，为了使无人驾驶车辆能够快速决策，应先考虑各算法的优点和局限性，采用各种算法融合方法，也需考虑算法的计算复杂度，减少执行时间。

参考文献：

[1]Wang C Y， Banitaan S. A Partitioning-Based Approach for Robot Path Planning Problems[C]//2018 18th International Conference on Control， Automation and Systems （ICCAS）. IEEE， 2018： 178-182.

[2]周俊静，段建民. 基于栅格地图的智能车辆运动目标检测[J]. 系统工程与电子技术，2015，37（02）： 436-442.

[3]刘晓磊，蒋林，金祖飞，郭晨. 非结构化环境中基于栅格法环境建模的移动机器人路径规划[J]. 机床与液压，2016，44（17）： 1-7.

[4]程向红，祁艺. 基于栅格法的室内指示路径规划算法[J]. 中国惯性技术学报，2018，26（02）： 236-240.

[5]吕太之，赵春霞，夏平平. 基于同步可视图构造和A*算法的全局路径规划[J].南京理工大学学报： 自然科学版，2017，41（3）： 313-321.

[6]张琦，马家辰，马立勇. 基于简化可视图的环境建模方法[J]. 东北大学学报 （自然科学版），2013， 34（10）： 1383-1386.

[7]Toan T Q， Sorokin A A， Trang V T H. Using modification of visibility-graph in solving the problem of finding shortest path for robot[C]//2017 International Siberian Conference on Control and Communications （SIBCON）. IEEE， 2017： 1-6.

[8]Ma Y， Zheng G， Perruquetti W. Cooperative path planning for mobile robots based on visibility graph[C]// Control Conference. IEEE， 2013： 4915-4920.

[9]安林芳，陈涛，成艾国等. 基于人工势场算法的智能车辆路径规划仿真[J]. 汽车工程，2017， 39（12）： 1451-1456.

[10]Gu X， Han M， Zhang W， et al. Intelligent Vehicle Path Planning Based on Improved Artificial Potential Field Algorithm[C] //2019 International Conference on High Performance Big Data and Intelligent Systems （HPBD&IS）. IEEE， 2019： 104-109.

[11]修彩靖，陈慧. 基于改进人工势场法的无人驾驶车辆局部路径规划的研究[J]. 汽车工程，2013 （9）： 808-811.

[12]Rasekhipour Y， Khajepour A， Chen S K， et al. A potential field-based model predictive path-planning controller for autonomous road vehicles [J]. IEEE Transactions on Intelligent Transportation Systems， 2016， 18（5）： 1255-1267.

[13]Huang Y， Ding H， Zhang Y， et al. A Motion Planning and Tracking Framework for Autonomous Vehicles Based on Artificial Potential Field-Elaborated Resistance Network （APFE-RN） Approach [J]. IEEE Transactions on Industrial Electronics， 2019.

[14]谭雁英，李洋，周军等. 复杂环境下基于A*算法的无人机路径再规划[J]. 系统工程与电子技术， 2017，39（6）： 1268-1273.

[15]赵晓，王铮，黄程侃，等. 基于改进A*算法的移动机器人路径规划[J].机器人，2018，40（06）： 903-910.

[16]孙炜，吕云峰，唐宏伟等. 基于一种改进A*算法的移动机器人路径规划[J]. 湖南大学学报： 自然科学版，2017，44（4）： 94-101.

[17]顾青，豆风铅，马飞. 基于改进 A* 算法的电动车能耗最优路径规划[J]. 农业机械学报，2015， 46（12）： 316-322.

[18]Guruji A K， Agarwal H， Parsediya D K. Time-efficient A* algorithm for robot path planning [J]. Procedia Technology， 2016， 23： 144-149.

[19]Zhang A， Li C， Bi W. Rectangle expansion A? pathfinding for grid maps[J]. Chinese Journal of Aeronautics， 2016， 29（5）： 1385-1396.

[20]杜明博，梅涛，陈佳佳，赵盼，梁华为，黄如林，陶翔. 复杂环境下基于RRT的智能车辆运动规划算法[J]. 机器人，2015，37（04）：443-450.

[21]Lan X， Di Cairano S. Continuous curvature path planning for semi-autonomous vehicle maneuvers using RRT[C]//2015 European Control Conference （ECC）. IEEE， 2015： 2360-2365.

[22]Du M， Mei T， Liang H， et al. Drivers visual behavior-guided RRT motion planner for autonomous on-road driving[J]. Sensors， 2016， 16（1）： 102.

[23]宋曉琳，周南，黄正瑜，曹昊天. 改进RRT在汽车避障局部路径规划中的应用[J]. 湖南大学学报（自然科学版），2017，44（04）：30-37.

[24]Li Y， Cui R， Li Z， et al. Neural network approximation based near-optimal motion planning with kinodynamic constraints using RRT[J]. IEEE Transactions on Industrial Electronics， 2018， 65（11）： 8718-8729.

[25]许凯波，鲁海燕，黄洋等.基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报， 2019，47（10）： 2166-2176.

[26]郭保青，郝树运，朱力强等. 基于改进蚁群算法的多AGV泊车路径规划[J]. 交通运输系统工程与信息，2018，18（06）：55-62.

[27]江明，王飞，葛愿等.基于改进蚁群算法的移动机器人路径规划研究[J].仪器仪表学报，2019（2）： 13.

[28]Zhao J， Cheng D， Hao C. An improved ant colony algorithm for solving the path planning problem of the omnidirectional mobile vehicle [J]. Mathematical Problems in Engineering， 2016： 452.

[29]Wang Y， Lu X， Zuo Z. Autonomous vehicles path planning with enhanced ant colony optimization[C]//2019 Chinese Control Conference （CCC）. IEEE， 2019： 6633-6638.

[30]Iswanto I， Wahyunggoro O， Cahyadi A I. Path planning based on fuzzy decision trees and potential field [J]. International Journal of Electrical and Computer Engineering， 2016， 6（1）： 212.

[31]Raja R， Dutta A. Path planning in dynamic environment for a rover using A? and potential field method[C]//2017 18th International Conference on Advanced Robotics （ICAR）. IEEE， 2017： 578-582.

[32]Al-Jarrah R， Al-Jarrah M， Roth H. A novel edge detection algorithm for mobile robot path planning [J]. Journal of Robotics， 2018.