自动驾驶汽车避障运动中路径规划研究综述

明瑞阳

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

主题词：自动驾驶；避障；轨迹规划

0 引言

随着汽车产业市场规模的不断扩大，汽车产业在加速向智能化、网联化、电动化和共享化转型。2021年8 月发布的GB∕T 40429—2021《汽车驾驶自动化分级》[1]将驾驶自动化从0级至5级分为6级，其中以5级为最高自动驾驶等级。

据行业报告显示[2]，在2020 年中国自动驾驶汽车行业的市场规模约为81.32 亿元，较上年的84.2 亿元同比下降了约3.5%，到2021年增长至94.1亿元左右，同比增长了约15.72%。在我国自动驾驶方面政策、技术发展和市场需求增长多方面带动下，预测未来几年自动驾驶汽车的市场规模将会持续增长，到2023年有望达到约120.5亿元。

在自动驾驶汽车发展中，由于避障功能与车辆安全具有高度耦合性，因此在向高等级自动驾驶发展的过程中，避障功能始终是汽车企业、大学和研究机构重点研发的自动驾驶功能之一。

整个避障运动分为4个动作，包括信息感知、智能决策、路径规划和运动控制[3]，通过这4个动作使车辆完成躲避障碍物或制动动作。在制动过程中，如何规划出一条合理且安全的轨迹尤为重要。避障路径规划也被称为局部路径规划，与全局路径规划相比，只对当前场景进行路径规划且能够适应不可预见的障碍物。目前，局部路径规划的主要方法包括基于采样的规划方法、人工势场算法、蝼蚁算法和神经网络算法[4]。

本文对基于采样和人工势场的路径规划算法进行综述，分析对比这2种算法的优缺点，并对近年来国内外研究人员对这两种路径规划算法进行的优化融合进行了归纳，为后续研究人员开展自动驾驶轨迹规划研究与开发提供参考。

1 基于采样的规划方法

目前，基于采样的规划方法可以避免配置空间的离散化和显式表示，从而可以很好地扩展到高维空间。概率路线图（Probabilistic Road Maps,PRM）[5]和快速探索随机树算法（Rapidly-Exploring Random Tree,RRT）[6]是基于采样法进行路径规划的代表性方法。

1.1 概率路线图算法

基于概率路线图算法解决路径规划问题是在给定的环境中设置多个点位，除去被设置在障碍物上的点位外，对剩余点位进行算法运算，从而得出一条规避障碍物的路线，如图1~图3所示。

图1 概率路线图设置点

图2 去除障碍物点位后的概率路线

如图3所示，在所规划的路段中，虽然所有点位均不在障碍物上，但2点之间的路线仍会经过障碍物，如灰色路线，因此碰撞检测耗时较长，导致规划效率较低。

1.2 快速探索随机树算法

与概率路线图算法不同，快速探索随机树算法是1 种递增式的构造方法。在整个路径规划过程中，仅随机生成1个点位，如果该点位处于无碰撞点位，则寻找探索树种离该点最近的节点作为基准节点，从该基准节点以固定步长向随机点位延伸，每段延伸线的终点会被当作有效节点加入搜索树种。该过程一直持续到目标节点与搜索树的距离小于最初设定的数值，然后寻找1条连接起点和终点的最短路径。该算法有一些不足之处，如搜索时间差异大，在狭窄的通道情况下性能差，离最优路径远。

1.3 算法改进

为了解决概率路线图算法中采样点过多导致运算速度过慢的问题，Mika 等[7]提出了1 种基于邻域的方法，通过滤掉不必要的节点来减小路线图的大小。Kumar等[8]提出了1种减少节点的概率路线图算法来减小路线图大小，通过附近障碍物和目标的距离误差以及高斯成本函数来消除部分节点，以提高规划效率。

而对于快速探索随机树算法而言，尽管改善后的RRT*[9]能够通过引入近邻搜索和随机树重新布线操作来实现渐近最优，但因为随机抽样机制会影响收敛速度，因此收敛到最优解需要大量时间。Noreen 等[10]提出了1种基于RRT*的RRT*—可调整边界（RRT*—AB）离线规划算法，该算法包括3 步策略：即连接区域、基于目标的有界采样和路径优化。基于目标的有界抽样在连接区域的边界内进行，以寻找初始路径，而连接区域可在复杂的环境中扩展，一旦找到路径，就使用节点剔除和集中的有界抽样对其进行逐步优化，最后的路径通过全局修剪进一步改进，以消除多余节点。为了提高该算法路径规划效率，除了剔除不需要的节点外，较为主流的方式是将其它原理或算法和快速探索随机树算法进行融合，以解决规划效率和路线质量问题。

Jeong 等[11]将三角不等式与RRT*相结合提出了Quick-RRT*（Q-RRT*）,其扩大了父顶点集合，产生路径成本比RRT*算法低且能更快收敛到最优。Zhuge等[12]在Q-RRT*基础上，将启发式信息与Q-RRT*算法优化能力相结合，提出1 种基于虚拟光的Q-RRT*（LQRRT*）,该算法相比于Q-RRT*算法优化了采样空间，提高了采样效率且试验证明了内存占用量较少。

Wu 等[13]提出了1 种基于RRT 的路径搜索算法Fast-RRT，该算法由1个改进RRT模块和快速最优选择模块融合，前者稳定获取1条初始路径，后者将多条初始路径进行合并获得近似最优路径。最终通过试验得出，在相同环境下Fast-RRT 算法会比RRT*算法有着更快的速度和更高的稳定性。Wang 等[14]为了解决狭窄空间路径规划问题，提出了1种自适应扩展双向RRT*（AEB-RRT*）算法，该算法从设定的起点和终点双向同时进行扩展，并根据碰撞到障碍物次数自适应调整采样频率，将得到的可行路径通过插值和三角不等式原理进行处理，得到更短的可行路径。

为了减少RRT 本身的局限性，除上述算法之外，还有基于势场的P-RRT*、结合基于势函数的RRT*（P-RRT*）和Quick-RRT*的PQ-RRT*[15]、将双向人工势场与快速探索随机树星（RRT*）相结合的RRT*-Connect（P-RRT*-Connect）规划算法[16]等，都有效地减少了RRT*算法本身的局限性。

1.4 小结

概率路线图和快速探索随机树法都是常见的路径规划算法。

通过对上述内容的综述，可将概率路线图算法和快速探索随机数算法的优缺点进行归纳对比，如表1所示。

概率路线图算法优点在于：随着搜索时间的增加，其成功规划路径的概率会快速向1收敛，也证明其具备概率的完备性，且具有较高的精度，可以在较为复杂的环境中规划路径。

概率路线图算法缺点在于：该算法需要在全局地图中建立随机采样点，因此运行时间较长，且不能很好地应对障碍物移动的情况。

快速探索随机树法优点在于：其路径生成速度快，能够在较短的时间内找到1条可行路径，且能够应对环境变化，自适应地规划出合适的路径，灵活性较高。

快速探索随机树法缺点在于：处理复杂环境时，随机树分叉多，使得不稳定性较大。

随着人工智能技术的发展，概率路线图和快速探索随机树法将向高效和智能化发展。这2种算法可以结合深度学习技术，实现更加精准和高效的路径规划。

2 人工势场法

人工势场算法是目前运用较为广泛的局部路径规划算法，其基本思想是将物体在具体环境中的运动，转化为人为抽象势场中的运动，由目标点对物体产生吸引力，由障碍物对物体产生排斥力，使得物体能顺利绕过障碍物到达目标点。其中，物体在抽象势场中的受力情况如图4所示，其中，Fatt是目标点对物体的吸引力，Frep是障碍物对物体的排斥力，Ftotal是吸引力和排斥力产生的合力。人工势场法优点在于该算法生成的路径平滑、计算量小、执行效率高[17]，但是同样存在着局部极值点和目标不可达的问题[18]。

图4 物体在人工势场中的受力情况

对于障碍物较少的简单场景下，人工势场算法可以较为容易地规划出1条无碰撞的路径以快速到达目标点。但在复杂场景下，存在局部极值点，在吸引力和多个排斥力的反复作用下，物体在多个障碍物间做振荡运动，无法驶出局部极值点，如图5所示。

图5 物体进入狭窄环境

如图6所示，对于物体进入三面封闭的环境后，由于目标点对物体向上的吸引力和障碍物墙壁对物体向下的排斥力两个方向相反的作用力作用下，使得该场景无法使用人工势场算法完成路径规划，存在目标不可达的问题。

图6 物体进入陷阱区域

2.1 局部极值点的人工势场算法改进

在狭窄环境下，路径中可能存在极值点使物体发生振荡运动从而难以到达目标点，针对这种问题，Duan等[19]在基于安全距离模型的人工势场中，对于可能存在局部极值点的道路工况，通过引入第二虚拟目标点，产生第二道目标点吸引力，克服了局部极值点问题。同样，Wang等[20]通过左转弯势场法使物体在脱离局部极值点附近，若物体已经处于局部极值点时，则通过虚拟目标点法在合适的位置设置虚拟点，并忽略障碍物和初始设置的目标点吸引力的影响，使物体在局部最小点转弯和跳出。

Gu等[21]在传统人工势场算法中，添加了1种可修正的斥力势场函数，并将此改进的人工势场算法与模糊控制算法进行融合，利用该融合势场解决局部极值点问题。Ma等[22]通过引入随机扰动势能的调节机制，解决了在局部极值点难以移动的问题。Shen 等[23]针对局部极值点导致路径规划失败的问题，将快速探索随机树算法与人工势场法相融合，将快速探索随机树所规划的节点设置为新的目标点，为物体提供吸引力的同时弱化预设目标点作用，并改进障碍物排斥势场功能，确保吸引力的力源可及性，保证物体出现在接近局部极值点附近时，能完成路径规划。

2.2 针对目标点不可达的人工势场算法改进

对于目标不可达问题，尹凤仪等[24]针对目标点附近人工势场建立了规则，在障碍物周围排斥力势场函数加入距离影响因子，使得物体能够抵达目标。Zhang等[25]为了解决物体在进入陷阱区域的目标点不可达问题，通过对斥力场函数进行改进并选择1个虚拟目标点，从而使物体逃离陷阱到达目标点，如图7所示。同样，Yang等[26]通过增加引力解决了目标不可达问题。

图7 物体进入陷阱区域所设的虚拟点

Cao 等[27]在人工势场法中引入了调节因子，以解决轨迹规划中目标不可达问题。

2.3 融合人工势场的改进算法

针对不同应用场景，张强等[28]将全局路径规划算法与局部路径规划算法相结合，提出1种融合安全A*和人工势场的融合算法，在A*算法中的代价函数里添加安全距离，并将A*算法中的部分关键节点设置为人工势场中的目标点提供吸引力，经仿真验证，该方法所规划的路径简短且避障能力较好。

音凌一等[29]为了解决适用于全局路径规划的灰狼优化算法求解效率低和易陷入局部最优的问题，将灰狼算法全局路径规划的节点设置为人工势场临时目标点，并改进临时目标点为临时边界，进行局部路径规划。最终通过仿真表明，在全局静态环境和局部动态环境下，该融合算法在规划路径时有效性很好。

Wu 等[30]提出了1 种将人工势场法和IRRT*算法相结合的融合算法，把人工势场法中的势场引入IRRT*算法中的搜索树扩展阶段，提供搜索树扩展方向指引，提高了IRRT*算法的收敛率和搜索效率。同样，辛鹏等[31]为了减小快速探索随机树法扩展时的随机性，把扩展方向通过人工势场法进行约束，减少随机树向正确目标点扩展的探索时间。

2.4 小结

人工势场法是基于虚拟势场的路径规划算法，它通过构造人工势场来引导物体在环境中移动，从而实现物体自主避障和路径规划。人工势场法的优势主要包括：算法简单易懂、实时性好，且可以用于包括室内室外、平面地形和复杂地形多种场景。其缺点在于作为1种局部路径规划方法，存在局部极值点问题，当物体陷入极值点后将无法继续前进。且该方法在使用过程中需要设定一系列参数，如障碍物排斥力、目标点吸引力等，这些参数设置需要经验和调试，可能会影响路径规划效果。

未来展望方面，人工势场法作为1 种经典的路径规划算法，已经被广泛应用于实际场景中。随着人工智能技术的发展，人工势场法仍然具有重要的应用前景。人工势场法也可以与其它路径规划算法相结合，或者与神经网络技术相结合，形成更加高效和使用便捷的路径规划算法。

3 结束语

避障技术在自动驾驶汽车或者是其他无人设备上来说都是1 项核心功能，针对动态或静态环境，合理、高效规划出1条平稳、无碰撞的路径是避障运动能否安全完成的重要核心，本文对3种局部路径规划方法优缺点和目前发展现状进行了综述。

概率路线图法和快速探索随机树法均是基于采样的路径规划方法。概率路线图的优点在于随着搜索时间增加，其成功规划出路径的概率会快速向1收敛，具备概率的完备性。快速探索随机树法的优点在于有更强方向性，且相比于概率路线图流程更加简单。但是这2种规划方法都存在着规划时间较长的问题。而人工势场法优点在于生成的路径平滑、计算量小，同时该方法对传感器的误差有一定的鲁棒性，其缺点在于存在局部极值和目标不可达问题。

在进行路径规划时，研究人员需要根据不同的待规划环境采用不同的路径规划策略。就目前而言，多种算法融合后进行路径规划，往往比单种规划方法所得到的路径规划效果好，同时也可避免一些如探索随机树扩展时间长、人工势场法容易陷入陷阱区域的问题。