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

袁师召 李军

（重庆交通大学机电与车辆工程学院）

如今人工智能技术得到了不断发展和应用，其中无人驾驶作为汽车逐渐智能化的一个方面备受关注。无人驾驶技术不仅可以减少由于驾驶员疲劳或操作不当等造成的交通事故以及拥堵现象的发生，而且可以提高能源的利用率，是未来汽车重要的技术发展趋势之一。路径规划作为无人驾驶汽车运行的关键环节，具有重大的研究意义。文章从全局和局部路径规划2 个方面综述当前无人驾驶汽车路径规划中的各种算法，分别从算法的搜索收敛能力、算法的实时性以及算法的复杂程度等方面进行阐述，并分析比较各算法的优缺点，为今后的深入研究提供参考。

1 无人驾驶汽车的路径规划

作为无人驾驶汽车顺利运行的重要环节，路径规划是指无人驾驶汽车在具有障碍物的环境中，能够规划出一条从起始位置状态到目标位置状态无碰撞的最优路径或次优路径，并满足所有约束条件，是实现汽车智能化的关键技术之一。根据路径规划的目标范围，可以将其分为全局路径规划和局部路径规划2 种[1]。全局路径规划主要是对局部路径规划起到导向和约束作用，使车辆沿着导航系统提供的一系列期望局部目标点行驶。全局路径规划不算复杂，前提是有拓扑级地图，而局部路径规划是在车辆沿期望路径行驶时，通过车载传感器感知周围环境及交通信息，从而实现车道保持、动态避障等功能，又可以称作避障规划。局部规划要求算法具有较高的实时性，以应对实时变化的环境信息，这对传感器、算法的效率和处理器的运算能力都是极大的挑战，避障规划不仅考虑空间还考虑时间序列。目前，对于已知环境的路径规划，已存在很多成熟算法，可实现车辆无碰撞地到达目标地点，但在未知环境下，如何根据无人驾驶汽车的传感器实时探测到的局部环境信息进行路径规划，仍处于试验研究阶段。

1.1 全局路径规划

全局路径规划是在已知的环境信息下，在事先已建好的环境模型中，去获得一条从初始地到目标地中符合一定性能的可行或最优的路径，其优点是保证了规划路径的最优性和可达性[2]。

全局路径规划在搜寻最优路径的算法上，根据搜索算法可分为图搜索类算法、随机采样类算法、智能算法等。图搜索类算法[3]主要包括Dijkstra 算法[4]、A*算法[5-6]、D*算法等。与Dijkstra 算法相比，A*算法增加了启发式估计，并减少了搜索量，提高了效率，同时保证了路径的最优性，但在环境复杂、规模较大时，效率仍较低。文献[7]采用仿真和试验相结合的方法，对AGV 路径规划的A*算法和D*Lite 算法进行了比较研究，比较的重点是生成轨迹的计算时间和生成轨迹的距离。结果表明，D*Lite 能够以比A*更快的计算速度规划出更短的路径。然而，在某些情况下，D*Lite 不如A*有效。这就表明选择哪种算法合适应该根据系统的需求。针对A*算法的不足，文献[8]将跳点搜索算法与原有的A*算法相结合，提出在生成最终路径的过程中，通过筛选跳点进行扩展，并且在扩展过程中，将A*算法中可能被添加到OpenList 和ClosedList 中的大量不必要的节点用跳点来替代以改进A*算法，减少了计算量。文献 [9]提出了一种优化路径的方法，即拓展Moore 型元胞邻居结构，使得路径较原D*算法进一步优化。对于D*算法的改进，主要发生在路径长度和运算时间上。就D*算法的路径长度问题，提出了拓展Moore 型元胞结构，将原D*算法的路径进一步缩短；与此同时，采用跳点搜索算法对原D*算法的运算速度进行一定幅度的提高。跳点搜索算法可以大量地节约内存，有效地提高运算效率，具有更快的速度、更高的空间复杂度。随机采样类算法主要包括概率路标算法、快速随机树算法，在复杂环境中得到了大量应用，如存在动态障碍物、高维状态空间和存在运动学、动力学等约束条件下的环境中，但这类算法存在耗费代价较大、实时性较差、可能规划得到非最优路径的问题[10]。智能仿生算法是一种模拟生物进化和仿生自然界动物昆虫觅食筑巢等行为的智能化算法，主要有遗传算法[11-12]、蚁群算法[13]、粒子群算法[14-15]等。遗传算法、蚁群算法适用于复杂问题的求解和优化，具有潜在的并行性的特点，但存在运算速度慢、解早熟的现象；与遗传算法和蚁群算法相比较而言，粒子群算法的优点主要在于收敛速度快。文献[16]提出了一种改进蚁群算法，应用在移动机器人路径规划中，对复杂环境下的机器人建立栅格模型，将指向上一节点的数组引入传统转移规则中，使算法逃逸能力得到了增强；在信息素更新中去掉最差蚂蚁释放的信息量，以利于种群的进化，使得在复杂环境中的路径搜索能力优于传统算法。文献[17]提出的优化的蚁群算法改进了信息素的更新方式和状态转移概率、设置了信息素浓度的阀值，并引入了死锁处理策略，避免求解过程中的早熟现象，增加解的多样性，从而使蚂蚁搜索最优路径的范围缩小，能够降低搜索过程中的迭代次数以加快运算速度、提高搜索效率，从而使全局最优路径可以高效、快速地获得。文献[18]提出的基于滚动窗口优化的智能汽车轨迹规划方法，能够同时满足行驶安全和全局最优的要求，把路径曲线描述为6 次多项式，并将路径规划问题转化为求解a6k的过程。该方法引入滚动窗口优化策略，用以解决智能汽车在多约束条件下、未知环境中生成全局最优轨迹的问题。

1.2 局部路径规划

局部路径规划是指无人驾驶汽车根据自身传感器获取到的周围环境信息，能够在未知或部分未知的周围环境中，自主规划出一条无碰撞的最优路径。用于局部路径规划的传统算法有人工势场法[19]、模拟退火法[20]、模糊逻辑法[21-22]、神经网络法[23]、动态窗口法、强化学习法[24]及基于行为的路径规划方法。人工势场法的优点是结构简单、计算量较小，但存在容易产生局部最小值的问题。文献[25]建立了改进的无人驾驶汽车人工势场模型，该改进模型通过利用高斯组合隶属函数在建立引力的目标点函数中，将障碍物约束和车辆约束考虑进去，并引入调节因子，解决了传统人工势场法容易陷入局部极小、目标不可达的问题。文献[26]把传统斥力势场中的实际距离利用椭圆化距离代替，并在传统人工势场法中引入道路边界斥力场模型，综合考虑了车道引力势能场、障碍物斥力势能场和道路边界势能场三者对汽车的影响，从而能够在较小车道空间内获得合适的汽车避撞局部路径。文献[27]结合车辆的实际运行情况，通过一种用正弦避障换道的方式，以最小安全距离作为对称距离的障碍点模型构建方法，使局部目标点处于对称轴线上，解决目标不可达和局部最小值的局部路径规划问题。智能水滴算法模拟水流与泥沙相互作用而形成水道的机制，是一种新型的群落智能算法，在计算科学领域中，当求解的问题比较复杂时，可以应用该算法进行求解。但是对于路径规划问题，智能水滴算法在求解时，存在启发性不足的缺陷，会导致所规划的路径不理想。文献[28]针对原智能水滴算法的以上缺陷，通过变量更换、改进概率选择策略和更新机制，使得该改进算法的求解能力较原算法明显提高。模糊逻辑法是根据模糊的环境信息，依照对应表格规划出的信息，实现局部路径规划，优点在于容易计算，能够实时跟踪规划。文献[29]提出一种基于模糊控制的移动机器人避障方法，但模糊规则根据经验设定，存在经验不完备等问题，因此该算法灵活性差、存在未知短板。可见，无论哪一种算法均存在各自的不足，因此，为了解决和弥补单一算法存在的问题和不足，可采用2 种算法相结合的方法。文献[30]在研究移动机器人路径规划问题中，采用了双层路径规划思想，将改进遗传算法和改进人工势场法相结合，首先采用改进的遗传算法进行全局路径规划，解决最优个体丢失的问题；然后利用改进的人工势场法，对已规划好的全局路径进行局部动态避障，解决了局部极小点问题。文献[31]在蚁群算法搜索过程中加入人工势场局部搜索寻优算法，用局部扩散信息素代替人工势场法中的力因素，使蚁群在搜索过程中更倾向于朝着具有高适应值的子空间搜索，提高了蚁群的预避障能力。文献[32]将修正APF 算法与模糊逻辑算法相结合，既解决了人工势场法规划中存在的局部极小值问题，又提高了算法在复杂环境中的有效性，并使用粒子群优化算法对模糊逻辑算法的隶属度函数进行了优化，使得在静态和动态的环境中能够快速作出响应并规划出合适的路径。

2 结论

文章从无人驾驶汽车全局路径规划和局部路径规划两方面对目前文献中常见的规划算法进行了概括和分析。对传统经典算法，如人工势场法及其改进算法和智能算法，做出了分析，初步得出不管是哪一种算法都有其自身局限性和缺点，如人工势场法尽管具有算法简单、实时性好、规划的路径轨迹圆滑的优点，但是存在容易进入局部最小点、目标不可达的问题和不足；遗传算法、蚁群算法的不足在于存在容易陷入局部最优的问题；神经网络算法的不足则是需要大量样本。面对复杂多变的路径规划问题，采用单一的规划方法往往已不能取得很好的效果，因此趋向于将多种研究方法相结合，如将局部路径规划与全局路径规划相结合，如将在局部环境已知条件下可实现的局部路径规划通过滚动窗口优化原理进行前后衔接，可实现全局路径规划；传统规划方法与新的智能方法相结合。如将蚁群算法与强化学习算法相结合，全局或局部路径规划与动态环境路径规划相结合等，可得到更加完美的、用于无人驾驶汽车的路径规划算法，这些是今后研究的重点与难点。