自动驾驶汽车路径规划算法研究*

李梓欣 李军

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

自动驾驶汽车使用传感器感知环境，并依照合理的算法在复杂环境中实现自主运动，使其能在道路上安全、高效地行驶。作为自动驾驶汽车研究的一个重要环节，路径规划就是根据给定的环境模型，在一定的约束条件下，利用路径规划算法规划出一条连接车辆当前位置和目标位置的无碰撞路径。在此基础上可按照不同需求选择一条最优路径。随着各个领域的不断发展，传统路径规划算法在复杂环境模型下存在规划速度慢、数据计算量大等问题，难以满足路径规划实时性、准确性的要求。现结合相关文献，从A*算法、蚁群算法等目前广泛使用的算法入手，介绍其基本原理与研究进展，并对其未来发展方向做出展望。

1 路径规划算法分类

依照路径规划算法在原理上的不同，可将算法大致分为基于搜索的路径规划算法、基于采样的路径规划算法以及基于智能算法的路径规划算法[1]。其中，基于搜索的路径规划算法主要包括Dijkstra算法、A*算法等；基于采样的路径规划算法主要包括RRT算法[2]、PRM算法[3]等；基于智能算法的路径规划算法主要包括遗传算法[4]、蚁群算法等。这些算法由于其不同的计算原理，其完备性与最优性也不尽相同，按照不同路段与工况需求选择不同算法以获得较好完备性与最优性是学者共同追求的目标。

依照算法在进行路径搜索时是否有启发信息介入，可将路径规划算法分为传统路径规划方法与启发式搜索算法。传统路径规划方法，诸如Dijkstra算法、Floyd算法等，盲目搜索整个环境空间，虽然算法较为简单，但其计算量极大，在复杂环境下难以高效完成路径规划。启发式算法在路径规划时引入启发因子或启发函数，按照一定的评价指标估计节点代价值，从而引导路径朝着预期方向进行规划，以提升效率。故对于启发式算法，评价指标的选取极为重要，将大大影响路径规划的质量。

2 典型的路径规划算法

2.1 A*算法

传统Dijkstra算法从起点开始逐步扩展，每一步为一节点找到最优路径。在寻优过程中利用贪心思想，遍历邻接节点更新距离。由于其未使用启发函数，算法计算量与空间占用都较大。

A*算法是建立在Dijkstra算法上的智能搜索算法，它通过引入与目标点有关的启发信息，引导算法沿着最优方向进行搜索。可通过不同的启发信息估计当前点与目标点间的距离，在设计代价函数时结合所需的启发信息，并优先选择代价值最小的节点。图1示出Dijkstra算法规划出的路径，其中红色路线为已规划的路径，蓝色“x”点为已搜索的路径节点；图2示出A*算法规划出的路径，由图可知A*算法在启发函数的影响下所需搜索的路径节点更少，算法效率更高。

图1 Dijkstra算法

图2 A*算法

A*算法利用启发函数，使得搜索方向更趋于目标点，但A*算法所规划的路径转折点较多，无法保证路径的平滑度；且存在多个最小值时无法保证路径最优。故国内外很多学者提出不同方法优化A*算法，试图改进其不足。

针对传统A*算法未考虑运动学性质且无法进行多步长路径规划，文献[5]利用高斯分布动态改变A*算法代价函数的权重系数，减小算法运算时间，防止其陷入局部最优。

传统A*算法遍历节点数目多，搜索效率低，文献[6]引入双向搜索机制，通过2个方向交替进行路径搜索，加快搜索速度；设置合理的启发函数和代价函数减少对无关节点的搜索，提高算法效率。文献[7]设置关键点代替OPEN表中的节点减小计算量，提高算法效率；利用反向搜索策略判断障碍物位置，降低路径长度。

针对传统A*算法搜索速度慢、路径转折点多且不适用于动态环境，文献[8]依据不同节点构成的轨迹间的夹角删除和新增节点；当环境模型较大时，算法设置局部子区域，进行多重A*算法搜索目标点。

文献[9]在A*算法估价函数中引入惩罚机制，通过不同曲率计算惩罚代价值，减少AGV转向次数；以小车电量、行驶距离、冲突节点作为优先级的判定依据，以路径长度与小车利用率作为多AGV协同规划的复合指标，进行多AGV无碰撞动态路径规划。

针对传统A*算法路径不平滑、可行路径不是最短、动态环境下效率较低等问题，文献[10]提出一种融合动态窗口算法的改进7×7的A*算法。将传统A*算法的搜索邻域由3×3扩大为7×7，同时去除同向多余子节点，优化算法角度，提高算法效率。

2.2 快速扩展随机树（RRT）算法

RRT算法在环境模型中随机生成节点，以最近节点作为基准点，按照一定步长向远离障碍物或边界的节点进行生长，直到到达目标点或与目标点在一定距离内时停止生长，随后算法连接起点与终点的最短路径，此为所需的规划路径。

RRT算法搜索能力较强且易于解决非完整约束寻优问题，在高维环境与复杂环境中应用较广。但RRT算法计算量较大，且生成路径稳定性较差。文献[11]提出改进RRT算法，新生成节点与目标点距离作为评价指标，引入权重系数，设置动态距离增量，防止算法陷入局部最优。

文献[12]加入目标点信息，生长距离由随机采样和势场共同引导，斥力场保证算法避开障碍，路径可直接与目标点相连。

RRT算法虽然具有概率完备性，但其无法保证路径最优。故在此基础上提出RRT*算法以规划出一条渐进最优路径[13]。RRT*算法通过重新选择父节点，并且在一定范围内重新连接节点，通过多次迭代实现渐进最优。如图3所示，RRT*算法规划得到的路径（图中红色路线所示）相比RRT算法所得路径（如图4所示）更短。

图3 RRT*算法

图4 RRT算法

文献[14]在RRT*算法基础上对采样点方向进行约束，同时对目标点方向更大权重，增强算法效率。文献[15]删除碰撞检测计算，设置碰撞风险评估函数实现避障。

为提升找到渐进最优路径的速度，文献[16]提出Informed RRT*算法，该算法将可能的最优解集中在初始解构成的椭球中，以提高算法效率。如图5所示，Informed RRT*算法采样得到的路径（图中绿色线路）相比图4中均集中在蓝色虚线构成的椭圆内，由此可提高算法效率。

图5 Informed RRT*算法

2.3 蚁群算法

蚁群算法（Ant Colony Optimization）由意大利学者Dorigo最早提出，是一种源于大自然的仿生类算法。蚁群算法的基本原理为，蚂蚁在走过的路径释放信息素，该信息素与路径长度有关。蚂蚁优先选择信息素浓度较高的路径，遇到未走过的交叉位置便随机选择路径，最优路径信息素浓度增大，直至蚂蚁找到最优路径。

蚁群算法搜索路径能力较为稳定，易与其他算法进行融合，但它也存在收敛慢、易早熟等问题。现阶段国内外提出多种优化算法。

针对蚁群算法存在的寻路时间长、收敛速度慢等问题，文献[17]将起始点与目标点连接，精英蚂蚁沿此连线搜索路径，利用该路径平滑处理后构建封闭区域，再计算转弯代价与设置的门限值进行比较，从而确定最终路径。

针对传统蚁群算法参数影响过大的问题，文献[18]提出一种结合粒子群算法的改进蚁群算法。改进算法通过动态惯性权重调整粒子群算法参数，并对蚁群信息素更新策略进行调整。文献[19]在边缘栅格与中心区域设定不同浓度信息素，对部分路径信息素重新赋值，保证算法随机性，防止其陷入局部最优。

针对蚁群算法在复杂环境下收敛慢、易出现“早熟”现象等问题，文献[20]将蚁群算法与A*算法结合，并设置信息素矩阵以保证算法向目标点收敛且效率更高。文献[21]引入通过极值限定策略、精英策略和信息素扩散策略，动态调整信息素浓度，以兼顾算法效率和质量。

2.4 算法比较

通常使用以下4个指标评价路径规划算法：

1）完备性。若在起始点与目标点之间有路径存在，则必能得到路径，否则无路径存在。

2）概率完备性。若在起始点与目标点之间有路径存在，只要经过足够时间的规划，必能得到路径。

3）最优性。规划得到的路径在某个评价指标上是最优的。

4）渐进最优性。经有限次规划迭代后得到的路径是接近最优的路径，且每次迭代后都更加接近最优。

各算法比较如表1所示：

表1 路径规划算法比较

对于上述各算法规划速度，基于采样的路径规划算法由于其随机采样的特性，使得规划速度更快，其中RRT*算法相对RRT算法具有渐进最优性，从而其速度更快。基于搜索的路径规划算法需要广泛搜索状态空间，因此算法速度相比RRT算法较慢，其中A*算法由于引入了启发函数使得其无需遍历搜索，比Dijkstra算法效率更高，速度更快。基于智能算法的路径规划算法需要大量迭代，需要更久的时间才能得到所需路径，因此相较其他2种路径规划算法速度更慢。

3 结论

文章将路径规划算法依照其算法原理与启发信息大致分类，并对部分规划算法的原理、特点及国内外改进方法进行简要阐述。对于不同路径规划算法，其原理与特点各不相同，从而使得不同算法在不同环境条件下有多种使用方式。如在复杂立体交通中利用基于采样的路径规划算法，发挥其在高维环境中规划的优势；也可通过优化启发因子，使得A*算法等启发式路径规划算法在复杂道路环境中可获得更加安全、节能的路线。

现有的路径规划算法在静态全局路径规划及已知环境信息的动态路径规划问题中进行了大量的研究，不同的算法在其进行路径规划时都具有一定优势。然而，对于未知环境下的路径规划，关于不确定环境因素与多车协同的路径规划研究较少。因此，通过多种算法融合，在高维、动态、复杂以及多变的环境中进行路径规划的研究，将成为自动驾驶汽车算法研究的主流方向。