自动驾驶汽车路径规划技术*

张栩源 李军

（重庆交通大学机电与车辆工程学院；重庆市轨道交通车辆系统集成与控制重庆市重点实验室）

自动驾驶汽车为了完成自主导航的功能，通常要经历环境感知、路径规划和运动控制3 个过程。其中，路径规划是无人车导航和定位技术中一个非常重要的环节，因此它也成为越来越多的研究者非常热衷的课题[1]。随着汽车市场的竞争加剧以及自动驾驶技术的优点凸显，自动驾驶成为智能交通系统的重要组成部分。它不仅排除了人为不确定因素的影响，而且在驾驶安全性、旅行时间、交通拥塞问题、能源利用率等方面也获得了较大的提升和改进。文章从理论和算法实时性等方面详细介绍了各种算法的优势和缺点，并针对各类算法在最新研究的路径规划问题中存在的问题提出了一些改进建议，为今后更进一步地深入研究提供了参考。

1 路径规划分类

自动驾驶汽车的路径规划问题，基于研究对象对所行驶环境信息掌握程度的不同，可分为2 类。第1 类是已知行驶环境信息的全局路径规划，属于静态规划[2-3]；第2 类是利用车载传感器实时获取环境信息的局部路径规划，属于动态规划[4-5]。

全局路径规划问题实质上是在已掌握的所有环境信息的前提下，规划出从起点到目标点的路径生成问题。通常是基于数字地图，根据周围环境的路网模型来选择路径。当因环境或者其他因素导致规划的路径无法继续通行时，则需要重新启动全局规划，以得到更新后的可行路径。局部路径规划需要车载传感器实时采集车辆周围的环境信息，充分了解周围环境地图信息以准确定位出车辆当前位置及周围障碍物分布，从而顺利规划出从当前节点到下一子目标节点的最优路径。在无人驾驶系统中，局部路径规划在跟踪全局路径的同时能够顺利完成避障，大大提高规划系统在动态未知环境下的路径规划能力。局部路径规划在路径规划的过程中非常重要，它通常以规划的曲线作为未来车辆可能的行驶路线。对该曲线进行安全分析，从而确定期望的曲率与速度。如果所规划的曲线与期望的行驶轨迹不一致，则说明曲线的安全性分析失效，该无人车很有可能出现安全隐患，甚至会陷入某一狭小区域而无法通行[6]。

2 路径规划常用算法

2.1 传统算法

传统路径规划算法包括A*算法、人工势场法、模糊逻辑算法、禁忌搜索算法等。文章仅对最常见的前两种算法做详细说明。

1）A*算法[7]是一种典型的启发式搜索算法，它也是静态路网中求解最短路径最有效的直接搜索算法。A*算法通过一个估价函数来引导和决定搜索方向，从起点开始向周围进行扩展搜索，利用估价函数来获取周围每个节点的价值，并从获取的周围节点中选择代价最小的节点作为下一个扩展节点，不断循环重复这一过程直到到达目标点，结束搜索，从而生成最终路径。由于每次选择的扩展节点的代价都是最低的，所以最终生成的路径代价也是最低的。

该算法具有完备的特性，它的优势在于对解的捕获能力是完全的。但由此会产生算法复杂度大、很难在动态移动障碍物的环境下较好运用的弊端。针对这种情况，文献[8]将该算法与跳点搜索算法相结合，在搜索过程中优化搜索策略，通过跳点搜索算法挑选出一批具有代表性的跳点进行扩展，而不是评估所有相邻节点进行扩展，避免了A*算法寻路过程中对大量中间节点的计算。此外，文献[9]提出了一种凸优化和A*算法相结合的避障路径规划算法，该算法允许A*算法利用大尺度网格规划出一条最优的大致趋势路径，并通过交替使用2 种凸优化算法快速计算出地面环境中无障碍凸多边形及其最大面积内切椭圆，以便移动机器人在该区域内进行局部避障和任务动作规划。

2）人工势场法[10]（APF）是一种虚拟力法。将被控对象在环境中的运动虚拟为在受力场中的运动，行驶环境中的障碍物对被控对象生成斥力势场并对其产生斥力，在目标点位置以及希望被控对象进入的区域生成引力势场并对其产生引力，对被控对象产生的引力和斥力进行矢量合成，二者产生的合力使得被控对象沿着无障碍物的路径运动。

该算法结构简单、实时性强、规划路径高效平滑，但遇到复杂环境易陷入局部最小点或者产生剧烈震荡。因此，该算法不适合对动态目标进行定位、跟踪和避障。文献[11]提出了一种改进的基于连通性分析的人工势场方法，并将其应用于LBS 系统的路径规划问题。在连通分析的基础上，在传统的人工势场算法中引入速度因子，构造新的重力场函数和排斥力场函数，利用速度因子这一矢量特性，使用户可以跟踪动态目标，有效避开移动过程中的障碍物，从而获得最佳路径。文献[12]针对传统人工势场法中的目标不可达问题和局部极小值问题提出了一种改进的斥力势场函数，实现了势场的调节。在改进的斥力场函数中引入了智能车辆与目标点的相对距离，增加了调节因子实现势场调节，使得整个态势场的最小势点始终位于目标点。同时针对障碍物与目标点之间的引力和斥力平衡所引起的局部极小化问题，提出了模糊控制算法的策略，使其摆脱最小值点。

4 种常见的传统路径规划算法在优化路径规划时存在的优缺点比较，如表1 所示。

表1 传统算法在优化路径规划时存在的优缺点比较

2.2 智能仿生学算法

智能仿生算法主要有粒子群算法、蚁群算法、神经网络算法、遗传算法、灰狼优化算法、烟花算法、人工鱼群算法等。

1）粒子群算法[13]（PSO）主要是通过模拟鸟群的觅食行为来搜索目标函数的全局最优值。由于传统的粒子群优化算法在寻找全局最优解时存在早熟收敛及收敛精度低等缺点，因此针对粒子群算法的研究主要集中在改进与优化种群结构以及相应参数等方面。为了解决未知环境下的路径规划问题以及提高粒子群优化算法的收敛速度，文献[14]提出了一种基于仿生神经网络改进的粒子群优化方法，利用仿生神经网络优化基于该方法的粒子群优化算法的适应度函数，并对粒子的速度更新算法进行改进，同时利用动态环境建模的方法来解决未知环境下的路径规划问题。此外，文献[15]提出了一种基于电子海图下的改进粒子群优化算法。利用电子海图建立三维静态环境模型，同时构造期望的路径航程、危险度和平滑度函数。在改进的POS 算法中综合考虑粒子位置与速度的影响，引入了搜索因子和同性因子自适应的调整粒子的惯性权重，并结合鱼群算法的“跳跃”过程使算法具有较强的平衡“探索”与“利用”能力，以及逃离局部最优“陷阱”的能力，有效地克服了粒子群算法在优化目标函数时存在过早收敛和求解能力差的问题。

2）蚁群算法[16]（ACA）是一种模拟自然界中蚂蚁群觅食行为的群优化算法。当蚂蚁处于觅食状态时，它会在所遍历的路径上分泌信息素，而且该信息素可以被其他蚂蚁识别，蚂蚁会优先选择信息素浓度较高的路径，并且其自身会释放一定量的信息素，从而增强了该条路径上信息素的浓度，因此形成了一个正反馈机制，同时信息素的浓度也会随着时间的推移而减弱。最终，可以通过不断的迭代获得一段从出发点到目的地的最短的路径。虽然这一正反馈机制能够加快收敛速度，但是会有降低蚁群多样性、减弱全局搜索能力且在复杂环境下容易陷入死锁状态的弊端。为此，文献[17]提出了一种改进的蚁群算法，调整传统蚁群算法的转移概率，自适应地调整信息素强度Q 值并引入信息素约简因子，加快算法的迭代速度，最后利用烟花算法中的爆炸算法来扩展搜索区域，避免陷入死锁状态。此外，文献[18]提出了一种自适应路径规划方法，该方法利用自适应调整启发式函数提高了算法的搜索效率，对衰减系数进行动态调整，加快了基于蚁群规则的算法的收敛速度。并更新信息素，限制信息素浓度的最大值和最小值，提高了该算法的搜索能力。

3）神经网络算法[19]是模拟人脑思维能力，通过大量模拟神经元实现非线性算法功能的网络。它与人脑处理信息的过程相似，具有学习和自适应功能。区别在于其理论基础是数学网络拓扑。人工神经网络的主要特征是能够并行处理信息的非线性网络，具有学习功能、容错能力、信息的分布式存储能力和鲁棒性。尽管其具备优秀的学习能力，但存在泛化能力差的问题。神经网络算法学习能力强，鲁棒性较好，因此很多研究者将该算法与其他优秀算法结合起来进行路径规划的研究。针对移动机器人未知空间的路径规划问题，文献[20]提出了一种基于门控递归单元-递归神经网络模型的动态路径规划方法。利用具有传感器输入的深度神经网络，生成新的控制策略输出到物理模型中去，以控制机器人的运动，从而避免机器人发生碰撞。并提出一种新的信息素更新和状态转移规则来提高算法的收敛速度，同时引入新的势场来解决传统APF 的不足。

4）遗传算法[21]是一种基于生物进化机制的优化算法，具有易于实现、收敛速度快等优点。遗传算法在简单地图上有很好的表现力，但在复杂、有很多障碍的地图上表现很差。由于遗传算法只能在解空间中随机搜索，不能充分利用给定的地图信息。为了克服遗传算法的早熟现象和上述不足，文献[21]提出了一种自适应遗传算法，即在进化过程中加入自适应算子和监督算子2个遗传算子。自适应算子可以根据障碍物的位置和地图的复杂性，进行自适应的路径调整。监督算子用来配合自适应算子检测染色体中是否存在重复或冗余的基因，如果存在，相应的基因将被删除，将有助于加快进化过程、缩短路径长度以及平滑路径。

4 种常见的智能仿生学算法在优化路径规划时存在的优缺点比较，如表2 所示。

表2 智能仿生学算法在优化路径规划时存在的优缺点比较

2.3 强化学习算法

强化学习算法[22]是一种完全不需要环境及自身先验知识的学习方法，利用人类思维模式中试错学习的方式，在规划过程中感知当前周围环境的同时，根据当前环境信息给予的反馈选择行为来寻找最优策略。基于该研究方法，在智能车以及移动机器人的路径规划方面取得了突破性的成果。文献[23]针对智能车辆传统路径规划算法中无法消除模型误差、对跟踪控制依赖程度高且无法求解控制动作的问题，提出了一种基于深度强化学习的模型迁移（DDPG）的智能车辆轨迹规划方法。利用DDPG 算法降低了规划方法对样本数据的依赖，能够处理连续输入和连续输出的模型训练，直接输出控制动作和轨迹序列。该方法较最优控制计算复杂度低，并使用模型迁移方法提高模型的泛化性能。但是，该方法并未解决智能车路径规划过程中常存在动态环境感知预估不足的问题。文献[24]提出了一种使用基于蒙特卡罗预测及深度策略梯度学习（MCPDDPG）的智能车路径规划方法，将多个单一强化学习算法应用到规划系统的子任务中。利用提取的环境信息对周围车辆的状态变化进行预测，设计Q 学习行为决策方法，便于智能车自行学习风险预估并及时做出决策规避，同时构建深度强化学习最优智能驾驶策略。文献 [25]提出了一种基于组合深度强化学习（DRL）的机器人巡逻路径规划方法，该方法结合强化学习和神经网络进行路径优化。先通过异步优势动作评价（A3C）算法对DRL 进行预训练，利用训练数据对随机策略参数化的递归神经网络（RNN）进行优化，有效解决了单独使用演员评论家（AC）方法的不收敛问题，且训练速度较快。再利用有效规划（EP）搜索策略对当前巡逻路径进行规划，并将在A3C 中得到的训练参数作为EP 的输入。在每个解码步骤中，选择概率最大的巡逻点。

3 结论

随着科技的不断发展，路径规划技术面对的环境会越来越复杂，路径规划所用到的算法必须具备迅速响应复杂环境变化的能力。单独使用某一种或某一类算法往往会因其自身的局限性不再能解决路径规划时遇到的复杂问题。因此提出3 点建议：

1）在对某类算法深入研究的基础上，可以结合不同算法的优点，使用2 种或多种混合算法进行路径优化，大大提高路径规划的效率和可行性[26-27]，并把环境建模方法与路径规划算法巧妙结合起来，发挥最大的价值。同时，还要针对当下研究热点（如多智能体并联路径规划、多车辆协作动态路径规划），设计出集合多种算法优点的融合算法以解决更加复杂的问题。

2）当下研究的自动驾驶车辆路径规划多针对单目标、平面二维场景，随着无人出租车及智能交通运输业等的快速兴起，这些单一目标简单场景已经不能满足使用要求。在今后的研究中可针对多目标、多维空间场景进行避障路径规划以提高作业效率。利用强化学习算法的优点，结合传统路径规划算法或智能仿生学算法等来进行路径规划以改善规划结果，提高规划效率[28]。

3）在今后的车辆路径规划研究中，应该多结合考虑车辆几何形状、运动学和约束条件，以此来提高路径规划的精确性。可以利用状态格策略进行路径在线搜索，缩短搜索时间[29]。