基于改进A*算法的无人驾驶车辆路径规划方法研究

林黄智, 田柳

基于改进A*算法的无人驾驶车辆路径规划方法研究

林黄智1, 田柳2

(1. 安徽职业技术学院 机电工程学院, 安徽 合肥, 230011; 2. 中国移动通信集团安徽有限公司, 安徽 合肥, 230088)

针对传统A*算法所规划路径距离障碍物近、转折点多、路径不平滑的问题, 对A*算法进行改进并应用于无人驾驶车辆路径规划中。在传统A*算法分析的基础上对背向障碍物搜索和评价函数进行改进, 同时采用3次样条插值方法对规划后路径平滑处理。将传统A*算法和改进A*算法应用于MATLAB环境下搭建的无人驾驶车辆模型进行路径规划仿真分析。结果表明, 改进A*算法所规划的路径距离障碍物比较远, 转折点数量明显减少, 同时路径更加平滑。

改进A*算法; 路径规划; 无人驾驶车辆

国民经济的快速发展使得汽车保有量不断增加, 这使得城市交通更加拥堵, 各种交通事故频发。每年全球死于交通事故的人数占据总死亡人数的20%左右, 同时也造成了巨大的经济损失[1]。人工智能技术的快速发展使得无人驾驶汽车受到了越来越多的关注, 无人驾驶技术对降低汽车道路交通事故发生率具有至关重要的意义。路径规划是无人驾驶车辆研发的核心技术之一, 其任务是获取一条安全无碰撞的轨迹, 确保车辆沿着该轨迹可以从起点安全地到达目标点[2]。无人驾驶车辆在行进的过程中需要对动静态的障碍物进行避让, 同时确保路径最短, 实现能量最优化[3]。

A*算法是一种求解最短路径的启发式搜索算法, 在无人驾驶车辆路径规划中得到了广泛的应用[4]。但是采用A*算法规划的路径往往存在折线、转折多的问题, 同时和障碍物距离比较近, 容易发生碰撞, 存在比较大的安全隐患[5]。基于此, 本文在A*算法的基础上对其进行改进, 同时将改进的A*算法应用于无人驾驶车辆的路径规划中, 为无人驾驶车辆路径规划提供参考。

1 A*算法及改进

1.1 A*算法

A*算法是一种静态全局路径规划算法, 其从车辆的起始点开始, 根据启发函数来搜索和起始点相邻的节点, 同时通过代价函数来选择一个最优的相邻节点作为当前节点进行继续搜索, 直到搜索到目标点为止, 最后由目标点回溯到起始点形成一条全局规划的路径。采用A*算法进行无人驾驶车辆的路径规划需要建立A*优化函数[6], 即(,) =(,) +(,), 其中:(,)为无人驾驶车辆起始点到目标点的估价函数;(,)为无人驾驶车辆起始点到当前点的实际代价;(,)为无人驾驶车辆当前点到目标点的代价, 是启发函数。

对于A*算法而言, 算法的效率高低取决于启发函数。如果启发函数(,) = 0, 那么评估函数完全由(,)决定, 此时A*算法退化为Dijkstra算法[7]。对于启发函数(,)而言, 其包含的启发信息越多, 那么在实际路径搜索的过程中效率就会越高[8]。如果启发函数(,)包含的启发信息比较少, 那么在实际路径搜索的过程中效率就会大大降低, 同时所规划的路径和实际的最优路径之间往往有比较大的差距。在A*算法中, 启发函数(,) = 0决定了路径的搜索方向和算法的效率, 定义启发函数为(,) =11+2(2– 21), 其中:1为对角线移动一格的代价;2为水平移动一格的代价;1= min(|-|, |-|),2= |-| + |-|, (,)为无人驾驶车辆当前所在位置; (,)为无人驾驶车辆路径规划目标点所在位置。

1.2 A*算法改进

为了解决采用传统A*算法进行无人驾驶车辆规划路径存在的距离障碍物比较近、转折点数量多以及路径不平滑等问题, 本文从3个角度对传统A*算法进行改进。

1.2.1 背向障碍物搜索

无人驾驶车辆运行中由于惯性的存在, 如果所规划路径距离障碍物过近, 那么和障碍物碰撞的可能性就会大大增加。采用背向障碍物搜索策略, 即和障碍物相邻的节点不会作为规划路径的考虑范围, 有效克服了传统A*算法所规划路径距离障碍物过近的缺陷[9]。

1.2.2 提取最优转折点

采用传统的A*算法进行无人驾驶车辆路径规划, 得到的路径常常包含有比较多的转折点。无人驾驶车辆在实际运行的过程中如果采用A*算法所规划的路径, 那么将会影响到车辆的乘坐舒适性, 同时惯性也使得行车安全性难以保证。采用传统A*算法规划得到的路径中许多的转折点往往是不必要的, 在确保和障碍物保持一定距离的前提下可以剔除一些不必要的转折点[10]。

采用A*算法对无人驾驶车辆进行路径规划, 路径中转折点集合为{p}, 从起始点依次采用有向线段连接之后的转折点, 具体如图1所示。

定义评价函数(x,y), 将其作为最优转折点的选择依据, 评价函数(x,y) = (1-)/1+2, 其中:1为障碍物中心到起始点与转折点连线的垂直距离,2为转折点到障碍物所在线段末端转折点的距离, 具体如图1所示, 系数为可调参数。

图1 起始点连接转折点示意图

计算各个转折点的评价函数, 选择评价函数值最小的转折点为最优转折点。在确定了第一个最优转折点之后, 以该点为新的起点重复上述过程直到无人驾驶车辆目标点结束。从起始点依次连接所有的最优转折点所得到的路径为最终规划的路径。

1.2.3 样条插值平滑路径

2 无人驾驶车辆路径规划仿真分析

2.1 环境建模及地图预处理

在无人驾驶车辆路径规划之前需要对安装在车辆上的传感器采集到的环境信息进行融合, 从而得到一个可以有效表示周围环境的地图模型。本文采用32 × 32的栅格地图来表示无人驾驶车辆周边的环境, 其中可以行使的区域采用白色栅格表示, 障碍物区域采用黑色栅格表示, 在地图的边界均设置障碍物, 避免无人驾驶车辆的初始位置点和目标位置点在地图之外。本论文的研究将无人驾驶车辆视为一个质点, 同时只能在网格范围内运动。在没有边界和障碍物的情况下, 无人驾驶车辆可以向周围8个方向的栅格移动。另外, 无人驾驶车辆在进行路径规划的过程中周围的环境始终保持不变, 即不包含有动态的障碍物。

2.2 仿真试验及结果分析

为了对比传统A*算法和改进A*算法对无人驾驶车辆路径规划的效果, 采用仿真试验进行分析。传统A*算法的路径规划流程如图2所示。改进A*算法主要是采取背向障碍物搜索、优化规划路径转折点以及规划路径平滑对无人驾驶车辆路径进行规划, 使得规划后的路径距离障碍物比较远、路径比较平滑, 提高无人驾驶车辆的行使平顺性。改进A*算法的路径规划流程如图3所示。

图2 A*算法流程图

选择无人驾驶车辆的起始点坐标为(3, 30), 目标点坐标为(29, 11), 分别采用传统A*算法和改进的A*算法进行路径规划, 路径规划结果如图4所示。为了对比传统A*算法和改进A*算法路径规划性能, 从规划路径长度、规划路径转折点个数、规划路径距离障碍物最近距离、运行时间4个方面进行对比, 结果如表1所示。

表1 传统A*算法和改进A*算法仿真结果对比

由图4和表1可知, 传统A*算法对无人驾驶车辆路径规划未考虑车辆和障碍物的距离, 这导致所规划的路径总是和障碍物的边缘相切, 同时存在比较多的转折点。对于改进的A*算法, 其所规划的路径长度比A*算法所规划的路径长度有所增加, 同时路径规划耗时也有所增加, 但是所规划的路径转折点个数明显减少, 所规划的路径确保和障碍物有一定的距离。改进A*算法中的参数对路径规划的长度、规划路径转折点个数、和障碍物的最近距离以及路径规划耗时之间均有一定的关系, 只有通过多次调试才能确保所规划的路径最优。

图3 改进A*算法流程图

图4 无人驾驶车辆路径规划结果

为了确保所规划的路径更加平滑, 在改进A*算法的基础上采用样条插值进行路径平滑。本文采用3次均匀样条插值函数对规划后的路径进行平滑处理, 结果如图5所示。

由图5可见, 采用3次均匀样条插值函数对规划后的路径进行平滑处理, 所得到的路径相比较未处理之前的路径更为平滑, 在平滑后的路径中不存在尖锐的转角, 这有利于无人驾驶车辆的转向控制, 提高车辆的乘坐舒适性。

通过对比A*算法和改进的A*算法, 采用改进的A*算法对无人驾驶车辆进行路径规划, 其规划路径的转折点数明显减少, 和障碍物的最近距离明显增大, 同时所规划的路径也更为平滑, 但是改进A*算法对路径的规划耗时相对较长, 这是改进算法的不足之处。

图5 改进A*算法采用3次样条插值平滑处理后路径

3 结论

针对传统A*算法在无人驾驶车辆路径规划方面存在所规划路径距离障碍物近、转折点数量多、路径不平滑的问题, 在对传统A*算法分析的基础上提出了改进的A*算法。通过背向障碍物搜索确保规划路径和障碍物的距离, 通过定义评价函数来选择最佳的转折点, 同时通过3次均匀样条函数来对规划的路径进行平滑处理。通过仿真试验表明采用改进A*算法所规划的路径和障碍物保持有一定的安全距离, 同时转折点的数目也有所减少, 规划的路径更加平滑, 但是存在路径长度和规划耗时增加的问题。

[1] 麦明珠. 纯电动汽车动力系统参数匹配及优化研究[J]. 湖南文理学院学报(自然科学版), 2020, 32(3): 25–29.

[2] 彭晓燕, 谢浩, 黄晶. 无人驾驶汽车局部路径规划算法研究[J]. 汽车工程, 2020, 42(1): 1–10.

[3] 刘博, 罗霞, 朱健. 无人驾驶车辆自动避障路径规划仿真研究[J]. 计算机仿真, 2018, 35(2): 105–110.

[4] 胡蔚旻, 靳文舟. 改进平滑A~*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(16): 204–210.

[5] 祁玄玄, 黄家骏, 曹建安. 基于改进A~*算法的无人车路径规划[J]. 计算机应用, 2020, 40(7): 2 021–2 027.

[6] 郭蓬, 吴学易, 戎辉, 等. 基于代价函数的无人驾驶汽车局部路径规划算法[J]. 中国公路学报, 2019, 32(6): 79–85.

[7] 张奋, 黄铁, 周军辉. 空间分析中双向Dijkstra算法优化研究[J]. 湖南文理学院学报(自然科学版), 2007, 19(2): 71–73, 86.

[8] 刘生伟, 马钺, 孟树峰, 等. 改进A*算法的AGV路径规划[J]. 计算机应用, 2019, 39(z2): 41–44.

[9] 乔云侠, 王庆, 阳媛, 等. 基于背向障碍物搜索A~*算法的平滑路径规划[J]. 传感器与微系统, 2020, 39(8): 127–129.

[10] 随博文, 黄志坚. 基于改进A~*算法的水面无人艇路径规划[J]. 舰船科学技术, 2019, 41(23): 162–166.

[11] 董敏, 陈铁桩, 杨浩. 基于改进RRT算法的无人车路径规划仿真研究[J]. 计算机仿真, 2019, 36(11): 96–100.

Research on path planning method of driverless vehicle based on improved A* algorithm

Lin Huangzhi1, Tian Liu2

(1. Mechanical and Electrical Engineering, Anhui Vocational and Technical College, Hefei, Anhui, 230011, China; 2. China Mobile Communications Group Anhui Co Ltd, Hefei 230088, China)

In order to solve the problems of the traditional A* algorithm, such as near distance to obstacles, many turning points and unsmooth path, A* algorithm is improved and applied to the path planning of unmanned vehicles. Based on the analysis of the traditional A* algorithm, the search and evaluation function of back obstacles is improved, and the cubic spline interpolation method is used to smooth the path after planning. The traditional A* algorithm and the improved A* algorithm are applied to the unmanned vehicle model built in MATLAB environment for path planning simulation analysis. The results show that the path planned by the improved A* algorithm is far away from the obstacles, the number of turning points is significantly reduced, and the path is smoother.

Improved A* algorithm; Path planning; Driverless vehicle

U 461

A

1672–6146(2021)02–0017–04

10.3969/j.issn.1672–6146.2021.02.004

林黄智, highgecho@foxmail.com。

2020–09–14

(责任编校: 张红)