浅析几种无人驾驶汽车路径规划算法

2021-03-03杨时川胡晓晓胡汉桥

时代汽车 2021年1期

关键词：路径规划无人驾驶发展方向

杨时川　胡晓晓　胡汉桥

摘要：路径规划是自动驾驶关键技术之一，各种路径规划算法现已不断改进并不断涌现。本文根据全局和局部路径规划对常用路径规划算法进行分类，对几种常用的路径规划算法原理进行介绍，并分析其发展方向。

关键词：无人驾驶路径规划算法原理发展方向

Analysis of Several Unmanned Vehicle Path Planning Algorithms

Yang Shichuan，Hu Xiaoxiao，Hu Hanqiao

Abstract：Path planning is one of the key technologies of autonomous driving. Various path planning algorithms have been continuously improved and emerging. This article classifies common path planning algorithms based on global and local path planning， introduces the principles of several common path planning algorithms， and analyzes their development direction.

Key words：unmanned driving， path planning， algorithm principle， development direction

1 引言

自动驾驶汽车能够自动感知周围环境、根据环境信息自动做出运动决策并实施行驶。自动驾驶系统的关键技术主要由四个部分组成，分别为：环境感知、行为决策、路径规划和运动控制。环境感知即为车辆凭借自身的各传感器相互配合工作来保证车辆正常行驶，常用的传感器有图像传感器，激光雷达，毫米波雷达，超声波雷达，生物传感器。行为决策是根据传感器获得的信息对未来一段时间的行车环境进行预测，如车道保持、转弯、制动、加速等。运动控制是指根据行为决策和路径规划对车辆本身运动状态进行控制，以达到期望的路径和期望的速度。

路径规划是是指生成一条连接车辆行驶起点位置与终点位置，且不与环境中障碍物发生碰撞的几何路径[1]。实际上两个关键点分别是车辆从A点到B点，不与环境中障碍物发生碰撞。一般前者称为全局路径规划，根据全局静态地图规划出一条从起始点到目标点的可行驶的最优路径。后者则体现了局部路径规划含义，智能车辆的局部路径规划是指基于传感器等设备感知行驶遇到的空间障碍物，在满足动力学、运动学约束以及稳定性、舒适性等评价指标的条件下预先或者实时地为智能车辆规划出从出发点到目标点的最优路径[2]。自动驾驶技术路线很多是在轮式机器人的技术路线基础上改进和发展。

2 全局路径规划算法

对于全局路径规划和局部路径规划因为要考虑的内容不一样，所以在选择算法时也会有各自倾向。自动驾驶技术路线很多是在轮式机器人的技术路线基础上改进和发展，因此很多算法也是在此基础之上改进以适合自动驾驶的情形，全局路径规划算法主要有A*算法、可视图法、模拟退火法、遗传算法、粒子群算法、蚁群算法等，现在将全局路径规划典型算法进行简单介绍。

2.1 A*算法

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，依据代价函数来搜索最优路径，既考虑从初始结点到当前结点的代价值，又考虑了当前结点到目标结点的启发值，是一种启发式搜索算法[3]。在路径搜索过程中，A*算法使用代价函数来评估节点的质量，算法将选择的代价函数数值最小的节点作为下一步的节点，然后它将继续从下一个节点搜索，直到达到目标点。

A*算法的代价函数如下：

f（n）=g（n）+h（n）

其中函數f（n）是结点n的当前代价值，函数g（n）是从初始结点到当前结点 n的实际代价值，h（n）是启发函数，为当前结点n 到目标结点最短路径的估计代价，是一个预测值。g（n）经常都是固定的数值，然而h（n）却不是固定的，它的改变会影响到f（n）是否为最短路径。因此在 A*算法中，启发函数h（n）的设计非常重要，合理的启发函数设计能帮助A*算法在路径规划中快速简洁，提高寻路效率。启发函数一般有四种表达式，但是最常用的是用曼哈顿距离定义。

曼哈顿距离：坐标横纵方向的距离之和，允许向上、下、左、右移动，启发函数表示为：h（n）=D*[abs（xb-xn）+abs（yb-yn）]，（xb，yb）为目标节点坐标，（xn，yn）为当前结点坐标，其中D表示h（n）的代价系数，一般取为10。但是针对不同的环境，可以选用不同的代价系数，例如文献3就根据当前节点和目标结点的距离不同，尝试用不同代价系数D，当障碍物环境地图不变的情况下减少了搜索时间。文献4提出了一种融合改进A*算法和动态窗口法的全局动态路径规划方法。设计了一种关键点选取策略，能够去除传统A*算法规划路径序列中的冗余点，从而提高路径规划性能[4]。

2.2 蚁群算法

蚁群算法是一种仿生算法，它是用来寻找优化路径的机率型算法。蚂蚁从蚁穴出发，在寻找食物过程中，在路径上会释放信息素来提醒同伴这条路径是否为一条优秀路径。蚁群算法的寻路模型可以简化如图1所示，1号蚂蚁选择{e1}路径取得食物并返回，2号蚂蚁选择{e2+e3}路径，信息素会随着时间的推移而逐渐挥发，在1号蚂蚁返回时，{e1}路径上会存在两倍于{e2+e3}路径上的信息素，剩下的蚂蚁在寻找食物时，根据信息素的浓度选择行走的方向，几个周期后，大部分蚂蚁就会逐渐集中在最短路径{e1}上。

它最开始被用来解决旅行商问题，即从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。后来世界各地研究工作者对蚁群算法进行了研究和应用开发，该算法现已被大量应用于数据分析，路径规划，机器人协作问题，水利，采矿等领域。在建立模型时，初始化参数会对结果产生较大影响，容易陷入局部最优，所以在建立模型时要选择合适蚂蚁数量，信息素常量，迭代次数，信息素挥发因子等大小。为了加快运算速度并得到最优解，有不同学者对蚁群算法进行改进。在路径规划研究领域中，文献5对于地图环境静态不变的问题，在路径规划的初始阶段，改进算法根据地图的结构和目标点的位置信息给蚂蚁正确的方向引导，并以此来优化初始信息素的分布，加快了算法的搜索速度[5]。文献6从信息素的更新方式及局部搜索策略方面进行了改进，并将虚拟路径这一概念应用于动态路径规划中[6]。

3 局部路径规划算法

局部路径规划，也称为避障路径规划，即考虑本车和障碍物之间的几何关系寻找出一条避免与障碍物发生碰撞的路径，是无人驾驶汽车的重要功能模块之一。常用的局部路径规划算法有人工势场法、神经网络算法、快速搜索随机树法、智能水滴算法等。

3.1 人工势场法

人工势场法路径规划的基本思想是将汽车在环境中的运动设计成为一种抽象的人造引力场中的运动。在无人驾驶汽车的运行环境中，人工势场模型的引力主要来源于目标点对汽车的引力势场，与目标点距离越大引力势能越强，引力方向朝向目标点。障碍物对汽车产生斥力，斥力的大小随着与障碍物的距离增大而减小，方向指向远离障碍物方向。最后根据引力和斥力的合力来控制汽车的运动。

智能汽车受到的势场是单个引力势场和斥力势场之和，可表示为：

Utotal（X）=Uatt（X）+Urep（X）

汽车所受合力为：Ftotal（X）=Fatt（X）+Frep（X）

汽车在实际环境中自主驾驶时，外部环境是动态的和变化的，并没有考虑车辆行驶动力学和运动学，因此在实际使用时需要增加约束条件。人工势场法也有自己的局限性，如当车辆离目标点很远时，引力特别大，相对较小的斥力在甚至可以忽略的情况下，物体路径上可能会碰到障碍物，又如在某个点，引力斥力刚好大小相等，方向相反，则车辆容易陷入局部最优解或震荡。

3.2 快速搜索随机树算法

快速搜索随机树算法（RRT）RRT是一种在完全已知的环境中通过采样扩展搜索的算法，它以一个初始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域，便可以在随机树中找到一条由从初始点到目标点的路径。采用RRT算法进行无人驾驶车辆路径规划步骤如下：

3.2.1 初始化

需要提供已知环境地图，包括障碍物位置以及终点位置。然后将车辆的起点作为随机树的根节点。

3.2.2 随机采样

随机树在生长时理论上是朝着终点进行生长，但是由于有障碍物的存在，所以在每次选择生长方向时，有一定的概率会向着目标点延伸，也有一定的概率会随机在地图内选择一个方向延伸一段距离。

3.2.3 树节点扩展

在选取采样点之后，如何判断采样点是否为随机树节点？这里采用的策略是寻找距离采样点最近的树中的节点，将其作为新扩展的节点的父节点，然后以该父节点为基础，向采样点的方向延申一定距离，将延伸后的节点作为新节点并加入树中。这个步骤的前提条件是新节点以及父节点到新节点的路径不发生碰撞，如果發生碰撞，则放弃该采样点和新节点。

3.2.4 终止条件

一般情况下，在树节点扩展的方法基础上，可以将扩展的新节点是终点作为终止条件，为了避免不存在路径导致的死循环问题，增加最大迭代次数作为另一个终止条件。

该算法也有自己的局限性，作为一种随机性算法，在同样的环境中可能得到不同的路径，而且随机采样的特性会导致路径不平滑。

4 总结与展望

无人驾驶中的路径规划算法有很多，但是都有自己的局限性，可以结合各自算法优缺点使多种算法相融合。在路径规划中要考虑动态障碍物、道路安全法规、车辆行驶动力学和运动学等问题。车辆运动速度快，也需要考虑算法的复杂程度，减少计算的时间，更快的做出决策。

课题来源：湖北省武汉软件工程职业学院“一专一项”教学改革项目。

参考文献：

[1]袁师召，李军.无人驾驶汽车路径规划研究综述[J].汽车工程师，2019，05：11-13.

[2]张朋飞，何克忠，欧阳正柱等.多功能室外智能移动机器人实验平台-THMR-V[J].机器人，2002，06：88-95.

[3]关泉珍，鲍泓，史志坚.基于A*算法的驾驶地图路径规划实现[J].北京联合大学学报（自然科学版），2016，30（02）：31-39.

[4]程传奇，郝向阳，李建胜等.融合改进A*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报，2017，51（11）：137-142.

[5]喻环.改进蚁群算法在机器人路径规划上的应用研究.[D].安徽：安徽大学，2017：11-20.