孔垂燊自动驾驶车辆避障路径规划研究综述-CST自动驾驶
孔垂燊焉知焉知·焉能不知
避障作为自动驾驶车辆在行驶过程中非常重要的部分，对发展自动驾驶车辆具有重要意义。文章介绍了车辆避障技术，概括了自动驾驶车辆避障所采用的传统算法和智能算法，分析了各种算法的优缺点以及改进方法。
本文来自 2018 年 5 月 25 日出版的《汽车工程师》，作者是重庆交通大学周伟和李军。
随着人工智能技术的兴起，以自动驾驶车辆为研究对象的运动路径规划问题越来越受到重视。而避障路径规划是自动驾驶车辆的关键部分，对自动驾驶车辆的研究具有重大意义。在自动驾驶汽车行驶过程中，准确地避开障碍物是智能车辆的基本要求。一个好的避障路径规划算法可以安全实时地避开障碍物，且具有较高的乘坐舒适性，从而提高出行效率。
文章总结了目前文献中经常出现的各种适用于自动驾驶车辆路径规划的算法，分别从算法路径寻优能力、算法实时性及算法复杂度等方面分析比较了它们在理论上的优势和缺点，为今后的深入研究提供参考。
1. 避障技术分析
自动汽车避障技术主要是利用先进的传感器技术来增强汽车对行驶环境的感知能力，将感知系统获取的车速、位置等实时信息反馈给系统，同时根据路况与车流的综合信息判断和分析潜在的安全隐患，并在紧急情况下自动采取报警提示、制动或转向等措施协助和控制汽车主动避开障碍，保证车辆安全、高效和稳定地行驶 [1]。采用人工势场法的智能车辆避障原理，如图 1 所示。
图 1 智能车辆避障原理图
文献 [2] 将避障问题看成有约束的多目标优化问题，而避障问题的处理前提就在于如何根据当前障碍物信息以及自身状态信息决策出该采取何种基本驾驶子操作（分为左换道、右换道、跟随巡航及制动）。
2. 局部危险避障算法研究
2.1 智能车局部危险避障概述
自动驾驶车辆作为一种具有自主决策能力的智能机器人，需要从外部环境获取信息并根据信息做出决策，从而进行全局路径规划和局部危险状况下的避障。
自动驾驶车辆的全局路径规划为车辆规划出了一条在已知环境地图信息下的最优路径。车辆在前进过程中，处在不可预测和高度动态的城市道路环境中，障碍物很可能出现在已经规划好的全局路径上，也有可能在前进的过程中一些障碍（行人或车辆等）动态地出现在路径上。自动驾驶车辆必须对这些不可预测的事件以某种方式做出反应，进行局部避障，使之仍然能够顺利到达目的地、完成任务。
因此，局部避障必须速度快、实时性好和效率高，而可靠的避障算法正是保证自动驾驶车辆成功避障的主要方法。因此，在全局路径规划的基础上，还需要进行实时的局部危险避障。
目前，对于自动驾驶车辆动态目标及城市道路区域的相关避障方法的研究，正是智能驾驶车辆研究的热点和重要方向，也是一项实现车辆智能化的关键技术。
2.2 传统避障算法
目前局部避障算法也有很多成熟的算法，每个算法的优缺点也不一样。目前所采用的方法主要有人工势场法（Artificial Potential Field，APF）和虚拟力场法（Virtual Force Field，VFF）等。
人工势场法是一种虚拟力法，它的基本思想是把车辆在周围环境中的运动视为车辆在人工建立的虚拟力场中的运动。目标点产生引力，引导车辆向目标点运动。障碍物产生斥力，避免车辆与障碍物发生碰撞，车辆在二者的合力下运动。根据引力和斥力的合力来控制车辆的运动，即车辆搜索沿着势场下降的方向运动，产生一条无碰撞的最优路径。
应用人工势场法规划出来的路径一般比较平滑且安全，算法简明，实时性良好，适合无人驾驶智能车领域。但是该算法也存在一些缺点，如当目标点附近有障碍物时，斥力远远大于引力，车辆将很难到达目的地；当智能车辆在某一点的引力和斥力刚好大小相等时，智能车将会陷入局部最优点；传统的人工势场只考虑了障碍物与目标点静止不动的静态环境，而车辆实际是在运动的环境中，因此在动态环境无法取得良好的效果。
针对传统人工势场的改进，大量学者展开研究，文献 [3] 利用高斯组合隶属函数建立引力的目标点函数，在引力点函数中考虑障碍物约束和车辆约束，并引入调节因子，建立了改进的无人驾驶汽车人工势场模型，消除了传统人工势场法容易陷入局部极小的问题。
文献 [4] 通过调整势力场范围、改进斥力势函数和动态调整斥力场系数，解决了陷入局部极小值的情况。文献 [5] 在人工势场中加入速度元素，能够规划出同时避开静态和动态障碍物且能到达目标点的理想路径。文献 [6] 解决了传统 APF 算法在无人车避障应用中虚拟势场作用域固定、避障角度过大的问题。
虚拟力场法是栅格法和人工势场法结合的一种移动机器人实时避障算法。VFF 算法是使用栅格来表示环境，同时使用力场法对无人车进行控制的局部避障算法。
2.3 智能优化算法
智能优化算法一般都是建立在生物智能或物理现象基础上的随机搜索算法，包括模糊逻辑算法（Fuzzy Logic Algorithm，FLA）、遗传算法（Genetic Algorithms，GA）、快速扩展随机树（Rapidly Random- exploring Trees，RRT）、蚁群算法 [7]、水滴算法 [8]、触须算法 [9] 及粒子群算法 [10]（Particle Swarm Optimization，PSO）等。
模糊逻辑算法主要是根据人类驾驶经验，设计出一个模糊控制规则库。将传感器获得的信息作为输入，经过模糊推理后得出车辆所需要的输出，一般输出为速度和导航角。因为智能车辆的运动学模型具有非线性和强耦合性的特点，而模糊控制避障算法不依赖受控对象的精确运动模型，因此采用模糊控制避障算法也是研究中经常采用的方法之一。但模糊规则往往是人们通过经验预先制定的，所以存在无法学习和灵活性差的缺点，且模糊规则数量随着输入的增多呈指数倍增长。
文献 [11] 针对移动机器人设计了一个模糊控制器，将通过安装在机器人前方 180° 范围内的超声波和红外传感器采集的障碍物距离信息以及电子罗盘获取的目标方位角作为模糊控制器的输入，机器人左右轮的速度作为输出。在隶属度函数的选择上，采用高斯型隶属度函数，因为高斯型隶属度函数曲线较为平滑，具有较好的准确性和简洁性。
图 2 模糊控制系统分层结构图
文献 [12] 采用分层分级的思想，将避障过程分为车辆绕开障碍物过程和车辆趋向目标过程的新方法，分别设计了一个避障行为控制器和目标趋向控制器，减少了算法的计算量和提高了运算速度。模糊控制系统分层结构图，如图 2 所示。
遗传算法 [13] 是模拟了生物界的进化论原理（适者生存，优胜劣汰）演化和遗传变异达到物种进化的一种智能算法。遗传算法把路径点作为一个种群，并按照一定的规则对每一个路径点进行编码，然后根据适应度函数选择路径点，借助遗传算子进行组合交叉和变异，逐渐演化产生出越来越优化的近似解。遗传算法具有并行计算能力、群体搜索特性与可扩展性，一般不需要辅助信息，但是效率比其他智能优化算法低，而且在利用选择交叉算子时，会丢失一些优秀的基因片段，从而导致过早收敛。此外，在编码环境中会有较长的计算时间与很大的数据存储空间需求。
文献 [14] 对传统遗传算法提出了一系列的改进措施，包括可见空间的概念、新的矩阵编码形式和新的变异算子。通过使用新的变异算子可使快速收敛到全局最优，且在静态环境和动态环境中都可以快速收敛。
快速扩展随机树（RRT）算法 [15] 是以状态空间中的一个初始点作为根节点，通过随机采样扩展，逐渐增加叶节点，生成一个随机扩展树，当随机树的叶节点中包含了目标点或者目标区域中的点时，从初始点到目标点之间的一条以随机树的叶节点组成的线段就是规划出的一条路径。由于算法在进行路径规划时是随机采样，不需要对状态空间进行预处理，因此有着很快的搜索速度，而且还考虑了车辆在运动过程的动力学约束和运动学约束，该算法也非常适用于智能车辆的运动规划问题。但 RRT 算法存在一些不足：
度量函数（最近邻算法）的合理选取决定算法的合理性和效率；
算法的随机性使得规划出的路径曲率变化过大，甚至出现小范围的直角变化，导致路径不平滑，不符合车辆运动学；
采样点在整个可行域内随机采样的搜索方式存
在很多不必要的运算，影响算法速度，降低搜索效率。针对传统 RRT 算法的改进，一些学者也提出了不同的方法。文献 [16] 根据驾驶经验丰富的驾驶员，设计直道和弯道模型的期望避障路径模型，最后为了使随机采样点分布在期望路径模型周围，利用高斯分布函数生成的点集中在均值周围的特点，再结合设计好的期望路径函数，则实现满足汽车安全稳定行驶的路径。
文献 [17] 利用 A* 算法进行路径规划，根据规划结果生成引导域来修改 RRT 随机采样过程中的采样策略，将目标偏向采样策略和引导域偏向采样策略相结合，使得随机采样点朝着目标点区域方向靠近，并在最近邻搜索过程中加入角度约束，因为智能车辆在行驶过程中有最大转向角限制。
文献 [18] 提出动态步长并引入目标引力思想，在传统 RRT 算法基础上，添加动态步长特性，减少 RRT 的随机性，让路径朝着目标方向扩展，改善了 RRT 的不确定性，提高了避障能力。
文献 [19] 提出一种连续曲率 RRT 算法，该算法在 RRT 框架中结合了环境约束以及车辆自身的约束。它首先采用了目标偏向采样策略以及合理的度量函数，保证了算法随机性的同时也加快了向目标点收敛的速度，大大地提高了规划速度和质量。最后针对智能车辆的实际应用提出基于最大曲率的约束的剪枝函数对树进行后处理，删除不必要的节点并插入必要的节点，接着使用 3 次 B 样条曲线对剩余的节点进行平滑处理以生成平滑且曲率连续的可执行轨迹。
文献 [20] 采用简单有效的 3 次 B 样条曲线平滑算法，对路径点进行曲率连续的拟合以生成平滑且曲率连续的智能车可执行的平滑路径。
此外，还有 RRT GoalBias，RRT Goal Zoom，RRT*，RRT-Connect 等改进方法。
2.4 多种算法结合
在车辆的实际避障过程中，往往会采用 2 种或多种算法相结合，通过互补来提高算法效率。
图 3 避障模糊控制器结构图
文献 [21] 利用模糊逻辑和遗传算法构建一种智能车辆避障路径规划算法。以智能车辆与目标点及障碍物中心点的角度差、智能车辆与障碍物的距离为输入量，智能车辆的速度、转角为输出量，分别建立避障行为模糊规则表和趋向目标模糊规则表，设计模糊控制器，如图 3 所示。最后利用遗传算法对避障行为模糊规则表进行优化，从而实现避障。
文献 [22] 将 RRT 算法与基于滚动窗口的路径规划相结合。采用反复的局部路径规划代替一次性的全局路径规划，保证了算法的实时性。同时以概率来实现随机采样取点，并引入启发式估价函数，使随机树易于朝着目标点方向生长。
文献 [23] 为了避免经典人工势场法（APF）的局部最小值问题，提出一种基于修正 APF 算法与模糊逻辑相结合的新方法。该算法克服了局部极小值问题，提高了算法在复杂环境中的有效性。并使用粒子群优化（PSO）算法优化模糊逻辑算法的隶属度函数。在静态和动态的环境中响应速度快，并能有效避开障碍物。
文献 [24] 在移动机器人上结合蚁群算法和人工势场法的优缺点进行路径规划。提出一种以栅格地图为环境模型，在蚁群算法搜索过程中加入针对具体问题的人工势场局部搜索寻优算法，将人工势场法中力因素转换为局部扩散信息素，使蚁群倾向于具有高适应值的子空间搜索，减少了蚁群算法在盲目搜索路径过程中产生的局部交叉路径及蚂蚁「迷失」数量，提高了蚁群对障碍物的预避障能力。随着自动驾驶技术的发展，车辆避障路径规划算法与其他方法结合，从而更快地优化其规划过程，将能更准确和迅速地进行避障。
3. 结语
文章主要分析了在局部危险避障环境中的优化算法，对传统算法和智能算法及其改进算法的优缺点做出了分析以及多种算法的联合求解。传统算法和智能算法都可在一定程度上解决自动驾驶车辆避障的问题，每种算法都有其优点和局限性。
人工势场法算法简明，实时性良好，规划的路径轨迹圆滑，适合自动驾驶智能车领域，但存在容易进入局部最小点、目标不可达及碰撞障碍物问题。
智能算法在传统算法的基础上，引入了更加智能化的计算，如遗传算法可以同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身容易实现并行化。
因此在实际情况下，要进行精确、安全和快速的避障仅仅依靠单一算法是有限的。车辆进行局部避障时，可以依靠 2 种或多种算法进行求解，得出避障路径，将多种算法的优缺点相互融合，产生更加完美的算法将是未来该领域研究的重点与难点。
参考文献
[1] 宋晓琳，冯广刚，杨济匡. 汽车主动避撞系统的发展现状及趋势[J]. 汽车工程，2008，30（4）：285-290
[2] 贾瑞. 基于滚动优化的自主驾驶车辆避障控制[D]. 吉林：吉林大学，2014：1-7
[3] 修彩靖，陈慧. 基于改进人工势场法的无人驾驶车辆局部路径规划的研究[J]. 汽车工程，2013，35（9）：808-811
[4] 王凯，宋星秀，张一闻. 利用改进人工势场法的智能车避障路径规划[J]. 辽宁工程技术大学学报（自然科学版），2014，33（9）：1236-1239
[5] 杜?，郭达，张新锋. 智能车避障路径规划方法研究[J]. 交通节能与环保，2016，12（3）：17-22
[6] 谭宝成，崔佳超. 改进人工势场法在无人车避障中的应用[J]. 西安工业大学学报，2014，34（12）：1007-1011
[7] 刘建华，杨建国，刘华平，等. 基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报，2015，46（9）：18-27
[8] 宋晓琳，潘鲁彬，曹昊天. 基于改进智能水滴算法的汽车避障局部路径规划[J]. 汽车工程，2016，38（2）：185-191
[9] 张明环，张科. 智能车避障触须算法中的障碍物探测研究[J]. 西北工业大学学报，2012，30（5）：763-767
[10] 李擎，徐银梅，张德政，等. 基于粒子群算法的移动机器人全局路径规划策略[J]. 北京科技大学学报，2010，32（3）：397-402
[11] 杨小菊，张伟，高宏伟，等. 基于模糊控制的移动机器人避障研究[J]. 传感器与微系统，2017，36（3）：51-54
[12] 张艳溶，马戎，张俊楠. 基于分层模糊控制的自主车辆避障仿真[J]. 测控技术，2012，31（9）：67-70
[13] 雷艳敏，王帅. 基于遗传算法的机器人路径规划的仿真研究[J]. 长春大学学报，2017，27（2）：1-3
[14] ZHANG X L, ZHAO Y, DENG N M, et al. Dynamic Path Planning Algorithm for a Mobile Robot Based on Visible Space and an Improved Genetic Algorithm[J]. International Journal of Advanced Robotic Systems, 2016, 13(3): 1
[15] 余卓平，李奕姗，熊璐. 无人车运动规划算法综述[J]. 同济大学学报（自然科学版），2017，45（8）：1150-1159
[16] 宋晓琳，周南，黄正瑜，等. 改进 RRT 在汽车避障局部路径规划中的应用[J]. 湖南大学学报（自然科学版），2017，44（4）：30-37
[17] 冯来春，梁华为，杜明博，等. 基于 A* 引导域的 RRT 智能车辆路径规划算法[J]. 计算机系统应用，2017，26（8）：127-133
[18] 王道威，朱明富，刘慧. 动态步长的 RRT 路径规划算法[J]. 计算机技术与发展，2016，26（3）：105-107
[19] 杜明博，梅涛，陈佳佳，等. 复杂环境下基于 RRT 的智能车辆运动规划算法[J]. 机器人，2015，37（4）：443-450
[20] ELBANHAWI M, SIMIC M. Randomised kinodynamic motion planning for an autonomous vehicle in semi -structured agricultural areas [J]. Biosystems Engineering, 2014, 126(39): 30-44
[21] 胡永仕，张阳. 基于遗传模糊算法的智能车辆避障路径规划研究[J]. 福州大学学报（自然科学版），2015，42（2）：219-224
[22] 康亮，赵春霞，郭剑辉. 基于模糊滚动 RRT 算法的移动机器人路径规划[J]. 南京理工大学学报（自然科学版），2010，34（5）：642-648
[23] ABDALLA T Y, ABED A A, AHMED A A, et al. Mobile robot navigation using PSO-optimized fuzzy artificial potential field with fuzzy control[J]. Journal of Intelligent & Fuzzy Systems, 2017, 32(6): 3893-3908
[24] 刘建华，杨建国，刘华平，等. 基于势场蚁群算法的移动机器人全局路径规划方法[J]. 农业机械学报，2015，46（9）：18-27
文章来源：智车科技
长按识别二维码
iKE焉知·车联网·ADAS·自动驾驶·AI