针对不规则机器人路径规划改进的A*算法

焦莉莉 王凤娇 张苏林 靳志刚

摘要：对复杂环境下移动机器人全局路径规划问题进行研究，提出一种针对不规则机器人路径规划改进的A*路径规划算法。首先，对全局运动空间进行建图录制;然后，将全局地图根据碰撞空间进行地图预处理，运用改进的A*算法规划一条从起点到终点的全局路径;最后在vs平台将A*路径规划算法与改进的A*路径规划算法进行对比实验。实验结果表明：文中方法较全局路径规划A*算法任务的效率明显提升。

关键词：移动机器人;全局路径规划;A*算法

中图分类号：TP3            文献标识码：A

文章编号：1009-3044（2021）27-0098-03

在科学技术快速发展的今天，机器人在日常生活中得到广泛的应用，其中路径规划是机器人技术的一个重要组成部分。机器人的路径规划指在特定的工作环境中，不断查询障碍物信息从而找出一条从起始点到目标终点的可通行路径。路径规划算法是实现机器人自主移动的关键前提。近年来路径规划的算法研究也被国内外学者所热衷。

目前路径规划算法主要有以下几种：基于图搜索的路径规划算法，如A*、D*、人工势场法、栅格图法等;基于智能仿生学的路径规划算法，如遗传算法、蚁群算法等;基于图搜索算法，虽然能够收敛到路径最优，但随着空间纬度的增加会导致算法的复杂化;对于智能仿生学算法在进行路径搜索时可能会陷入局部最小值。为了更好地解决上述路径规划算法局限，有关学者提出一种基于采样的路径规划算法，主要包括概率路标算法[1]（PRM）和快速拓展随机树算法[2]（RRT）。

1 A*算法基本概念

A*算法的基本思想是从起点开始根据评价函数不断向目标终点的方向进行搜索，通过数据容器记录每次搜索确定的点，最后搜索到目标点，从而获得最小代价的全局路径。A*算法定义，移动机器人基于在当前栅格寻路时，通常选择八邻域法，即有8个邻域可作为下一步运动方向，分别为正前、正后、正左、正右、左前、左后、右前、右后。

A*算法目的在于获得最小的代价路径，其中评价函数为f（ n） = g（ n） + h（ n）。评价函数中f（n）的物理意义为当前点的评价函数， g（ n） 的物理意义为过去代价函数，用于评价起始点到当前节点的代价，h（ n） 的物理意义为当前成本函数，用于评价当前节点到目标节点的代价。g（n）通常用固定的数值表示，但h（n）通常不是固定的，h（n）的表达式选择会影响到f（n）最小代价函数的合理性。基于以上的设计，启发函数h（n）设计为A*算法的关键要素。合理的启发函数设计能提高寻路效率。启发函数常见四种表达式，其中最常用的是曼哈顿距离。

曼哈顿距离指代x坐标方向距离与y坐标方向距离之和，启发函数表示：h（n）=D*[abs（xb-xn）+abs（yb-yn）]，（xb，yb）为目标节点坐标，（xn，yn）为当前结点坐标，其中D表示h（n）启发函数的代价系数，针对不同地图环境，通常选用不同的代价系数，本方案选择10为代价系数。例如文献[3]根据当前结点和目标结点的距离不同，尝试了不同的代价系数D，从而实现障碍物环境地图不变时降低搜索时间。

2改进的A*算法

文献[4]提出了一种融合改进A*算法和动态窗口法的全局动态路径规划方法。但是A *算法的效率仍然比较低，如果地图中存在比较多的U 型和 L 型等特殊障碍物时，A *算法仍然需要访问大量无效地图空间。因此，在路径规划的实际应用中，当地图环境机器人通道空间比较宽阔时常常把地图障碍物按照机器人半径膨胀处理后再調用A*寻路算法。这样可以减少A*算法的搜索时间。

但我们所研究的项目中机器人为车型机器人，地图环境中机器人的通道空间比较狭窄，将车型机器人按照车型机器人半径进行障碍物膨胀处理时会导致狭窄区域没有路径。

针对这一问题增加不规则机器人的障碍物碰撞逻辑。A*算法的搜索实质上是对当前栅格相邻的栅格正前、正后、正左、正右、左前、左后、右前、右后进行碰撞预判，如果相邻栅格超出地图边界、相邻栅格为障碍物区域或者相邻栅格之前搜索过即相邻栅格在关闭列表中，则添加该相邻栅格进关闭列表，其他情况则将相邻栅格添加进开启列表。增加不规则机器人的障碍物碰撞逻辑就在这一步添加，在加入开启列表或关闭列表前，额外再加一个条件（以邻接栅格为中心，以目标车的方向和大小构建下一步车的位置，判断下一步该车是否会覆盖到不可走状态的栅格——即与障碍物不能碰撞），若满足此额外条件，相邻接栅格加入开启列表，否则添加该相邻栅格进关闭列表。

在增加的不规则机器人的障碍物碰撞逻辑中，目标车边界栅格在左前、左后、右前、右后已经不是一行或者一列，而是倾斜的，但是注意到左前、左后、右前、右后四个方向栅格倾斜的角度为45的奇数倍，依次将左前、左后、右前、右后四个方向用两个循环来判断长和宽边界;利用计算几何的思路计算此时虚线矩形的四个边角点a1、a2、a3和a4，每一个边角点由车形机器人的几何中心以一定的角度向外延伸一定的半径计算得来。注意，代码中对于目标车越界情况进行处理-即目标车虚线矩形边界覆盖到了栅格地图的外面，判定此时目标车几何中心所在栅格的相邻栅格进入关闭列表。

通过实际项目测试，可满足车型机器人狭窄区域路径规划要求。

3针对不规则机器人路径规划的预处理算法

上述A*算法，增加了条件2的约束增加了算法的复杂性，延长了算法计算周期。在实际项目中增加条件2的地图预处理功能。即将条件2作为地图栅格化的一个已知元素。在实时A*路径规划中降低了算法的计算周期。

本算法验证通过Windows操作系统的VisualStudio2010开发平台。算法主要分为3个功能模块，地图构建模块、地图预处理模块和主程序模块。