基于改进A*算法的移动机器人全局路径优化研究

方文凯 廖志高

摘 要：针对传统A*（A-STAR）算法在移动机器人全局路径规划中存在搜索效率低下、搜索路径不够平滑及不安全等问题，提出一种双向搜索A*算法。在传统A*算法上建立起四邻域及八邻域混合搜索路径机制，设定双向搜索中的虚拟目标点，借助人工势场算法思想，建立双向搜索时搜索点到该虚拟目标点的衰减函数，并在保证最优性的基础上改进评估函数模型以及调试适当的权重值，引入三阶贝塞尔曲线规划新的行驶路径。通过Pycharm平台进行仿真，结果表明：改进后的A*算法所规划的路径长度、搜索效率及路径平滑性等特性都优于传统A*算法，规划出的路径长度较传统算法提高19.61%，搜索效率较传统算法提高66.19%，路径平滑度大幅度提高，全局路径优化效果较为明显。

关键词：移动机器人；全局路径规划；人工势场；双向搜索；贝塞尔曲线

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

0 引言

随着现代科技不断高速发展，智能移动机器人凭借小巧灵活、简单操作、功能丰富以及能满足人们诸多需求的优势，始终处于科学研究的前沿，同时也不断推动着科技的进步。在移动机器人的研究中，如何使机器人自主规划出最优路径是重点问题[1-2]。移动机器人路径规划分为全局路径和局部路径[3]，全局路径是指在运动信息已知的状态下全局搜索到最优路径，而局部路径是指运动信息未知或获取不全的状态下自主规划路径的过程。常用于移动机器人全局路径规划的算法有A*算法[4]、Dijkstra算法[5]、RRT算法[6]、粒子群算法[7]以及仿生智能算法[8]等，局部路径规划算法有动态规划法[9]、动态窗口算法[10]、人工势场法[11]等。

A*算法是一种启发式搜索路径算法，既有深度优先遍历算法的全局搜索性[12]，又有广度优先遍历算法的贪心性[13]，能够在运动环境已知的场景下快速搜索到最优路径，被广泛应用于路径规划领域中。为了获取更优的路径效果，学者们进行了诸多研究。周超等[14]对A*算法的启发搜索函数进行改进，引入坡度信息影响因素，使得A*算法能够在坡度不平的环境中规划最优路径，但在规划路径的过程中造成节点过多，从而导致路径不够平滑。陈家宝等[15]通过对启发函数引入权重值来优化评估函数模型，使得A*算法能夠加快搜索效率，但易陷入局部最优解中。柴红杰等[16]针对A*算法规划的路径不够平滑等问题，提出在障碍物节点附近建立缓冲地带来增加移动过程中的安全性，但在仿真过程中算法搜索效率低下及搜索时间较长。刘子豪等[17]针对A*算法搜索效率低下等问题，提出使用跳跃点搜索理论来搜索运动的节点，有效地减少了在搜索过程中无效节点的遍历，但所规划的路径不够平滑，不利于移动机器人的路径行驶。黄迎港等[18]针对多障碍物环境设计一种运动优先级策略以提高搜索效率，但并未考虑到改进后的算法在特殊环境中的路径状况。

由以上分析可知，A*算法仍然存在搜索路径时路径不够平滑、搜索时间过长以及算法效率低下等问题。故本文先建立起较为复杂的全局静态障碍物环境，提出改进移动机器人运动模型，引入四邻域及八邻域混合搜索模型，使得规划出的路径相对安全。在此基础上，设置虚拟目标点，借助人工势场算法思想设计出衰减函数，从而双向搜索路径使得搜索点在虚拟目标点重合，减少无效节点搜索，并改进A*算法中的评估函数以及增添适当的权重值，引入三阶贝塞尔曲线轨迹优化，最终达到提高算法搜索效率及优化轨迹的目的。

1 传统A*算法

1.1 仿真环境及遍历节点

在研究移动机器人路径规划时需要确定其仿真环境，常用的仿真环境分为栅格地图、矢量地图以及自由空间地图等。因栅格地图具有易理解、结构简单清晰等优势，故采用较为广泛的等精度正方形栅格地图来模拟机器人运动环境，以栅格大小为单位记录其运动信息。

传统A*算法在遍历节点时一般是四邻域或八邻域方式。如图1所示，图1（a）所示为四邻域遍历，遍历下一个节点方向为正上、正下、正左以及正右，但容易造成规划出的路径转折点过多的问题。图1（b）所示为八邻域遍历，在四邻域上增加了左上、左下、右上以及右下方向，扩大了遍历节点范围，但容易造成遍历节点时忽略障碍物的存在。

1.2 传统A*算法原理

传统A*算法是一种启发式搜索算法，该算法既有Dijkstra算法全局搜索性，又有BFS算法的贪心性。区别于A*算法，Dijkstra算法是遍历全局节点进行搜索的，并没有考虑到与目标点位置之间的导向作用，故在使用Dijkstra算法路径规划时搜索效率低下，但因全局搜索导致搜索的路径往往是最优路径。而BFS算法中的贪心性增添了与目标点位置之间的导向作用，收录节点时会选择与目标点方向相近的节点，故遍历搜索时较快，但规划的路径往往是次优路径。而A*算法则融合了Dijkstra算法全局搜索性及BFS算法的贪心性，建立起新的启发式评估函数模型，如式（1）—式（3）所示：

[fn=λn+μn，] （1）

[λn=x-xs2+y-ys2，] （2）

[μn=x-xg2+y-yg2.] （3）

式中：n为搜索当前节点；x、y分别为当前节点的位置坐标；xs、ys为初始节点的横、纵坐标；xg、yg为目标点的横、纵坐标；[fn]为当前节点搜索时的评估函数值；[λn]为当前节点与起点之间的评估值；[μn]为当前节点与目标点之间的评估值。当[λn]为0时表示该算法退化为BFS算法，当[μn]为0时表示该算法退化为Dijkstra算法。

2 改进双向搜索A*算法

2.1 改进搜索邻域

针对传统A*算法搜索邻域较差导致规划路径不平滑及行驶不安全等问题，本文将传统的单一四邻域及八邻域搜索机制改进为四邻域及八邻域混合切换搜索机制，即遍历子节点时首先判断与障碍物之间的距离，当运动节点到达以障碍物为圆心、单位栅格对角线长度为直径的安全距离时切换成四邻域搜索，大于安全距离时切换成八邻域搜索。此方法融合了四邻域及八邻域搜索优势，使得移动机器人在行驶的过程中更加安全。

四邻域及八邻域混合切换机制是一种新的遍历节点策略。如图2所示，当节点A点需要收录B点时，若采用单一的四邻域搜索遍历，得出的路径则是A-b1-a1-B或A-b1-b2-B；若采用单一的八邻域搜索遍历时，得出的路径是A-b2-B；而若采用混合切换机制搜索遍历时，得出的路径是A-b1-B。从不同搜索路径方式可知，混合切换机制搜索得到的路径相对远离障碍物，避免了转折点过多及穿过障碍物的情况发生，对于移动机器人行驶则更加安全，从而体现出混合切换搜索机制的优势。

2.2 改进双向搜索

双向搜索A*算法是在传统A*算法基础上采用双向同步搜索方式，即将起点和目标点当成新的搜索点，引入虚拟目标点，即起点与目标点的中点，若虚拟目标点为障碍物，则按照四邻域及八邻域混合搜索机制重新搜索到满足条件的虚拟目标点，使得新的搜索点同时向虚拟目标点方向搜索，直至在虚拟目标点相遇，从而停止搜索得到全局路径。具体的算法步骤及流程图（图3）如下：

Step 1 首先构建100*100栅格环境地图。

Step 2 创建3个列表：open_list 1（S）、open_list 2（H）以及closed_list 1（D），其中open_list 1和open_list 2表示双向搜索过程中待遍历收录的节点，closed_list表示收录已存放遍历的节点且放置虚拟目标点，并将起点放到open_list 1中，将目标点放到open_list 2中，开始遍历全局节点。

Step 3 判断收录的节点中closed_list是否与虚拟目标点重合，如果是，利用回溯算法原理将closed_list中的节点遍历，求解该最短路径长度，结束算法；如果不是，则执行下一步操作。

Step 4 按照该节点为新节点进行遍历，先判断与障碍物之间的安全距离，大于安全距离时采用八邻域遍历搜索，小于安全距离时采用四邻域搜索，生成对应的子节点。判断该子节点是否在open_list 1及open_list 2中，如果是，则更新open_list 1及open_list 2中的[fa]，如果不是，则需要收录该节点，并分别计算该节点的[fa]值。

Step 5 选取最小的[fa]中的节点加入到closed_list前序及后序中，并删掉在open_list 1及open_list 2对应的值，当open_list 1及open_list 2列表为空则算法结束，并返回Step 3。

2.3 改进评估函数

为使得改进后A*算法能够保持前期加快搜索而后期扩大搜索范围，引入人工势场算法思想，根据人工势场中引力作用设立衰减函数，使得虚拟目标点为双向搜索点提供一个新的评估函数。其值为初始点A点及目标点B点的中心点C点（xu，yu），以节点a为例，即（a-A）作用、（a-C）作用以及（A-C）作用，通过不断调整引力作用权重值使得移动机器人向虚拟目标点靠拢并相遇，其引力图如图4所示。

如图4所示，A、B两点为起始点和目标点，C点为虚拟目标点，搜索节点a和b向虚拟目标点靠拢，其节点a改进后评估函数模型：

[fa=λa+ωx*?a-η*γa，η∈0，1.]

（4）

式中：[λa=x-xs2+y-ys2；]

[?a=x-xu2+y-yu2；]

[γa=xu-xs2+yu-ys2；]

[ωx=1ρ2πexp-x-?22ρ2，]

其中[ρ=12π]，[?]为虚拟目标点的中点。根据评估函数模型，在保证最优性基础上使得评估值[fa]比实际值小，从而不断地改变[η]值，继而规划出最优路径。

2.4 改进路径平滑性

通过上述改进策略使得移动机器人行驶更加安全，搜索效率大幅度提高，但仍存在着规划路径不够平滑等问题，即在行驶过程中容易造成移动机器人转弯斜度过大等问题，需要对行驶路径进行平滑性处理。而三阶贝塞尔曲线具有保凸性及平滑性等优点，被广泛应用在路径规划领域，具体表达式为：

[Dt=i=0nnipi1-tn-iti，t∈0，1，] （5）

[bt=p01-t3+3p1t1-t2+3p2t21-t+][[p3t3，t∈0，1.]] （6）

其中：式（5）为贝塞尔曲线表达式；式（6）为三阶贝塞尔曲线；[pii=0， 1， …， n]为给定的轨迹点。随着[t]不断连续变化，可以描绘出平滑完整的移动机器人行驶路径。

3 仿真及结果分析

为验证本研究的科学性对其进行仿真分析。其仿真实验环境如下：处理器为Intel CORE i7-6700 HQ，CPU为2.60 GHz，编程语言为python，面向对象开发设计并在2021版pycharm开源平台模拟仿真。针对移动机器人全局路径规划研究，分别对传统A*算法以及改进后A*算法在较为复杂的栅格常规环境中模拟仿真对比，其栅格环境地图为100×100单位栅格，机器人移动半径为1个单元栅格，起点位置为[1，1]，目标点位置为[99，99]。为验证改进后A*算法的科学性，将A*算法改进过程逐个进行对比分析，分别提高A*算法在移动机器人路径规划领域中的鲁棒性。

3.1 四邻域及八邻域混合搜索机制仿真

实验一：为提高移动机器人行驶安全，采用四邻域及八邻域混合搜索机制进行仿真分析，并将各邻域搜索仿真图做横向对比分析，得到传统算法不同遍历节点图及仿真数据，如图5和表1所示。

通过对仿真数据进行对比分析可知，在运用四邻域及八邻域混合机制来搜索节点的过程中能够使得规划出来的路径相对平滑，可以防止出现图5（b）中陡峭的移动方向改变，使得移动机器人在行驶过程中更加安全，故改进有效。同时，在运用混合遍历方式时可以进一步得到最优的路径，使得规划的路径更短，但搜索时间将会增多。

3.2 双向搜索仿真

实验二：针对传统A*算法在搜索中存在着搜索过慢等问题，改进A*算法采用双向搜索路径方式，在混合搜索机制基础上进行仿真并做横向对比分析，得到传统算法及双向搜索A*算法仿真图如图6所示，仿真数据见表2。

通过对比分析图6（a）与图6（b）可知，双向搜索A*算法在搜索过程中可以大幅度降低搜索时间，适当地放弃无效节点的遍历，从而进一步提高算法搜索效率，故改进有效。但在路径规划中可能会导致规划长度不是最优，这主要是因为设计虚拟目标点时不在最优路径上，从而导致规划出次优的路径。但运用双向搜索可以大幅度提高算法效率，降低搜索时间。

3.3 新评估函数仿真

实验三：为提高A*算法的搜索效率，在上述四邻域及八邻域混合搜索机制及双向搜索A*算法后改进新的评估函数模型，在保证最优性基础上不断调试评估函数模型中的权重值[η]，得到仿真图及仿真数据，如图7和表3所示。

从对图7（a）和图7（b）栅格环境的对比分析可知，在保证评估函数最优性的基础上不断调试权重值[η]，使得規划长度及搜索时间等指标达到最优为止，从而进一步提升算法搜索效率，规划出最优路径，使得改进算法有效。

3.4 路径平滑性仿真

实验四：针对移动机器人在行驶中存在拐点较多等问题，采用三阶贝塞尔曲线来改进A*算法，并在上述优化策略后，增添贝塞尔曲线得到路径平滑性仿真图及数据，如图8和表4所示。

通过对比分析图8可知，图8（a）中存在过多的拐点，但对比图8（b），三阶贝塞尔曲线处理后使得规划的路径相对平滑许多，各折线拟合出一条完整的曲线，更有利于移动机器人的平滑行驶。与传统A*算法四邻域搜索仿真对比，改进后路径长度优化19.61%，搜索效率优化66.19%，即三阶贝塞尔曲线改进后A*算法无论是在搜索效率还是在路径规划安全平滑性上都有大幅度的提升，故改进有效。

4 结论

针对传统A*算法在全局路径规划中存在路径规划不平滑、不安全及搜索效率低下等问题，首先，建立起四邻域及八邻域混合搜索机制，使得规划出的路径相对远离障碍物，在移动过程中更加安全。其次，引入双向同步搜索机制并设计虚拟目标点，借助人工势场思想，建立搜索点到虚拟目标点的衰减函数模型，在保证最优性基础上，在新的评估函数中增添权重值，通过不断调整权重值使得在保证规划路径最优时提高算法搜索效率，降低算法搜索时间。最后，引入三阶贝塞尔曲线使得规划出的路径更加平滑。但该改进后的算法并不是在任何情况下都优于传统算法，当出现虚拟目标点严重偏移最优路径时，改进后的算法将可能低于传统算法的性能。此外，该算法只是在仿真模拟实验，缺乏实际移动机器人的测试，下一步将结合实际应用场景展开研究。

参考文献

[1] PATLE B K，BABU L G，PANDEY A，et al.A review：on path planning strategies for navigation of mobile robot[J].Defence Technology，2019，15（4）：582-606.

[2] ZAFAR M N，MOHANT J C. Methodology for path planning and optimization of mobile robots： a review[J].Proceda Computer Science，2018，133：141-152.

[3] GARCIA M A P，MONTIEL O，CASTILLO O，et al.Path planning for autonomous mobile robot navigation using ant colony optimization and a fuzzy cost function evaluation[J].Applied Soft Computing，2009，9（3）：1102-1110.

[4] LI C G，HUANG X，DING J，et al.Global path planning based on a bidirectional alternating search A* algorithm for mobile robots[J].Computers and Industrial Engineering，2022，168：108123.

[5] DAKULOVI? M，HORVATIC S， PETROVIC I.Complete coverage D* algorithm for path planning of a floor-cleaning mobile robot[J].IFAC Proceedings Volumes， 2011， 44（1）：5950-5955.

[6] MASEKO B B，VAN DAALEN C E，TREURNICHT J.Optimised informed RRTs for mobile robot path planning[J].IFAC-Papers OnLine，2021，54（21）：157-162.

[7] DEWANG H S，MOHANTY P K，KUNDU S.A robust path planning for mobile robot using smart particle swarm optimization[J].Procedia Computer Science，2018，133：290-297.

[8] TUNCER A，YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering，2012，38（6）：1564-1572.

[9] DENG X，LI R F，ZHAO L J，et al.Multi-obstacle path planning and optimization for mobile robot[J].Expert Systems with Applications，2021，183：115445.

[10] COSTANZI R，FANELLI F，MELI E，et al.Generic path planning algorithm for mobile robots based on Bezier curves[J].IFAC-PapersOnLine，2016，49（15）：145-150.

[11] LAZAROWSKA A.Discrete artifificial potential field approach to mobile robot path planning[J].IFAC-Papers OnLine，2019，52（8）：334-337.

[12] WAHAB M N A，NEFTI-MEZIANI S，ATYABI A. A comparative review on mobile robot path planning： classical or meta-heuristic methods[J].Annual Reviews in Control，2020（50）：233-252.

[13] SAEED R A，RECUPERO D R，REMAGNINO P.A boundary node method for path planning of mobile robots[J].Robotics and Autonomous Systems，2020，123：103320.

[14] 周超，谷玉海，任斌.基于一種改进A*算法的移动机器人路径规划研究[J].重庆理工大学学报（自然科学），2021，35（5）：127-134.

[15] 陈家宝，文家燕，谢广明.基于改进A*算法的移动机器人路径规划[J].广西科技大学学报，2022，33（1）：78-84.

[16] 柴红杰，李建军，姚明.改进的A*算法移动机器人路径规划[J].电子器件，2021，44（2）：362-367.

[17] 刘子豪，赵津，刘畅，等.基于改进A*算法室内移动机器人路径规划[J].计算机工程与应用，2021，57（2）：186-190.

[18] 黄迎港，陈锴，罗文广.复杂环境下无人机全覆盖路径规划混合算法研究[J].广西科技大学学报，2022，33（1）：85-93.

Research on global path optimization of mobile robot based

on improved A* algorithm

FANG Wenkai1，LIAO Zhigao* 1，2

（1.School of Economics and Management， Guangxi University of Science and Technology， Liuzhou 545006 China; 2. Guangxi Industrial High Quality Development Research Center （Guangxi University of Science and Technology）， Liuzhou 545006， China）

Abstract：Traditional A*（A-STAR） algorithm has some problems in global path planning of mobile robot， such as low search efficiency， insufficient smooth and safe search path， and so on. A bidirectional search A* algorithm is proposed. Firstly， based on the traditional A* algorithm， the four-neighborhood and eight-neighborhood hybrid search path mechanism is established， and the virtual target point in the two-way search is set. With the help of artificial potential field algorithm， the attenuation function from the end point to the virtual target point is established. On the basis of ensuring the optimality， the evaluation function model is improved and the appropriate weight value is debugged， and the third-order