陈家宝 文家燕 谢广明

摘  要：在移动机器人路径规划中，针对传统A*算法规划的路径搜索时间长与不平滑的问题，提出一种改进的A*算法。首先，在传统A*算法的基础上，混合使用4邻域和8邻域搜索算法，并建立切换机制，改变搜索范围，提高路径搜索精度，减少了路径转折点。其次，通过对启发式函数引入权重，优化估价函数，缩短了路径规划时间。最后，对A*算法规划的路径使用3次均匀B样条曲线进行平滑处理，消除路径拐角尖点，在保证路径最优的情况下，提高路径平滑性。仿真结果表明，改进后的A*算法所规划的路径在长度、平滑性、搜索消耗时间等特性上都优于传统算法。

关键词：移动机器人;路径规划;A*算法;B样条曲线

中图分类号：TP242           DOI：10.16375/j.cnki.cn45-1395/t.2022.01.012

0    引言

近年来，国家高度重视和支持机器人领域的技术创新，随着利好政策不断出台，我国机器人产业正在进入飞速发展阶段[1]。在移动机器人领域，路径规划是指在有障碍物的工作环境中寻找一条由起始位置到目标位置的无碰撞路径，使机器人可以准确无误地到达工作岗位，这是研究的重点和难点[2-3]。

国内外研究学者针对路径规划问题提出了许多有效的算法，目前主要采用粒子群算法[4]、人工势场法[5]、A*算法[6]、Dijkstra算法[7]、蚁群算法[8]等。其中A*算法是一种启发式搜索算法，具有简单易操作的特点，广泛应用于路径规划问题中[9]。但在实际应用中发现，规划的路径存在转弯折点较多、路径搜索不精确、不平滑、遍历节点数较多等     缺点。

为获得更优的路径，研究者们进行了许多改进。文献[10]提出使用跳点搜索算法来改进A*算法，有效减少列表中无用节点数量，但所规划的路径转折直角过多，不利于移动机器人行驶。文献[11]提出改进双向A*算法，使起点和目标点同时运行A*算法，用来减少寻路时间，但当起点和目标点中间存在障碍物时，会产生并行搜索区域，没能减少时间反而增加了寻路时间。文献[12]引入模拟退火法来优化A*算法，扩展节点选择方式，但在复杂的障碍物环境下将会产生大量无用的扩展节点，增加了时间。文献[13]通过扩大A*算法的搜索邻域为24邻域，增加了路径选择方向，但应用到障碍物复杂的环境下，会产生忽略障碍物的情况，导致路径搜索不精确。

由以上研究可知，A*算法仍然存在路径搜索不精确、转折点多、不平滑等问题。本文建立了比较复杂的障碍物环境地图，提出结合4邻域和8邻域搜索算法的A*算法，同时对启发式函数引入权重，对路径进行3次均匀B样条曲线平滑处理。解决了路径搜索不精确问题，在保证路径长度最短且平滑的情况下，减少寻路时间，获取一条最优路径。通过仿真试验，验证了所提算法的可行性与有效性。

1    A*算法

1.1   传统A*算法

A*算法是一种启发式搜索算法，是求解最优路径的有效方法[14]。它通过估价函数[f（n）]来引导搜索方向，从而寻找出最优路径。其估价函数为：

[f（n）=g（n）+h（n）]，                  （1）

式中：[n]代表当前节点，[f（n）]是当前节点[n]的估价函数，[g（n）]是移动机器人从起始节点到达当前节点[n]的实际代价值，[h（n）]是从当前节点[n]到达目标节点的代价估计值，通常采用歐氏距离或曼哈顿距离表示。欧氏距离指2个节点之间的直线距离，曼哈顿距离指2个节点坐标之间横轴和纵轴绝对值之和。由于机器人在栅格环境地图中不能全向移动，所以在考虑实际应用情况下，本文采用曼哈顿距离来表示，公式如下：

[h（n）=xn-xg+yn-yg]，               （2）

式中：[（xn， yn）]表示路径当前节点所在栅格中心的位置坐标，[（xg， yg）]表示路径目标节点所在栅格中心的位置坐标。

算法流程如图1所示。

Step  1     构建环境地图。

Step 2    设定2个列表：CLOSED列表和OPEN列表，其中CLOSED列表用于存放已扩展节点，OPEN列表用于存放待扩展节点。初始化CLOSED列表和OPEN列表为空，将起始节点S放入OPEN列表中。

Step 3    在OPEN列表中搜索[f（n）]代价最小的节点[n]，将该节点放入CLOSED列表中，并从OPEN列表中移除该节点。

Step 4    判断CLOSED列表中的节点[n]是否为目标节点G，如果是，则利用回溯算法，求解得出最短路径，结束算法;如果不是，则以该节点为父节点向4个方向继续进行扩展搜索，生成对应方向的子节点[m]。

Step 5    判断子节点[m]的位置在地图中是否有障碍物，如果是，则删除该节点;如果不是，则对其进行下一步判断。

Step 6    判断该节点是否在OPEN列表中，如果是，则需要计算该节点的[f（n）]，并选取最小代价的节点并保留;如果不是，则将该节点放入OPEN列表中，再计算代价。

Step 7    返回Step 3，继续循环以上步骤搜索，直至找到目标节点G，得出最短路径，结束算法。

由于传统A*算法所规划的路径存在一定的缺陷，易产生大量与最终路径无关的节点，运动路径转折点多，不平滑，路径搜索精确度低，难以满足移动机器人的实际工况运动要求。因此，本文提出一种改进搜索邻域和启发函数的A*算法。

1.2  改进搜索邻域和启发函数的A*算法

1.2.1    改进搜索邻域

传统A*算法搜索扩展节点一般采用4邻域或  8邻域搜索算法[15]，如图2所示。其中图2（a）所示为4邻域搜索，即每个搜索方向之间夹角都为90°，容易造成规划的路径转折点过多。图2（b）所示为  8邻域搜索，在4邻域的基础上增加了4个邻域，使得搜索方向之间的夹角变为45°，优化了搜索角度，扩大了搜索节点的范围。但在较复杂的地图环境中，会使得搜索不精确，易忽略障碍物的存在，造成规划的路径会穿过障碍物，不符合移动机器人实际运动路径的要求。

针对传统A*算法邻域搜索不足的问题，本文将传统算法单一的邻域搜索模式改进为结合4邻域和8邻域的混合搜索算法，即通过对当前节点的障碍物环境进行判断，切换使用4邻域和8邻域搜索算法，再对子节点进行搜索扩展。此法改变了传统算法单一的扩展子节点方式，融合了2种搜索算法的优点，使得路径转折点减少，路径搜索精度提高。

混合4邻域和8邻域搜索算法是一种新的搜索策略。如图3所示，从S节点到达G节点时，当遇到障碍物，采用4个邻域搜索扩展路径到达B2节点，没有障碍物则采用8个邻域搜索扩展路径到达G节点，得出代价最优路径S-B2-G。而传统4邻域搜索得到的路径为S-B2-A-G或S-B2-B3-G，传统8邻域搜索得到的路径为S-B3-G，显然传统邻域搜索得到的路径存在转折点多和会穿过障碍物的情况，没有混合算法优越。

改进搜索邻域算法流程主要分为两部分：1）初始阶段，先将起始节点放入OPEN列表中;2）扩展阶段，通过判断设定的切换触发条件，采用4邻域或8领域进行扩展。主要步骤如下：

Step 1  当进行扩展子节点时，需要对当前节点[n]的4个方向的待扩展子节点进行判断，并进行标记。如判断是障碍物，则对变量赋值为1;如判断不是障碍物，则对变量赋值为0。

Step 2  通过确定变量值来选用搜索算法。当为1时，使用4邻域搜索算法的A*算法进行扩展，扩展后再判断节点是否在OPEN列表中，并对其进行进一步处理，找出最小代价节点。当为0时，使用8邻域搜索算法的A*算法进行扩展，通过标记情况获取信息，判断是否计算8个方向扩展节点的代价值。当对8个方向进行计算时，需要比较、计算8个方向的代价值，判断节点是否在OPEN列表中，并选取最小代价值确定扩展方向;否则直接进行判断，计算代价值确定扩展方向，再保存到OPEN列表中，进行下一步处理。

Step 3  返回Step 1，循环搜索直至寻找到目标点，得出路径。

1.2.2    启发函数的优化

传统A*算法的估价函数只是将实际成本和启发式成本直接相加，而实际上，实际成本和启发式成本在最佳成本估价函数中的权重往往不相等[16]。因此，为不同环境下的启发式代价设置一定的权重，优化估价函数，有助于提高A*算法的运行   效率。

1）考虑在一种极端情况下，如果[h（n）]为0，则只有[g（n）]起作用，A*算法演变成为Dijkstra算法，这样能够保证寻找到最短路径。但函数[h（n）]使用更大的启发式算法来估计从[n]到目标的最小路径的代价，可以限制对路径方向的一些偏离。2）如果[h（n）]小于或等于从[n]运动到目标的实际代价，可以保证能够寻找到一条最短的路径，但[h（n）]越小，A*算法搜索扩展的节点越多，规划路径的速度就越慢。3）如果[h（n）]恰好等于从[n]运动到目标点的代价，那么算法将只搜索寻找最优路径而不会搜索扩展任何其他节点，将会大大减少计算量，此时A*算法规划路径会非常快。尽管这很难实现，但只要能够提供精确的信息，在某些特殊的情况下让它们相等，A*算法运行的效果也会很好。4）如果[h（n）]大于从[n]运动到目标的代价，就不能保证寻找到的路径最短，但A*算法规划路径消耗的时间会很短。5）如果[h（n）]比[g（n）]大很多，则只有[h（n）]起作用，A*算法就会演变成广度优先搜索算法。

针对上述问题，本文对启发式函数引入权重，将传统A*算法的估价函数重新构造为：

[f（n）=g（n）+w*h（n）]，[w≥1].         （3）

通过改变[w]来影响搜索效率，但如果权重过大会导致规划路径陷入局部最优。为此，在实际应用时，可以根据需求灵活地调节[w]，提高A*算法效率。

传统A*算法和引入启发式函数权重的A*算法在MATLAB中的路径规划仿真结果分别如图4和图5所示。选用100[×]100大小的栅格环境地图，障碍物占比为20%。仿真图中左上方圆圈设置为起点，右下方方块设置为目标点，阴影区域为算法搜索节点，黑色线条为规划所得最短路径。对比分析2个仿真结果得出，引入启发式函数权重的A*算法搜索区域少，搜索时间短，效率明显比传统A*算法高。

2    3次均匀B样条曲线路径平滑处理

混合了4邻域与8邻域搜索并引入權重的改进A*算法，其规划所得的路径准确性明显提高，规划时间缩短，但路径不平滑、拐角尖点的问题依然比较突出，造成机器人行驶转弯效率低，不利于移动。因此，需要平滑处理规划所得的路径，有助于提高机器人运动效率。而B样条曲线具有几何保凸性、不变性、凸包性等优点，被应用于路径平滑处理[17]。其中3次B样条曲线在节点处具有二阶连续性的特点，能够优化曲线，满足机器人移动的加速度与速度连续性的要求。所以本文采用3次均匀B样条曲线对路径进行平滑处理，B样条曲线表达式为：

[C（t）=i=0nPiNi， k（t）]，                   （4）

式中：[Pi（i=0， 1， 2， …， n）]为给定控制点的坐标，[Ni， k（t）]为基函数，其表达式为：

[Ni， k（t）=1k！j=0k-i（-1）jCjk+1（t+k-i-j）k]，

[0≤t≤1]， [i=0， 1， …， k-1]，         （5）

[Cjk+1=（k+1）！j！（k+1-j）！].           （6）

由式（4）和式（5）可知，当[k=3]时，基函数为：

[N0，  3（t）=16（-t3+3t2-3t+1）N1，  3（t）=16（3t3-6t2+4）N2，  3（t）=16（-3t3+3t2+3t+1）N3，  3（t）=16t3]. （7）

将式（7）代入式（4），得到3次均匀B样条曲线方程为：

[N0， 3（t）=161tt2t31410-30303-630-13-31P0P1P2P3].

（8）

使用3次均匀B样条曲线来对A*算法的尖点路径进行光滑处理。将获取的相邻坐标代入上述公式中，就能确定控制点对应的样条曲线方程，随着[t]的连续取值，就可以绘制出光滑的B样条曲线。当有[n]个控制顶点时，只需要将控制顶点移动[n-3]次，就能得到一条完整、连续的3次B样条曲线，完成对路径的平滑优化处理。

3    仿真及结果分析

为验证本文所设计算法的可行性和有效性，在MATLAB R2020b中建立比较复杂的障碍物栅格环境地图。针对移动机器人路径规划问题，分别对传统A*算法和本文混合4邻域与8邻域搜索同时引入权重的A*算法进行仿真。

3.1   路径规划仿真试验

构建的栅格环境地图大小为30[×]30。如图6所示，环境地图中左上角的圆点为机器人起点，右下角的圆点为目标点，障碍物为黑色方格，可行路径为白色方格。

在相同的障碍物环境地图中（图6），分别采用传统A*算法4邻域搜索、8邻域搜索和本文的改进邻域搜索并引入权重的A*算法进行路径规划仿真试验，获得的仿真结果分别如图7—图9所示。

分析图7—图9可得，相同环境下，4邻域A*算法规划的路径长度不是最优，路径转折点多。   8邻域A*算法规划的路径出现了从2个障碍物之间穿过去的情况，所得路径不符合移动机器人的运动要求。本文改进邻域搜索并引入权重的A*算法所规划的路径明显比4邻域A*算法规划的路径转折点少，遇到障碍物会选择使用4邻域A*算法，没有障碍物时会使用8邻域A*算法，解决了路径会穿过障碍物的问题，同时引入启发式函数权重，提高了效率，路径长度得到减小。

传统A*算法和改进邻域搜索并引入权重的A*算法性能如表1所示。由表1可知，改进邻域搜索并引入权重的A*算法消耗的时间和规划的路径长度明显优于传统A*算法。

3.2   路径平滑处理仿真试验

采用3次均匀B样条曲线对路径进行平滑处理，仿真结果如图10所示，局部放大如图11所示。从图中可以看出，路径经过3次均匀B样条曲线处理后变得十分平滑。对比改进邻域搜索并引入权重A*算法规划的路径可知，3次均匀B样条曲线消除了路径上的拐角尖点，使路径更加平滑顺畅，同时在保证路径最优情况下，减小了路径的长度。机器人在实际移动时遇到直角转向会造成卡顿，而路径经过平滑处理后，机器人可以保持加速度与速度的连续性，使机器人移动更加流畅。仿真结果表明本文算法对路径平滑处理的可行性与有效性。

4    结论

本文针对移动机器人路径规划问题，提出了一种改进A*算法：混合使用4邻域与8邻域搜索算法，调节算法搜索邻域，从而提高了路径搜索精确度，减少规划路径的转折点;引入启发式函数权重，改变启发式成本在成本估价函数中的权重，缩短了路径规划的时间。对规划路径进行3次均匀B样条曲线平滑处理，消除了路径拐角尖点，使机器人可以平滑地移动到目标点。仿真结果表明，混合4邻域与8邻域搜索同时引入权重的A*算法，结合3次均匀B样条曲线平滑处理后，应用于移动机器人路径规划上是可行和有效的。

参考文献

[1]     吴青鸿，李健，刘欢，等.基于模糊PID下肢外骨骼机器人的控制技术[J].广西科技大学学报，2020，31（4）：104-111.

[2]     卜新苹，苏虎，邹伟，等.基于非均匀环境建模与三阶Bezier曲线的平滑路径规划[J].自动化学报，2017，43（5）：710-724.

[3]     王洪斌，尹鹏衡，郑维，等.基于改进的A*算法与动态窗口法的移动机器人路径规划[J].机器人，2020，42（3）：346-353.

[4]     皮倩瑛，葉洪涛.一种动态调节惯性权重的粒子群算法[J].广西科技大学学报，2016，27（3）：26-32.

[5]     丁佳宇，王茂森，戴劲松.基于前馈控制人工势场法的无人机群系统设计[J].传感器与微系统，2021，40（5）：114-117.

[6]     田华亭，李涛，秦颖.基于A*改进算法的四向移动机器人路径搜索研究[J].控制与决策，2017，32（6）：1007-1012.

[7]     SUNITA，GARG D.Dynamizing dijkstra：a solution to dynamic shortest path problem through retroactive priority queue[J].Journal of King Saud University-Computer and Information Sciences，2021，33（3）：364-373.

[8]     LIU J H，YANG J G，LIU H P，et al.An improved ant colony algorithm for robot path planning[J].Soft Computing，2017，21（19）：5829-5839.

[9]     张红梅，李明龙，杨乐.基于改进A*算法的移动机器人安全路径规划[J].计算机仿真，2018，35（4）：319-324.

[10]   赵晓，王铮，黄程侃，等.基于改进A*算法的移动机器人路径规划[J].机器人，2018，40（6）：903-910.

[11]   王中玉，曾国辉，黄勃.基于改進双向A*的移动机器人路径规划算法[J].传感器与微系统，2020，39（11）：141-143.

[12]   祁玄玄，黄家骏，曹建安.基于改进A*算法的无人车路径规划[J].计算机应用，2020，40（7）：2021-2027.

[13]   张敬寒，陶兆胜，彭澎，等.基于扩大搜索邻域A*算法的平滑路径规划[J].长春理工大学学报（自然科学版），2018，41（6）：124-127.

[14]   杨瑶，付克昌，蒋涛，等.一种改进A*算法在智能车中的应用研究[J].重庆理工大学学报（自然科学版），2021，35（3）：71-79.

[15]   张志文，张鹏，毛虎平，等.改进A*算法的机器人路径规划研究[J].电光与控制，2021，28（4）：21-25.

[16]   LIN M X，YUAN K，SHI C Z，et al.Path planning of mobile robot based on improved A* algorithm[C]//29th Chinese Control and Decision Conference，2017：3570-3576.

[17]   胡中华，许昕，陈中.无人机三维航迹非均匀3次B样条平滑算法[J].控制工程，2020，27（7）：1259-1266.

Mobile robot path planning based on improved A* algorithm

CHEN Jiabao1， WEN Jiayan*1，2， XIE Guangming1，3

（1. School of Electrical，Electronic and Computer Science， Guangxi University of Science and Technology，

Liuzhou 545616， China; 2. Guangxi Key Laboratory of Automobile Components and Vehicle Technology（Guangxi University of Science and Technology）， Liuzhou 545006， China; 3. College of Engineering，

Peking University， Beijing 100871， China）

Abstract： In the path planning of mobile robots， an improved A* algorithm is proposed to solve the problem of long and unsmooth path search time subjected to the traditional A* algorithm. Firstly， on the basis of the traditional A* algorithm， the 4-neighbor and 8-neighbor search algorithms are mixed， and a switching mechanism is established to improve the path search accuracy and reduce path turning points. Secondly， by introducing weights to the heuristic function， the evaluation function is optimized， and the path planning time is shortened. Finally， the path planned by the A* algorithm is smooth using cubic uniform B-spline curves to eliminate the corners of the path and improve the smoothness of the path while ensuring the optimal path. The simulation results show that the path planned by the improved A* algorithm is superior to the traditional algorithm in terms of length， smoothness， and searching time consumption.

Key words： mobile robot; path planning; A* algorithm; B-spline curve

（责任编辑：黎  娅）