基于优化算法的移动机器人全局路径规划

何佳泽 张寿明

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

移动机器人同步定位与建图（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个节点的代价函数值。 每一个栅格的长、宽都为10，根据对角线计算方法可知，栅格对角线距离为，近似为14；G（n）的值为起点到某一个栅格的最短距离［6，7］。笔者采用曼哈顿距离展开计算求得H（n）：

其中10为栅格的宽度。

求出起点周围8个相邻节点的代价函数值F（n），并且方向是朝着终点，（3，3）节点的代价函数值最小［8］，所以全局路径规划到（3，3），并且以此点为中心点， 计算周围8个相邻节点的代价函数值，选取下一个规划路径点，直到到达目标位置点为止［9］，如图2所示。

图2 A*算法代价函数规划路径

图2中，起点到第2个节点最小代价函数值为54，然后是48，再到终点是42，由此得到一条最优全局路径规划。

1.2 A*算法的优缺点

A*算法由于原理简单，在实际生产中得到了广泛的应用， 但是它的缺点也同样非常明显，如果地图比较大的话，它将会遍历很多点，计算量特别大，并且每一个点的计算量也非常大，所以对系统的运算能力要求较高［10］。 为了弥补这两方面的不足，笔者使用JPS算法与GBNN模型结合的方法来克服这两个方面的缺点。

2 跳点搜索法

为减少中间无效节点和一些效果比较差的节点，笔者采用跳点搜索规则对每个节点周围的可拓展节点进行筛选，跳过不需要拓展的节点［11］。 这样就可以减少大量的节点运算，提高整体性能，进而提高搜索效率［12］。

水平方向和对角线方向的筛选规则如图3、4所示。

图3 水平方向筛选规则

图3、4中灰色点代表不适合经过X节点建立全局路径规划的点， 白色点代表适合经过X节点建立全局路径规划的点。 图3中路径从X22节点朝着X点向地图的右边运动， 可以直观地看出从X22到Y最短的路线是走直线：X22→X→X42→Y，直接经过X的路径是最短的，如果绕过X，那么将不是最优选择；如果终点Y是节点X51或者X53，那么经过X节点就不是最优路径选择， 此时的规划路径将不经过X节点。 同理在图4中X22节点朝着X方向向Y节点运行， 搜索过程则可以直接跳过X节点。所以笔者根据图3所示的水平方向筛选规则分成a、b两种情况来筛选拓扑点（图4所用对角线方向筛选规则同理）：

图4 对角线方向筛选规则

a. 从X22节点向右侧移动不经过X节点比经过X节点的路径差的情况，如终点为X42或者X52；

b. 从X22节点向右侧移动不经过X节点比经过X节点的路径优的情况，如终点为X51或者X53。

情况a中X节点会加入到点集合中，情况b中X节点就会被去掉，这样就可以去掉无效或者低效节点，减少节点处理量。

在没有障碍物节点的环境中， 沿着X、Y方向的节点筛选规则为：

其中，m代表X可以拓展的相邻节点，len（）代表路径行进长度；（X22，…，m|X）代表不通过X而直接到m的最短路径；（X22，X，m）代表X节点到达m的最优路径。

同理，可以得到在没有障碍物节点的环境中对角线方向的筛选规则：

3 A＊算法与GBNN模型优化

3.1 GBNN模型

GBNN模型是一种离散的生物启发神经网络，它不需要机器学习和深度学习。GBNN模型是三维立体神经网络，主要用在水下机器人的路径规划中。 笔者通过简化，构建了如图5所示的二维神经网络［13］，与二维栅格地图一一对应。

图5 简化的二维GBNN模型

该算法的主体思想是不断向四周传递激励，障碍物对发散出的激励有抑制作用，通过迭代算法计算出每个位置的活性数值。 该算法有记忆特性，地图上的每一个点都可以通过不断迭代到达激励的发出点，这个激励的发出点也就是路径规划中的终点［14］。

GBNN数学模型如下：

其中，Wij是两个神经元i、j之间的连接权值，xi是i神经元的活性输出值，Ii是i神经元的外部激励值，ωij是i、j两个神经元之间的连接系数，函数g是模型变换函数，γ、r为常数，根据情况设置。笔者采用的是二维栅格地图，所以式（7）使用的是GBNN二维模型的欧拉公式，xix、xiy分别表示第i个神经元的x、y坐标值，通过式（7）即可求出i、j神经元之间的距离。

3.2 A*算法与GBNN模型结合

GBNN的二维神经网络结构可以与路径规划中的栅格地图一一对应起来，每一个神经元和一个平面二维栅格对应，它依据二维栅格地图中各个栅格的状态来决定神经元的外部输入。 通过直接计算神经元的活性值来规划路径，这样就可以避免大量代价函数计算， 减少节点之间的运算量。 GBNN模型不需要神经网络学习， 不需要训练，可以满足路径规划对实时性的要求。

4 实验仿真

笔者提出在A*算法的基础上使用跳点搜索，这样去掉不需要的低效和无效节点，然后在此基础上加入GBNN模型。 模型构建以后，通过MATLAB仿真方法比较算法优化前后的效果。

实验配置如下：

硬件 CPU i7-8750H

内存 16GB

软件 MATLAB2016a

首先建立50×50的栅格地图， 规定起点和终点的位置，随机生成障碍物坐标，通过比较算法优化前后的路径规划时间、路径遍寻节点数量和全局规划路径长度这3个指标来比较。

图6为优化算法流程。

图6 优化算法流程

图7、8分别显示了50×50的二维栅格地图未使用和使用笔者所提算法的规划路径，图中绿色圈为起点，蓝色圈为终点，规划路径为蓝色曲线。图9、10分别对应图7、8的运行时间、遍历节点数和路径总长度。

图7 未使用优化算法规划路径

图8 使用优化算法规划路径

图9 未使用优化算法路径规划数据

图10 使用优化算法路径规划数据

因为算法具有随机性，为了使结果更具真实性，所以通过多次仿真实验，比较算法优化前后的路径规划时间、路径遍寻节点数量和全局规划路径长度的平均值，详见表1。

表1 算法优化前后性能对比

通过表1可以看出优化后的算法对二维栅格地图全局路径规划效果较好。

5 结束语

对传统的A*算法进行优化， 加入JPS 和GBNN，将3种算法进行结合。 采用路径规划时间、路径遍寻节点数量和全局规划路径长度这3个指标对算法的优劣性进行对比， 可以看出使用3种算法结合后的优化算法效果较好。