改进A*算法的机器人最短路径规划研究∗

陈 晨

（南京理工大学 南京 210094）

1 引言

移动机器人如今在各行各业都扮演着一定的角色［1～3］，而路径规划作为机器人完成导航以及其他任务的前提，在机器人领域中有着重要的地位。路径规划的目的是在有障碍物的环境中为移动机器人从起始位置到目标位置规划出一条最优并且安全无碰撞的路线，是自主移动机器人的基础［4］。对机器人路径规划的研究非常之多，常用方法主要有蚁群算［5］、粒子群优化算法［6］、栅格法［7］、神经网络算法［8］等。在移动机器人的路径规划中，最为常用也最为简单的栅格法沿用至今，其原理简单（0，1分别代表可通行区域和障碍物），对移动机器人的传感器要求也不高。A*算法用栅格图作为路径规划的基图，在上面进行路径的搜索。针对这种方式，文献［9］对传统A*算法中延申结点的等级进行了赋值，实现路径远离障碍物，避免了实际中移动机器人会碰撞到障碍物边缘的问题；文献［10］虽然解决了实际移动机器人行驶中路径的平滑性能，但是因为其改进的原理是将搜索当前节点的8 个方向改成无限个方向，无疑大幅增加了计算的难度，使得搜索的时间变长。文献［11］通过虚拟障碍物的设置，在障碍物的周边设置虚拟障碍，即障碍物边缘膨胀化处理，避免规划的路径太过靠近障碍物而发生碰撞。文献［12］通过修改搜索策略，采用JPS 跳点搜索策略，根据一定的规则从栅格中选择一些点进行扩展，极大地提高了效率，文献［13］为了提高路径的平滑度和降低搜索的时间，将现实世界里的元素信息加入到启发函数中，文献［14］为了提升传统A*算法的速率，用确定的方向搜索减少搜索区域。文献［15］提出了基于A*算法的跳点搜索策略，通过省略中间直线部分的搜索点，从而减少了算法的计算量，文献［16］采用的方式是将原先冗余的两条相邻边，使用与它们相近的共有边来代替，一定程度上将趋于目标点的要求进行了简单化，但有一个缺陷是当环境变得复杂且节点交错时搜索的效率提升不大。

基于以上各方法的特点，本文通过对启发函数加入当前节点父节点的信息，并用欧式距离和曼哈顿距离的中值来代替原先的启发函数，提高了启发函数h（n）的值，使之更加接近真实的路径代价，效率更高，速度更快。

2 A*理论基础

2.1 环境建模

环境模型的建立是进行机器人控制的基础，合理的地图模型可以提高规划的效率，其中无约束栅格为图中白色网格，带约束栅格为图中黑色网格，每个栅格都代表着整个实验场景中的其中一部分，他们共同组成了实验的现实环境地图。如图1所示。

图1 栅格地图

2.2 算法流程

A*算法是一种经典的启发式搜索算法，其搜索方向主要有两种，如图2所示。

图2 栅格地图及机器人移动方向

A*算法的核心表达式为

式中f（n）表示从初始栅格经过节点n 到达目标栅格的总的代价消耗，g（n）表示从初始栅格到节点n 所在栅格的实际代价消耗，h（n）表示从节点n到目标栅格的估计代价消耗，其中f（n）的大小几乎取决于h（n）的大小。因此分析A*算法的关键在于对启发函数h（n）的研究。当预估的代价h（n）小于真实的路径代价，搜索的范围会比较广，得到的路径也比较短，相应带来的问题就是耗时较长，当预估的代价h（n）大于真实的路径代价，搜索的速度会比较快，相应的问题是路径可能不是最短的，h（n）越接近真实的路径代价，算法的速度和效果越好。因此，在复杂、规模较大的环境中我们更要对启发函数进行一个改进，在提高速度的同时也能得到更短的路径。

A*全局路径规划流程如图3所示。

图3 A*算法流程图

3 改进的A*算法

3.1 启发函数的修改

由第一部分的计算公式可得，预估的代价损耗h（n）极大程度地影响着整体的预估代价，实验表明，算法的效率高低取决于h（n）的大小与实际损耗代价的差值，h（n）越接近真实损耗，算法的效率越高，一般的代价方式有曼哈顿距离（式（2）），欧式距离（式（3））和切比雪夫距离（式（4））3 种。而实际中，曼哈顿距离相对于实际距离偏大，欧式距离相对于实际距离偏小。

其中栅格n 的坐标为（nx，ny），目标栅格的坐标为（goalx，goaly）。

如图4所示，点G为目标点，点N为目前所处的点，可以看出，欧式距离是两点的直线距离，由于移动机器人在规划时肯定会遇到各种各样的障碍物，所以实际消耗的代价肯定要比欧式距离要大很多，曼哈顿距离为两条直角边的和，在绝大多数的移动机器人场景中这个距离是大于实际行走路线的距离，所以可以取曼哈顿和欧式距离的中值作为启发函数

图4 欧式距离和曼哈顿距离

h（n）的估计值。根据以上所述，定义新的启发函数：

3.2 增加父节点信息

A*算法按照传统的启发函数h（n）进行路径搜索时，会不断的往返搜索，导致搜索的节点过多，增加了计算节点的数量，降低了效率。本文加入当前节点父节点的信息，主要是把当前节点到起点的代价，当前节点到目标点的预估代价以及当前节点父节点到目标点的预估代价这三者这和作为衡量当前节点是否为目前最佳路径上的节点的量度，该想法的表达式（6）：

式中h（p）是当前节点的父节点到目标点的预估距离。改进的启发函数使得A*算法的搜索方向在实际搜索中更有目的性地接近终点，减少了算法的遍历点数量，提高了算法的速度。当然，并不是加入越多的评估点算法效率就越高，随着评估点的增多，该算法的存储容量就会越大，影响算法的性能。故只增加了当前节点父节点的信息来提高算法速度。当然，在后面的仿真实验中，也验证了本文提出的的这个改进的合理性。

4 仿真结果及分析

此次实验的环境和编译工具分别为Intel 的Windows 和Matlab 仿真软件。改进过后的A*算法与传统算法分别进行了多次实验，取其中经典的差异进行展示，展示的栅格地图尺寸选取的为100×100，地图中黑色的方块均为障碍物，灰色部分为路径规划时拓展的节点，白色的线代表着规划出来的路径。仿真结果如图5所示。

图5 A*和改进A*算法搜索效果对比图

从图5（a）可以看出传统的A*算法扩展的节点过多，由此带来占用内存过大，计算时间过长等问题，导致移动机器人的规划时间较长，没有很好的实时性。改进过后的A*算法图5（b）解决了上述问题，扩展结点大大缩减，规划路径几近等于扩展出来的节点，没有大量的往返之前的节点，计算速度因此大幅提升，移动机器人的行驶效率也因此得到了大幅提升。具体数据对比见表1。

表1 A*算法与改进A*算法数据对比

由表1 可知，本文改进算法在保证得到相似路径的基础上，减少了大量不必要栅格的访问，有效地降低了计算量，减少了计算机资源的消耗，使得移动机器人在实时性方面有了很大的改善。经过多次仿真实验验证，本文算法较传统的A*算法运行时间平均减少了85%，地图规模越大，计算提升时间越大，保证了移动机器人路径规划的实时性。

5 结语

A*算法在路径规划上存在实时性低，内存消耗严重的问题，不能满足机器人在复杂、大规模环境下的实时规划要求。为了解决这一关键性问题，本文对A*算法的启发函数进行了改进，使其更加接近真实的路径代价，同时增加了父节点的信息，提高了启发函数在整个预估函数的比重，避免了大部分不必要节点的探索。仿真结果表明，无论在大规模，还是小规模地图中，改进的A*算法都能大大提升路径搜索的效率。