基于节点优化的A＊算法路径规划

蔡 诚，梁利东，贾文友，江 磊

（安徽工程大学 机械工程学院，安徽 芜湖 241000）

路径规划技术是机器人研究领域中的一个重要分支。路径规划问题即是按照某种优化指标（如时间、距离、能量等）规划出一条从给定起始点到给定目标点且与所在环境中的障碍物无碰撞的最优或次最优路径[1]。根据对环境信息的掌握程度，路径规划技术包括环境已知的全局路径规划和环境未知的局部路径规划[2]。

A*算法在路径规划中的应用较为成熟和广泛，但随着地图面积的增大其搜索空间将会产生多余的搜索节点，导致算法效率降低、规划路径出现不必要的转折等问题[3]。针对这些问题，众多学者从不同的角度提高和改进了A*算法的搜索效率。本文基于节点优化策略提出了一种改进的A*算法，通过对搜索过程进行优化，减少计算量和耗时，并通过关键点选取方法，消除路径中的冗余点，使路径更加平滑。

1 路径规划环境建模

环境建模的目的是为路径规划提供可用的数据分析平台，常用的建模方法主要有栅格地图法[4]、几何特征地图法[5]和Voronoi 图法[6]。栅格法应用最为广泛，它将搜索环境分成网格单元，且这些网格单元具有二值信息，栅格的大小决定着环境信息存储量的大小以及路径规划时间的长短，所有节点可分为障碍物节点和自由节点两大类，每个自由节点连接相邻的自由节点组成一个图，用搜索算法生成从初始节点到目标节点的路径。由于栅格法地图的创建和维护比较容易，每个栅格的信息直接与环境中某区域对应，通过地图很容易进行路径规划，且易于扩展到三维环境[7]。因此本文选择栅格法进行环境建模，将移动机器人的起点和目标点均看成质点并将环境中任意形状的障碍物用矩形代替，障碍物的矩形包络如图1所示。

图1 障碍物的矩形包络模型

2 A*算法思想

A*算法是一种静态环境下最优的搜索算法，由于其高效性，一经提出便被大量地应用在路径规划研究中，其核心表达式为

其中，n表示当前被搜索节点；f(n)表示从起点经过当前节点到目标节点的估计成本；g(n)表示起点到当前节点实际成本；h(n)为启发函数，表示当前节点到目标节点的估计成本。

A*算法通过函数f(n)搜寻每一步代价最小的节点从而找到代价最小的路径，一般需要构造两个表：open list 和close list。open list 作用是保存搜索过程中遇到的扩展节点，同时将这些节点按代价的大小进行排序。close list 作用是保存open list 表中代价最小的可扩展节点。主要算法流程为：在二维空间中，以起点为初始，把起点s 放入到open list 中，close list 为空，遍历open list，查找f(n)值最小的节点，把它作为当前要处理的节点并把这个节点移到close list，对其相邻的8 方向单位栅格中的每一个节点分别计算f(n)值。选取子节点中f(n)值中最小的点作为下一个位置，在close list中加入此节点，并将该节点作为新的当前节点（父节点）。重复以上步骤，直至找到终点。其中close list 中按照先后顺序添加的节点所组成的路径就是A*算法所规划的路径。

尽管A*算法已经成为移动机器人导航中广泛使用的路径规划算法，如何解决算法规划路径中拐点多、转折次数多的问题是本文的研究重点。

3 基于节点优化的A*算法

3.1 优化搜索过程

改进A*算法搜索程序结构如图2 所示。

图2 改进A*算法搜索过程优化程序框图

close list 中保存获取的从起始节点开始的路径节点，open list 仅保存当前扩展节点的后续节点，不保存其他已扩展节点的后续节点。改进算法的估价函数为：f(pi)=g(pi)+h(pi)，g(pi)表示从起始节点到节点pi的路径长度；h(pi)为启发函数，使用欧几里得距离，表示从节点pi到目标点之间的直线距离，节点pi距离终点越近，f(pi)越小，以此引导搜索的方向，使得逐步靠近目标点。

算法程序思路用如下文字方式描述：首先设置各项参数，创建open list 和close list，把起点加入到close list，若目标点不在close list 中，则清空open list，从close list 中选取节点进行扩展，将扩展节点的后续节点加入open list。计算open list 中所有节点的f(pi)，选取f(pi)最小的节点，将其加入到close list，并修改插入节点的路径长度；若目标点在open list 中，则直接将其添加到close list，省去计算估价值和比较估价值的步骤，节省路径规划时间。扩展open list 时，遍历V中几何点构造的所有节点，若节点pi不在close list 中且与close list 的扩展节点可视（之间没有障碍物），则将其作为一个后续节点。

改进算法与A*算法的主要区别是open list 仅保存当前扩展节点的后续节点，不保存已扩展节点的其他后续节点，这大大减少了open list 保存的节点数量，减少了计算量和时耗。

3.2 优化搜索路径

close list 中保存的是一条从起点到终点的无碰路径，受启发函数的限制，路径中的某些节点和折点在存储路径的时候是多余的，冗余节点造成存储的浪费，而冗余转折点会导致机器人在行走过程中不必要转弯，不利于机器人的控制。针对这个问题，提出一种搜索路径关键节点选取策略，原理如下：

（1）设x1、x2、x3为不在同一直线上的三个点，若x1-x2连线、x1-x3连线都不与障碍物发生碰撞，则删除点x2，保存x1、x3；若x1-x2连线不与障碍物发生碰撞，x1-x3连线与障碍物发生碰撞，则保存x1、x2、x3，以x2为下一起点依次向下选取两点继续构造三角形。

（2）若选取后的x3、x4和x2为在同一直线上的三个点且x2-x3连线、x3-x4连线均不与障碍物发生碰撞，则删除点x3，保存x2、x4；更新路径，重复上述操作直至目标点。

路径节点筛选如图3 所示，具体步骤如下：

图3 路径节点筛选示意图

第1 步，以1 为起点，连接1-2、1-3、2-3，均未与障碍物发生碰撞，删除点2，保存点1、点3。

第2 步，同理，连接1-4、1-5、3-4、4-5，均未与障碍物发生碰撞，删除点3、点4，保存点1、点5。

第3 步，连接1-5、5-6，未与障碍物发生碰撞，连接1-6，发生碰撞，保存点1、点5、点6。

第4 步，以5 为起点向下依次选取两点，点5点6 点7 在同一直线且5-6、6-7 均不与障碍物发生碰撞，删除点6，保存点5、点7。

第5 步，更新路径，重复上述步骤直至目标点8。

筛选后的路径如图4 所示。

图4 路径节点筛选后

4 仿真结果

为了验证本文算法的优越性，设计仿真实验来进行验证，构建20*20 的栅格地图，可以自由设置起点和终点及障碍物分布，仿真功能就是实现从起点至终点寻找一条最优路径。实验分别采用A*算法和改进A*算法进行路径规划，路径仿真结果如图5 和图6 所示。

图5 A*算法轨迹规划

图6 改进A*算法路径规划

分析对比实验结果可知：在机器人起始位置和障碍物位置相同的情况下，改进后的算法路径总长度缩短，节点和转折点数量降低，有效提高了路径平滑度，更加适合移动机器人的运动特性。表1 是以路径长度、搜索节点数、转向次数以及所需规划时间等作为评价指标对两种算法的详细参数对比情况。

表1 实验路径参数表

从表1 可知，本文算法的路径搜索性能有了一定提升：在路径长度上减少了38.79%，搜索节点数减少了77.27%，转向次数降低了50%，规划时间减少了32.23%。可见该算法更高效地搜索到最优路径，减少了搜索节点数，降低了路径成本，使得路径更加平滑。

5 结论

本文通过改进A*算法，对搜索过程优化，减少计算量和耗时，并通过关键点选取方法，剔除冗余节点和转折点，使搜索到的路径更加平滑。仿真结果表明，改进后的A*算法比原A*算法所规划出的路径长度减少了，拐点和转弯次数也都减少了，节省了机器人路径规划的时间，缩短了路径长度并提高了路径的平滑性，从而提高了机器人的路径规划的效率，更加适用于机器人的路径规划。