何佳泽 张寿明

（昆明理工大学信息工程与自动化学院）

移动机器人同步定位与建图（SLAM）中，需要规划一条从起始点到终点的路径，这个过程就被定义为全局路径规划［1，2］。传统的A*算法是一种启发式搜索算法， 它将整个地图分成很多个节点，以评估节点的代价函数值来作为节点的综合优先级［3］，通过遍历周边的节点，选取最高优先级的节点， 逐渐找到一条从起点到终点的最优路径。 传统A*算法在二维栅格地图中的路径规划效果比较好， 它能快速找到代价最小的函数值，从而得到线路最短的路径。 但是，因为它需要遍历周边节点， 所以在尺寸较小的地图中比较实用。随着地图尺寸的不断扩大，它将会搜索大量的无用节点，使得搜索的节点数量以指数级增长［4］。

为了使A*算法在尺寸较大的地图中也能使用，笔者提出将它与启发神经网络（GBNN）模型结合，并使用跳点搜索（JPS）算法跳过下一个无用节点，减少整体计算量，从而提高算法的性能。

1 算法原理

1.1 A*算法栅格地图全局路径规划

A*算法采用代价函数，通过不断寻找周围的节点，分析其代价规划出一条最优路径［5］，代价函数模型如下：

式中 F（n）——从起始状态经由状态n到目标状态的代价；

G（n）——在状态空间从起始状态到状态n的实际代价；

H（n）——从状态n到目标状态规划的最佳路径的代价。

A*算法是一种二维栅格地图， 首先建立A*代价函数栅格地图（图1）。

图1 A*代价函数栅格地图

图1建立的是5×5的栅格地图，A*算法的基本原理是从起点开始遍历周边8个节点的代价函数值。……