改进A*算法的移动机器人全局路径规划研究

支琛博，张爱军，杜新阳，彭 鹏

(南京理工大学机械工程学院，江苏 南京 210094)

1 引言

路径规划对移动机器人的导航起到至关重要的作用，已经成为当下控制领域研究热点，其主要是让目标对象在规定范围内的区域内找到一条从起点到终点的无碰撞安全路径[1]。

目前存在多种路径规划算法，如人工势场法、蚁群算法、粒子群算法以及Dijkstra算法[2]等，其中A*算法是一种启发式搜索算法，通过评估节点的代价值搜索目标点，其优点是在实际运用过程中具有良好的鲁棒性，且速度相对其他算法较快，运用较多。

针对传统A*算法在实时性不高、规划路径的安全性得不到保障的情况下，国内外学者从不同层面对其进行了改进与提升。文献[6]提出了一种以双向搜索机制为核心的改进A*算法，其通过把初始点与目标点同时以机器人当前所在点为目标进行搜索，缩短了搜索路径的时间，但是路径的安全性不能有保障；文献[7]将传统搜索扩展节点方法由搜索3*3领域改为搜索7*7领域，虽然在安全方面减少了运动轨迹折线，使得运动轨迹更平滑，但是不能保证机器人的路径轨迹远离障碍物；文献[8]通过引入碰撞威胁因子的方法，在启发式函数上加入与障碍物的距离和安全距离函数，使得安全性有了保障，但是在实时性方面并没有的得到较大的改善；文献[9]通过增设视觉传感器等外设，实现障碍物的识别与定位，但是在实际应用中往往会提高成本，不利于推广。

以上算法都在不同程度上改善了A*算法的性能，使得A*算法得到了较快的发展，但是始终没有一种算法可以较好程度上兼顾实时性与安全性。本文算法在选取扩展节点上融合JPS算法选取跳点的思想，将符合跳点要求的点作为A*算法的扩展节点，从而可以快速搜索节点，提高算法实时性；在融合JPS算法的基础上，引入安全权重方阵思想，选取远离障碍物的跳点，从而在提升实时性的基础上提升安全性。本文最后通过一系列仿真，验证算法的可实施性。

2 改进A*算法

传统A*算法在移动机器人寻找路径时，通过寻找当前节点附近成本代价值最小的节点来实现最优路径搜索。其在大面积地图环境下，随着路径长度的增加，搜索时效性低；在拥挤的地图环境下，规划路径不符合机器人运动学原理，容易造成误碰撞。针对传统A*算法的局限性，本文作出如下改进：

1)优化选取节点过程，提高实时性；

2)结合安全权重方阵，提高安全性。

2.1 A*算法实时性改进

JPS算法[10]也是一种启发式算法，其在移动机器人的路径规划过程中，通过当前节与其父节点，确定路径方向并省去过程中无意义的节点。相较于A*算法，若检测到有意义的节点，会忽略探路过程中所通过的各个步骤，并仅将这个有意义的节点加入Open表中，从而对路径节点进行有针对性的选取，减少有效提升路径搜索的速度。

2.1.1 剪枝规则

在路径搜索过程中，通过只扩展网格地图上的某些节点(跳点)来加快最优搜索，合理选取跳点需要剪枝(省去无意义节点)，其规则如下：

1)节点附近不存在障碍物

若路径搜索方向为斜对角，则记为d1，若方向为直线，则记为d2。若从节点x按照一定方向移动可以到达节点y，则记作下式：

y=x+k1d1+k2d2

(1)

对于当前节点的任意邻节点，若满足以下约束条件，则进行剪枝

(2)

其中len表示路径搜索长度，p(x)表示当前节点的父节点，n表示当前节点的邻节点，a表示节点b不会出现在路径a上。

图1(a)显示了一个示例，父节点为p(x)=1，除n=8外所有x的邻居都被修剪掉；图1(b)显示了一个示例，父节点为p(x)=1，除n=6，n=7和n=8外所有x的邻居都被修剪掉。

图1 当前节点附近没有障碍物示意图

2)节点附近存在障碍物

节点n若存在以下情况下则不能被剪枝：

①n不是当前节点的自然邻居

②

(3)

图2(a)显示了一个示例，父节点为p(x)=1，n=3是障碍物节点，这里n=4的节点不能剪枝；图2当前节点附近有障碍物示意图(b)显示了一个示例，n=2是障碍物节点，这里n=3的节点不能剪枝。

图2 当前节点附近有障碍物示意图

2.1.2 筛选跳点

设初始点为x，并将其添加到Open表中，沿着x的水平和垂直方向进行路径搜索，若遇到不可到达区域，则沿x的对角线移动一个单位距离，对新位置的水平和垂直方向搜索，往复循环此过程，若遇到强迫邻节点，将其作为跳点加入Open表，并利用剪枝规则删除过程中的节点。

2.1.3 算法流程

本文将JPS取点策略应用在A*算法中，根据剪枝规则筛选出跳点，并将其放入Open表中，从而减少了Open表节点数量，提升算法速度。其大体思路如下：

1)将起始点(第一个跳点)加入Open表中；

2)在算法执行前增加一个预处理过程，所谓预处理就是通过寻找当前节点的继承跳点，修剪掉中间无用节点，连接跳点实现两点间的长距离跳跃，并把前一个跳点移除Open表并加入至Close表中；

3)重复执行步骤二，直到到达目标点；

4)对Close表按照时间先后顺序进行路径连线，输出最优路径。

相比于传统A*算法，利用JPS策略改进后的A*算法可以通过连接跳点，实现较长距离的“跳跃”。在寻路的过程中只需要花费很短的时间进行预处理，就可以减少大量不必要的节点，极大地提高了寻路的效率。

本文在地图构建方面采用栅格法，相比于拓扑地图法等其它地图构建方法，栅格法可以有效地提取环境信息，并且在仿真编码中易于实现，传统A*算法与融合JPS的改进A*算法效果如图3与图4所示。

图3 传统A*算法效果图

图4 融合JPS的改进A*算法效果图

2.2 A*算法安全性改进

在传统A*算法中，通常存在图5所示的路径规划情况，然而其忽略了实际应用中机器人的体积，易造成误碰撞。本文通过引入安全权重方阵思想，使得移动机器人可以有效的与障碍物保持安全距离，从而提升算法的安全性。

本文借助多邻域搜索思想，针对不同安全距离的要求，设定相应的邻域矩阵完成对障碍物的检测。因为本文地图环境类型为栅格地图，所以设与障碍物的最小安全距离为一个栅格的距离，相对应的邻域矩阵大小为3*3，也称其为基础比较方阵。以基础比较方阵为例，将方阵中心元素设置为当前路径节点，其值为0，其他位置值设定为1，如式所示。

(4)

在路径搜索的过程，若矩阵范围内检测到障碍物，则把相应位置的元素值由1改为2，生成安全权重方阵，表示此处有障碍物存在。例如对于图5中的路径节点X，其安全权重方阵XB为

(5)

设置d为安全系数，若d越大，路径安全程度越高。若方阵中有2，则设d为5(实际情况可自行选定)，表示当前节点附近存在障碍物，否则为0，具体表达如下

(6)

得到改进A*算法的函数代价式如式所示，其中m为统计基础比较方阵中2的个数，也称障碍物影响因子，其值越大表示当前节点附近的障碍物越多。如图6所示，结合以上算法，因为原路径节点代价值增大，所以重新选取路径节点，使得路径远离障碍物。

f(n)=g(n)+h(n)+md

(7)

图5 传统A*算法安全性改进前效果图

图6 传统A*算法安全性改进后效果图

若要设定其他安全距离，可以在基础比较方阵的基础上进行矩阵变换，通过其与变换矩阵A做式(9)的运算，从而得到中心元素值为0、其余元素值为1的k*k(k为奇数)比较矩阵C。

(8)

(9)

按照式将比较方阵C生成安全权重方阵，完成重新选取路径节点。最终的流程图如图7所示。

图7 A*算法安全性改进流程图

2.3 混合A*算法改进

为有效解决传统A*算法在移动机器人寻找路径时，其在大面积地图环境下，随着路径长度的增加，搜索时效性低，在拥挤的地图环境下，规划路径不符合机器人运动学原理，容易造成误碰撞问题，本文将A*算法与JPS算法结合，采用选取跳点策略选取路径节点，同时结合安全权重方阵思想，使得移动机器人可以有效的与障碍物保持安全距离，从而提升算法的安全性，构建融合JPS与安全权重方阵的改进A*算法。

如图8所示为改进算法流程图，其具体步骤如下：

1)创建栅格地图并初始化参数，选择初始位置S(xStart，yStart)，终点位置G(xGoal，yGoal)，创建节点列表Open与Close表，将初始位置加入Open表中；

2)在算法执行前增加一个预处理过程，所谓预处理就是通过寻找当前节点的继承跳点，修剪掉中间无用跳点，连接跳点实现两点间的长距离跳跃，并把前一个跳点移除Open表中，令其加入到Close表中，记录此刻跳点的路径代价值f(n)；

3)结合安全权重方阵算法，判断此时路径节点是否紧挨障碍物，若紧挨障碍物，则更新f(n)值，重新选取相应跳点，直到达到安全距离要求，将新节点加入Open表中，并把前一个跳点移除Open表中，令其加入到Close表中；

4)重复执行步骤二与步骤三，直到达到目标点；

5)对Close表按照时间先后顺序进行路径连线，输出最优路径，可得到可得出本文全局路径规划的最优路径。

图8 改进算法流程图

3 改进 A* 算法仿真

为了验证本文算法在移动机器人在实际路径规划过程的有效性，本文采用仿真形式，在多组不同栅格地图环境下进行三种算法的仿真，并将结果进行比对。仿真环境的计算机参数为：系统Windows 10，CPUIntel Core i5，内存8GB，编译环境MATLAB 2016b。

在实验过程中，本文分别将传统A*算法(算法1)、融合JPS的改进A*算法(算法2)、融合JPS与安全权重方阵的改进A*算法(算法3)三种方法做仿真，其中对于算法3设定安全距离为一个栅格的距离，从评估节点数量、路径搜索时间、路径长度三个因素来评估算法的有效性，同时在每组对比试验中设定起始点、目标点以及障碍物信息均相同，以此来达到控制变量对比算法效果。

图9、图10与图11分别为算法1、算法2、算法3在地图大小为20*20的栅格地图上的算法效果图，从图中可以明显看出，算法3无论是安全性还是拐点数量相比去前两者都有一定的效果。

图9 传统A*算法效果图 图10 融合JPS的改A*算法效果图

图11 融合JPS与安全权重方阵的改进A*算法效果图

如图12所示，为了验证算法的普适性，本文分别在10*10、50*50以及100*100大小的栅格地图上仿真本文算法，并将其与前两种进行效果比对。

图12 不同大小栅格地图改进算法前后的定型效果对比

表1传统A*算法与本文改进算法的对比是本文算法在改进前后算法效果对比表，分别通过评估节点数量、路径搜索时间、路径长度三个因素来评估算法的有效性。

表1 传统A*算法与本文改进算法的对比

将表格中的搜索时间与路径长度作成线条图形式，如图13所示，随着地图空间的增加，本文算法相对于传统A*算法在搜索时间方面有很大的提升，耗时长短与融合JPS的改进A*算法相当；如图14所示，相比于传统A*算法与融合JPS的改进A*算法相比，本文算法的路径长度平均增加了11.3%，这主要体现在为了提高安全性需要增加其他节点，从而可以避开障碍物。此外在评估节点数量方面，本文算法体现出搜索方向的引导效果好，减少了需要比较计算的节点数。

图13 搜索时间对比图

图14 路径长度对比图

4 结束语

本文针对传统A*算法在移动机器人路径规划的过程中存在的一些问题进行了针对性的改进：首先为有效解决传统A*算法在移动机器人寻找路径时，其在大面积地图环境下，随着路径长度的增加，搜索时效性低，本文结合了JPS算法的选取跳点思想，对路径节点进行有针对性的选取；其次为了解决在拥挤的地图环境下，规划路径不符合机器人运动学原理，容易造成误碰撞问题，本文将传统A*算法结合安全权重方阵，使得移动机器人可以有效的与障碍物保持安全距离，从而提升算法的安全性。最终融合以上两种方法构建融合JPS与安全权重方阵的改进A*算法，使得移动机器人可以在复杂环境下提高实时性，同时也可以增加路径轨迹的安全性。下一步工作将会考虑如何应对动态环境中的路径规划，以此来提高算法的鲁棒性。