沈刚 邵金菊 谭德荣 牛亚明 马晓田
摘 要：针对智能车使用A*路径规划算法存在转折点和冗余点的问题，提出一种考虑智能车静态特性的改进A*路径规划算法。在已知静态环境信息的栅格地图上，考虑到智能车自身存在实际宽度，对障碍物进行膨胀扩展;其次根据路径上前后节点相对方向的改变提取必要的转折点，并依次连结前后转折点，若转折点连线不经过障碍物，删除连结转折点之间冗余的转折点;重复上述操作，直至所有冗余点被删除，保留关键转折点。仿真结果表明，该方法可以实现车辆安全无碰撞地到达目标终点。关键词：路径规划;A*算法;障碍物膨胀;轨迹平滑中图分类号：V323.19 文献标识码：B 文章编号：1671-7988（2020）02-28-03
Abstract： In order to solve the problem of turning points and redundant points in using A* path planning algorithm for intelligent vehicles， an improved A* path planning algorithm considering the static characteristic of intelligent vehicles is proposed. On the grid map with known static environmental information， considering the actual width of the intelligent vehicle itself， the obstacles are expanded. Secondly， the necessary turning points are extracted according to the change of the relative direction of the front and rear nodes on the path， and the front and rear turning points are connected in turn. If the turning points are connected without passing through the obstacles， the redundant turning points between the turning points are deleted. Repeat the above operations until all redundant points are deleted and key turning points are reserved. The simulation results show that the method can ensure the vehicle to reach the destination safely without collision.Keywords： Path Planning; A* Algorithm; Obstacles Expansion; Track SmoothingCLC NO.： V323.19 document Code： B Article ID： 1671-7988（2020）02-28-03
前言
近年来，智能车越来越成为国内外学者和各大汽车厂商研究的热点和重点。导航是智能车非常重要的功能模块，路径规划技术作为导航的基础和关键[1，2]，直接影响着智能车行进中的安全避障性和快速通过性。早期的路径规划技术主要针对移动机器人进行主要研究，最常见的路径规划算法主要分为两类，一类是基于节点搜索的以A*算法和Dijkstra算法为代表的传统路径规划算法[3，4]，一类是基于遗传式的以蚁群算法和粒子群算法为代表的智能路径规划算法[5，6]。在全局静态路径规划领域，传统的A*算法具有计算量小、搜索精度高等优点，将移动机器人作为质点完成路径规划，却无法满足智能车在实际导航中的综合需求，存在忽略智能车自身静态特性与动态特性的问题。为了解决传统算法不适用于智能车路径规划的问题，本文在已有研究的基础上提出一种考虑智能车静态特性的改进A*算法。
1 A*算法介绍
A*算法是一种标准的静态全局路径寻优算法，其关键在于评价函数的选取[7]。通过对环境地图中初始位置到目标位置进行代价估计，对比选择最优的搜索方向，直至搜寻到目标位置，从而回溯到起始位置形成最终的全局最优路径。其估价函数可以表示为：
式中f（n）为初始节点到目标节点的代价估计函数，g（n）為状态空间中从初始节点到当前节点n的实际代价，h（n）为从当前节点n到目标节点路径最优的代价估计。若启发式函数h（n）为0时，估价函数则完全由实际代价函数g（n）来决定，类似于广度优先搜索算法。相反若不考虑实际代价，即当g（n）为0时，估计代价决定整个规划路径代价，此时类似于深度优先搜索算法。因此A*算法也可以称为是优化版的盲目搜索算法，结合了广度优先搜索算法和深度优先搜索算法各自的优点。A*算法执行步骤如下流程图所示：
A*算法中估价函数的选取对最优路径的选择至关重要，如果估计函数选取不当会造成路径搜索非最优且效率低下。只有估计代价值和实际代价值接近时，估价函数的选取才更准确高效，基于这些选择两点间的曼哈顿距离作为函数估计值。
2 改进A*算法
2.1 障碍物膨胀
A*算法规划的最优路径能够确保智能车沿着路径快速、准确地到达目标终点。但是传统路径规划算法以移动机器人作为运动目标，这种情况下移动机器人本身作为质点，不会考虑运动对象的静态特征，忽略了运动对象的长、宽、高等外部特征，在这种情况下运动对象与障碍物任何时刻都没有碰撞风险，如图2所示。
智能车作为特殊的运动体，它所处的行驶环境十分复杂多变，行驶路径周围必然存在很多固定的障碍物。如果通过算法规划出的路径紧贴障碍物，那么当智能车沿着路经到达障碍物拐角处，由于智能车自身存在不可忽略的长度与宽度，会导致智能车与障碍物发生碰撞，如图3所示。
针对上述问题，本文将静态地图中的障碍物进行膨胀处理。考虑到智能车与移动机器人的差异性，智能车自身存在相对于路径与障碍物不可忽略的长度和宽度，由于一般车辆的长度在4.7米左右，宽度在1.8米左右，因此将障碍物膨胀半径设定为智能车宽度的一半左右，同时为提高安全性设定为1米，这样智能车在道路行进过程中规划出的路径与障碍物的最小距离大于车辆宽度的一半，可以确保可通行路段宽度至少大于车辆的宽度，使车辆安全无碰撞地通过。
2.2 轨迹平滑
A*算法是按照分层遍历的方法规划最优路径，不可避免的会导致规划路径中包含很多冗余的转折点，对于智能车在实际道路行驶中后续的局部路径规划十分不利，增加计算量。基于此问题本文首先选择提取转折点。在规划的路径中，从起始点开始，根据坐标判断第二个节点相对于起点的方向，然后向该方向延伸，直到路径上的节点开始转向，偏离初始方向。此时保留转折点和起点，删除中间的冗余点。例如，若起点的坐标为（2，2），第二个节点的坐标为（2，5），则可以判断第二个节点以后的节点横坐标即可，直到该节点的横坐标不是2为止，将其前一个节点作为转折点。继续重复上述步骤，从新的转折点开始寻找下一个转折点，直到路径结束。
由于提取出所有的转折点后仍然存在多余的转折点，这些转折点周围有可能不存在实际的障碍物，因此有必要剔除它们。假设提取转折点后的路径点为，连接P1P3，若P1P3不经过障碍物，则说明它们之间的P2为多余的转折节点，可以删除后继续连接P1P4;若连接P1P3经过障碍物则继续连接P2P4，重复上述步骤，直到删除所有冗余点，保留路径上的关键转折点。
3 仿真实验与结果分析
为了验证改进A*路径规划算法的有效性，本文选择在基于MATLAB r2016a的20×20的平面栅格地图上进行仿真实验。智能车的宽度设定为1.5m，实验起点设为（1.5，2），终点设为（18，19），共计进行四组实验。如图3所示。第一组实验为通过标准A*算法所得的最优路径，从图中可以发现该
路径基本可以实现智能车以较短的距离从起点行驶到终点;第二组实验为障碍物经过膨胀处理后的路径规划，从图中可以发现规划出的路径与障碍物保持基本的安全距离，可以确保智能车通过障碍物拐角时不发生碰撞;第三组和第四组实验分别是提取关键转折点和剔除冗余转折点后平滑轨迹所得到的最优路径，比较分析可以发现在路径平滑处理之后智能车的规划路径更加平顺，可以确保智能车快速平稳通过。
仿真实验结果显示，改进A*算法能够规划出智能车全局最优路径，且行驶距离最短，行驶路径最为平顺，符合智能车行驶过程中的快速到达要求与安全避障要求。
4 结论
本文针对现有A*算法全局路径规划的不足提出了一种考虑智能车静态特性的优化A*算法进行路径规划。首先在原有已知静态栅格地图中将障碍物进行膨胀处理使车辆在实际行驶时与障碍物保持安全距离避免碰撞，在此基础上针对规划路径存在较多冗余转折点的问题进行关键转折点选取和冗余点剔除处理，确保智能车路径规划更加平稳、高效。仿真结果表明优化A*算法在智能车全局路径规划中效果显著，对于车辆智能导航与安全避障方面具有重要的作用。
参考文献
[1] 龙卓群，吴超，雷日兴.移动机器人躲避多静态障碍物路径智能规划方法[J].自动化与仪器仪表，2018（10）：178-181+184.
[2] 龙卓群，雷日兴.移动机器人全覆盖路径规划算法研究[J].自动化与仪器仪表，2018（09）：15-17.
[3] 赵晓，王铮，黄程侃等.基于改进A*算法的移动机器人路径规划[J].机器人，2018，40（06）：903-910.
[4] 张希闻，肖本贤.改进D～*算法的移動机器人路径规划[J].传感器与微系统，2018，37（12）：52-54+58.
[5] 孙海洋，夏庆锋，杨冠男等.基于改进蚁群算法的机器人路径规划方案研究[J].软件导刊，2018，17（09）：22-24.
[6] 王慧，王光宇，潘德文.基于改进粒子群算法的移动机器人路径规划[J].传感器与微系统，2017，36（05）：77-79.
[7] 吴麒麟，杨俊辉，汪若尘等.基于混合SA算法的智能汽车全局路径规划[J].江苏大学学报（自然科学版），2019，40（03）：249-254.
