基于拟合优先搜索的多场景自适应改进A＊算法.pdf

基于拟合优先搜索的多场景自适应改进A*算法*沈克宇,游志宇,刘永鑫(西南民族大学电气工程学院,四川 成都 6 1 0 2 2 5)摘 要:针对传统A*算法存在遍历节点数多、转折角度大和搜索速度慢的问题,提出基于拟合优先搜索的多场景自适应改进A*算法。首先,引入父节点的启发距离以减少遍历节点数和提高搜索速度,并量化场景地图信息,利用自适应控制原理实现启发权重的适时调整,以增强算法鲁棒性;其次,采用拟合优先搜索策略,进一步增强算法的启发性;接着,通过局部剪枝和冗余节点删除对路径进行平滑处理,减少遍历节点数和转折角度;最后,进行仿真测试。测试结果表明,所提算法遍历节点数更少、转折角度更小、搜索速度更快。关键词:A*算法;路径规划;自适应;拟合优先;路径平滑中图分类号:T P 2 4 2文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 4.0 1.0 1 5A m u l t i-s c e n e a d a p t i v e A*a l g o r i t h m b a s e d o n f i t t i n g-f i r s t s e a r c hS HE N K e-y u,YOU Z h i-y u,L I U Y o n g-x i n(C o l l e g e o f E l e c t r i c a l E n g i n e e r i n g,S o u t h w e s t M i n z u U n i v e r s i t y,C h e n g d u 6 1 0 2 2 5,C h i n a)A b s t r a c t:A i m i n g a t t h e p r o b l e m s o f l a r g e n u m b e r o f t r a v e r s a l n o d e s,l a r g e t u r n i n g a n g l e,a n d s l o w s e a r c h s p e e d o f t h e t r a d i t i o n a l A*a l g o r i t h m,a m u l t i-s c e n e a d a p t i v e i m p r o v e m e n t A*a l g o r i t h m b a s e d o n f i t t i n g-f i r s t s e a r c h i s p r o p o s e d.F i r s t l y,t h e h e u r i s t i c d i s t a n c e o f t h e p a r e n t n o d e i s i n t r o d u c e d t o r e-d u c e t h e n u m b e r o f t r a v e r s a l n o d e s a n d i m p r o v e t h e s e a r c h s p e e d,t h e s c e n e m a p i n f o r m a t i o n i s q u a n t i-f i e d,a n d t h e a d a p t i v e c o n t r o l p r i n c i p l e i s u s e d t o a c h i e v e t h e t i m e l y a d j u s t m e n t o f t h e h e u r i s t i c w e i g h t t o e n h a n c e t h e r o b u s t n e s s o f t h e a l g o r i t h m.S e c o n d l y,t h e h e u r i s t i c s t r a t e g y o f f i t t i n g-f i r s t s e a r c h i s u s e d t o f u r t h e r e n h a n c e t h e h e u r i s t i c o f t h e a l g o r i t h m.T h i r d l y,t h e p a t h i s s m o o t h e d t h r o u g h l o c a l p r u n i n g a n d r e d u n d a n t n o d e d e l e t i o n t o r e d u c e t h e n u m b e r o f t r a v e r s e d n o d e s a n d t h e t u r n i n g a n g l e.F i n a l l y,a s i m u-l a t i o n t e s t i s c a r r i e d o u t o n M a t l a b,a n d t h e t e s t r e s u l t s s h o w t h a t t h e p r o p o s e d a l g o r i t h m h a s f e w e r t r a v e r s e d n o d e s,s m a l l e r t u r n i n g a n g l e,a n d f a s t e r s e a r c h s p e e d.K e y w o r d s:A*a l g o r i t h m;p a t h p l a n n i n g;a d a p t i v e;f i t t i n g-f i r s t;p a t h s m o o t h i n g1 引言近年来,移动机器人技术已经逐渐替代传统人工作业,被广泛应用到工业、服务业、城市安全和空间探测等领域。路径规划是移动机器人任务管理系统的关键技术之一,是指在有障碍物的工作环境中规划出一条从起始节点到目标节点的无碰撞路径,并使规划路径满足某些优化原则(如搜索速度更快、路径距离更短等)成为最优路径1。根据对场景地图信息掌握的程度,无人驾驶机器人路径规划可分为局部路径规划和全局路径规划2,3。局部路径规划需要硬件设备能实时采集周围场景地图信息,对环境误差和噪声有较高的鲁棒性。全局*收稿日期:2 0 2 2-0 4-2 8;修回日期:2 0 2 2-0 8-3 1基金项目:成都市科技项目(2 0 2 1-R K 0 0-0 0 0 7 9-Z F);西南民族大学中央高校基本科研业务费专项资金(2 0 2 1 1 0 1)通信作者:游志宇(y o u z h i y us w u n.e d u.c n)通信地址:6 1 0 2 2 5 四川省成都市双流区西南民族大学电气工程学院A d d r e s s:C o l l e g e o f E l e c t r i c a l E n g i n e e r i n g,S o u t h w e s t M i n z u U n i v e r s i t y,S h u a n g l i u D i s t r i c t,C h e n g d u 6 1 0 2 2 5,S i c h u a n,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 6卷第1期2 0 2 4年1月 V o l.4 6,N o.1,J a n.2 0 2 4 文章编号:1 0 0 7-1 3 0 X(2 0 2 4)0 1-0 1 4 2-0 8路径规划基于先验全局地图信息,规划出的路径精度取决于获取的场景地图信息的准确度。在全局路径规划算法中,基于启发式搜索的A*算法4,5拥有出色的路径最优性、寻路完备性和搜索高效性,多被应用于静态场景地图的路径规划中,一直是研究人员研究改进的重点。文献6 通过改变距离计算方式与函数权重来缩短寻路时间、减少冗余节点数量。文献7 将切比雪夫距离作为启发式函数因子,同时引入父节点增强其影响力,使得搜索速度极大提升。文献8 通过扩展到2 0搜索邻域,并设置了安全距离,使规划出的路径更平滑且距离更短。文献9 设计了新型距离计算方式,使得最终规划出的路径距离更短。文献1 0 针对复杂场景地图引入安全因子使路径尽量避开危险区域,适用于机器人运行。文献1 1,1 2 都采用双向搜索方式以增强算法实时性,文献1 2 还引入了扇形邻域扩展,使搜索更有导向性。文献1 3 利用模拟退火法取代传统算法的距离判断方式,使得搜索更快地向目标节点进行。文献1 4 通过引进时间因子对估价函数进行改进,使得改进算法可以节约规划时间、降低路程成本。文献1 5 在传统A*算法中引入动态窗口法,提升路径平滑处理的灵活性并满足移动机器人非完整性约束条件。从上述文献中可以看出,对A*算法的改进主要包括优化距离计算函数、扩展邻域以及与其它智能算法相结合,但这些改进的普适性和鲁棒性较弱,且部分对计算机性能要求较高。本文针对部分文献中的改进A*算法存在鲁棒性差、遍历节点数多、路径转折角度较大和搜索速度较慢的问题,基于传统A*算法,在二维静态环境下以移动机器人为载体,提出一种兼顾算法鲁棒性和普适性且计算效率较高的基于拟合优先搜索的多场景自适应改进A*算法。首先,通过自适应控制机制实现启发式搜索,根据地图变化适时调整权重。其次,引入拟合优先搜索,增强算法的启发性。接着,通过路径剪枝和冗余节点删除机制,对路径进行导向规划和平滑处理。在相同栅格场景地图中,传统A*算法与本文改进A*算法的仿真结果表明,本文改进A*算法在路径规划时遍历节点更少、路径更平滑、搜索速度更快,对多场景地图具有更强的鲁棒性和普适性。2 传统A*算法A*算法是由H a r t等人4提出的,在D i j k s t r a算法基础上发展而来。它根据定义的代价函数在静态环境中寻找一条从起始位置到目标位置的最小移动距离路径,其代价函数表达式如式(1)所示:f(n)=g(n)+h(n)(1)其中,n表示当前节点所在位置;f(n)表示从起始节点位置到当前节点位置的代价函数;g(n)表示移动机器人从起始节点位置到当前节点位置的实际移动代价;h(n)表示从当前节点位置到目标节点位置的预估移动代价,称为启发式函数。在路径规划时,若h(n)远小于g(n),此时A*算法近似于D i j k s t r a算法,遍历节点会增多,搜索速度将大大降低;若h(n)远大于g(n),此时A*算法约等于最佳优先搜索算法,搜索速度提高,但容易出现局部最优解。因此,选择合适的启发式函数h(n)将会影响A*算法的规划性能。常用的h(n)计算方法有欧几里得距离(E u-c l i d e a n D i s t a n c e)、曼 哈 顿 距 离(M a n h a t t a n D i s-t a n c e)和对角线距离(D i a g o n a l D i s t a n c e)。假设起点坐标为(s1,s2),终点坐标为(g1,g2),则欧几里得距离的计算公式如式(2)所示:h=(s1-g1)2+(s2-g2)2(2)曼哈顿距离的计算公式如式(3)所示:h=s1-g1+s2-g2(3)对角线距离的计算公式如式(4)所示:h=1.4D i a g o n a l+(S t r a i g h t-2D i a g o n a l)(4)其中,D i a g o n a l=m i n(|s1-g1|,|s2-g2|),S t r a i g h t=|s1-g1|+|s2-g2|。由于欧几里得距离的计算精度高于曼哈顿距离和对角线距离的,得出最优路径的可能性更大,故A*算法选取欧几里得距离进行移动代价预估。3 改进A*算法传统A*算法在进行路径规划时,需要遍历的节点数较多、搜索速度慢、鲁棒性较差,而且规划出的路径存在许多冗余节点,路径总转折角过大而不适合移动机器人运动学原理,这些不足都限制了A*算法的应用。本文从自适应权重调整、拟合优先搜索以及局部剪枝与冗余节点删除这3个方面对传统A*算法进行改进,以保证改进后算法最终规划出的路径相对最优,增强鲁棒性和搜索效率,减少遍历节点数和总转折角度,从而缓解移动机器人的存储压力,降低能源损耗。341沈克宇等:基于拟合优先搜索的多场景自适应改进A*算法3.1 自适应权重调整传统A*算法在遍历节点时存在循环访问判断的情况,搜索效率较低。因此,本文引入父节点并增强其启发能力,以减少遍历节点数,同时提高搜索速度。为了增强算法的鲁棒性和普适性,同时避免因启发函数过强导致规划出的路径出现更多局部最优解,本文设计了能随场景地图变换的自适应权重W,如式(5)所示:W=(1-l n P)2(5)在规划之前先量化标定障碍物所在栅格,将栅格地图中可通行节点总数记作S u m0,障碍物节点总数记作S u m1,则式(5)中的P表示起始节点到目标节点所围地图的障碍物分布率,其计算如式(6)所示:P=S u m1S u m0+S u m1(6)在场景地图发生变化时,障碍物分布率P也会变化,此时自适应权重W会随P的改变而自适应地调整,使之能适应多种场景地图,此时能够进行自适应权重调整的启发式函数h(n)如式(7)所示:h(n)=Wh(n)+h(n-1)(7)其中,(n-1)表示当前节点位置n的父节点所在位置。为了验证增加了自适应权重调整的启发式函数在遍历节点和搜索速度上的性能,在图1所示3 03 0栅格地图中进行对比测试,相关结果如表1所示。T a b l e 1 R e s u l t s c o m p a r i s o n o f t r a d i t i o n a l A*a l g o r i t h m a n d t h e a l g o r i t h m w i t h a d a p t i v e w e i g h t a d j u s t m e n t 表1 传统A*算法和增加自适应权重调整的算法测试结果对比算法遍历节点/个寻路时间/s传统A*算法3 2 10.8 1 4增加自适应权重调整的A*算法5 00.1 6 4 图1中,圆形为起始节点,五角星为目标节点,黑色为障碍物,灰色节点为遍历且收录的节点,浅灰色为在判断后丢弃的节点,黑色实线为最终路径。根据图1和表1的数据可知,增加自适应权重调整的A*算法所遍历的节点数远少于传统A*算法的,且寻路时间更短。3.2 拟合优先搜索传统A*算法的搜索范围为4邻域或图2 a中F i g u r e 1 C o m p a r i s o n o f t r a d i t i o n a l A*a l g o r i t h m a n d t h e a l g o r i t h m w i t h a d a p t i v e w e i g h t a d j u s t m e n t 图1 传统A*算法与增加自适应权重调整的A*算法对比的8邻域。研究人员针对搜索邻域的扩增与缩减展开研究,当邻域增大为1 6邻域甚至无穷大时,能保证寻路最优,但搜索速度变慢;当缩减邻域到3邻域甚至单向搜索时,搜索速度提高但无法保证寻路最优,且可能搜索失败。由此可见,无论是扩大邻域还是缩减邻域,都有一定的局限性,故本文并没有针对可扩展邻域的数量进行改进,而是重新设计传统8邻域中的动态规划矩阵M o t i o n。记(d x,d y)为当前节点与邻接节点之间横纵坐标的变化数值,S(i)为从当前节点到邻接节点的单步移动距离,此时的动态规划矩阵如式(8)所示:M o t i o n=d x,d y,S(i)(8)F i g u r e 2 T r a d i t i o n a l 8 n e i g h b o r h o o d s s e a r c h a n d i t s l i m i t a t i o n s图2 传统8邻域搜索与其局限性441C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)如图2 b所示,以目标节点为中心,向外画圆时,搜索过程中会出现h(n)相等的情况。由于A*算法是基于最小移动距离原理进行路径搜索,所以当h(n)相等时,g(n)将占据算法的主导位置,起到引导搜索方向的决定性作用。故本文提出拟合优先搜索策略,通过对搜索邻域分配优先级,以增强g(n)的搜索启发性,如图3所示。当移动方向靠近搜索方向时,实际移动距离变小,此时寻优路径向最优方向拟合,搜索速度得到提升。图3中,黑色虚线表示从起始节点(父节点)到目标节点的搜索向量,黑色实线为从起始节点向子节点的移动向量,向量间的夹角记作。F i g u r e 3 V e c t o r a n g l e r e p r e s e n t a t i o n图3 向量夹角表示记a=(a x,a y),b=(b x,b y),向量间夹角的余弦如式(9)所示:c o s=abab=a xb x+a yb y(a x)2+(a y)2(b x)2+(b y)2(9)根据搜索向量与移动向量的位置关系,本文对传统8邻域的动态规划矩阵M o t i o n进行设计。由式(9)可知,向量间夹角越小,其移动方向与最优搜索方向越拟合,故设计关于c o s 的函数作为搜索邻域时单步移动距离S(i)的权重,确保在寻路过程中优先选择与搜索向量拟合的邻域,从而增强g(n)的启发性和导向性,提高搜索速度。但该函数取值应该适中,若是过大则无法用于复杂地图环境,若是过小则路径优化不够明显。改进后的S(i)如式(1 0)所示:S(i)=(1-c o s)/8+1S(i)=(1-c o s)/8+1(d x)2+(d y)2(1 0)此时扩展邻域并分配优先级的g(n)动态规划矩阵如式(1 1)所示:M o t i o n=d x,d y,S(i)(1 1)由式(1)及A*算法寻路原理可得拟合优先搜索f(n)如式(1 2)所示:f(n)=ni=1S(i)+h(n)(1 2)在图1的场景地图中进行验证,测试结果如图4所示。图4中黑色实线为在自适应权重调整基础上增加拟合优先搜索策略后规划出的路径。与图1 b对比,图4中灰色栅格覆盖面积更少,可以看出路径向目标节点拟合程度较高。结果表明,遍历节点数比表1中自适应权重调整算法的减少1 0个,寻路时间由表1中的0.1 6 1 s减少到0.1 4 2 s,此时算法搜索效率更高。可见在自适应权重调整算法的基础上对其进行优先拟合搜索使得改进A*算法的性能更为优越。F i g u r e 4 T e s t r e s u l t o f a l g o r i t h m i n t r o d u c i n g f i t t i n g-f i r s t s e a r c h 图4 引入拟合优先搜索的算法测试结果3.3 局部剪枝与冗余节点删除从图4中可以明显看到,路径存在局部最优解,而且经过了大量的冗余节点,故还需要对之前规划出的路径进行平滑处理。首先通过局部剪枝去除路径上的局部最优解,之后再删除路径上的冗余节点,以保证最终规划出的路径经过的节点数更少且路径更为平滑。3.3.1 局部剪枝因为场景地图中存在多种障碍物分布情况以及8邻域搜索的角度局限性,故可能出现三角形和梯形局部冗余。即使是更复杂的局部冗余路径,也可以先将三角形剪枝为梯形,再对梯形剪枝,从而形成平滑路径。图5 a所示为三角形局部冗余路径,图5 b为梯形局部冗余路径。其中,灰色圆球代表的a、b、c、d均是路径上相邻的节点,黑色为障碍物。图5 a中若需要从a点到达c点,可以直接从a到c,并不需要经过中间节点b。图5 b中若需要从a点到达d点,可以直接从a到d,并不需要经过中间节点b和c。图5的三角形和梯形路径存在局部最优解,导致全局路径无法最优,因此需要对局部冗余路径进行剪枝处理,以避免出现局部最优。记4个相邻节点a、b、c、d的坐标分别为(a1,a2),(b1,b2),541沈克宇等:基于拟合优先搜索的多场景自适应改进A*算法(c1,c2)和(d1,d2)。F i g u r e 5 S c h e m a t i c o f l o c a l r e d u n d a n t p a t h s图5 局部冗余路径示意图对于图5 a的三角形局部冗余路径,将从a到b的向量记作A B,将从b到c的向量记作B C,将从a到c的向量记作A C。本文采用8搜索邻域进行路径规划,一旦路径出现三角形局部最优的情况,该三角形一定是等腰直角三角形,此时可以通过坐标位置关系或向量垂直原理进行判断。向量垂直判断函数如式(1 3)所示:J u d g e_T r i=(A BB C)(A CB C)(A CA B)(1 3)若J u d g e_T r i为0,表示此时路径可能存在三角形局部冗余,需要对路径进行判断:若对局部最优路径剪枝后经过障碍物,不处理;若a与c可直连且未经障碍物,可以直接沿着从a到c的方向剪枝。剪枝完三角形局部冗余后,再对梯形冗余进行剪枝操作。记从a到d的向量A D=(d1-a1,d2-a2),从b到c的向量记作B C=(c1-b1,c2-b2)。通过向量平行原理判断路径中的梯形冗余,其判断函数如式(1 4)所示:J u d g e_T r a=(d1-a1)(c2-b2)-(d2-a2)(c1-b1)(1 4)若J u d g e_T r a为0,说明此时局部路径呈梯形,需要对从a到d的节点进行判断。若经过障碍物不处理,否则直接对路径剪枝。为验证路径剪枝的有效性,针对图1所示地图进行剪枝处理仿真测试,测试结果如图6所示。其中虚线为原始路径,实线为剪枝后路径。从图6中可知,剪枝可以有效解决复杂地图中出现的局部最F i g u r e 6 P a t h p r u n i n g d e m o n s t r a t i o n图6 路径剪枝演示优路径的问题。3.3.2 冗余节点删除剪枝完成后,还需要对路径上的冗余节点进行处理,从而减少路径经过的节点数,使得最终路径更平滑。首先,计算初始路径中邻近3个节点间的位置关系,通过向量共线原理判断并存储路径中的拐点;接着,依次判断邻近4个拐点是否可以直连,直连后若未经过障碍物且总距离最短,则记录该拐点位置,并删除初始路径中位于直连拐点之间的冗余节点;随后,以记录拐点为起点,再与随后3个邻近拐点进行直连判断,直到目标节点为止。更新路径节点作为新规划路径,再次循环判断,直到路径上没有冗余节点,此时得到的路径即为最终路径。冗余节点删除原理示意图如图7 a所示,图中ABCD为规划出的路径。假设AD、AC和BD均未经过障碍物,可直接得出AD为最优路径。若AD经过 障碍物,再比 较ACD与ABD这2条路径的总距离,距离最小的为最优路径。为验证路径剪枝和冗余节点删除策略的有效性,在图4场景中进行路径规划测试,结果如图7 b所示。其中,虚线为初始路径,实线为经过路径剪枝与冗余节点删除之后的路径,深灰色方格表示最终经过的节点。从图7 b中可知,删除冗余节点后的规划路径需要存储的遍历节点数大大减少,路径更为平滑,641C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)经过的节点数也更少。此时仅需要记忆几个拐点就可以规划出完整的路径,有效缓解了移动机器人的存储压力。F i g u r e 7 R e m o v i n g r e d u n d a n t n o d e p r i n c i p l ea n d p a t h s m o o t h i n g t e s t图7 删除冗余节点原理与路径平滑测试4 实验仿真为了验证本文改进A*算法的优越性,在I n-t e l C o r eTM i 5-7 3 0 0 HQ C P U 2.5 0 GH z计算机上利用MAT L A B 2 0 2 0 b对传统A*算法和本文改进A*算法进行仿真测试。在图8所示的3种场景中进行路径规划,图中黑色虚线表示传统A*算法规划出的路径,黑色实线为本文改进A*算法规划出的路径。相关仿真实验结果如表2所示。T a b l e 2 E x p e r i m e n t a l r e s u l t s o f p a t h p l a n n i n g i n f i g u r e 8表2 图8中路径规划实验结果地图遍历节点/个传统A*算法本文改进算法总转折角/()传统A*算法 本文改进算法寻路时间/s传统A*算法本文改进算法 图8 a1 2 32 63 2 1.2 8 3 2 4 7.4 8 9 60.2 8 10.2 3 9图8 b3 2 14 06 0 6.9 9 1 1 2 8 0.8 9 4 70.8 1 70.2 8 4图8 c1 3 52 73 6 0.0 0 0 0 6 8.7 4 9 50.2 9 50.2 4 1 从本文改进A*算法与传统A*算法在以上3种不同场景地图中的规划路线和表2中相关数据可知,本文改进A*算法鲁棒性和实时性更强,能适应多种场景地图,且规划出的路径更优。F i g u r e 8 T e s t r e s u l t s o f t h e p r o p o s e d i m p r o v e d A*a l g o r i t h m i n d i f f e r e n t m a p s图8 本文改进A*算法在不同场景地图中的测试结果为了进一步论述本文改进A*算法的优越性和稳定性,在模仿小区环境构建的5 05 0栅格地图中选取5组不同起始节点和目标节点进行测试,分别为 (7,7),(4 2,4 3),(7,4 7),(4 7,7),(3 7,3 3),(1 4,1 3),(2 6,2 5),(7,1 8),(4 9,7),(1 3,4 7)。以第1组起始节点与目标节点为例,分别使用传统A*算法、文献6 改进A*算法和本文改进A*算法进行路径搜索,最终规划出的路径如图9所示。5组不同起始节点和目标节点测试的相关结果如表3所示。根据表3可知,本文改进A*算法与传统A*算法和文献6 改进A*算法相比,遍历节点数平均减少了7 2.1 9%和2 8.3 6%,在删除冗余节点后极大缓解了计算机存储压力;总转折角度平均减少了6 4.3 3%和2 8.5 9%,规划出的路径更为平滑,降低了移动机器人与障碍物发生碰撞的几率;寻路时间平均减少了6 8.5 1%和2 7.1 5%,实时性更强,741沈克宇等:基于拟合优先搜索的多场景自适应改进A*算法F i g u r e 9 T e s t r e s u l t s o f d i f f e r e n t p a t h p l a n n i n g a l g o r i t h m s图9 不同路径规划算法测试结果T a b l e 3 T e s t i n g r e s u l t s o f f i v e d i f f e r e n t s t a r t i n g a n d t a r g e t n o d e s表3 5组不同起始节点和目标节点测试结果序号遍历节点/个传统A*算法文献6改进A*算法本文改进A*算法总转折角/()传统A*算法文献6改进A*算法本文改进A*算法寻路时间/s传统A*算法文献6改进A*算法本文改进A*算法11 2 4 94 5 21 2 45 1 3.8 4 9 62 5 1.0 5 1 01 7 4.8 0 5 65.9 4 61.7 6 40.5 7 926 5 51 1 77 14 3 7.4 3 3 61 9 2.7 1 6 71 6 5.5 2 9 72.4 1 80.4 6 40.3 2 731 7 13 13 14 0 5.0 0 0 01 7 2.7 4 6 81 2 5.9 9 7 50.5 4 70.2 1 80.1 8 645 0 43 7 13 1 35 8 8.1 4 1 63 3 8.8 7 4 02 0 2.2 0 4 61.6 0 21.2 0 31.0 8 059 4 64 2 03 6 04 0 5.0 0 0 02 4 0.9 4 5 41 6 6.0 6 6 94.1 9 81.6 0 31.3 7 6搜索速度更快,一定程度上解决了机器人在转弯时额外产生的能源损耗和时间等待问题。5 结束语本文针对传统A*算法存在遍历节点数较多、总转折角度过大和搜索速度较慢等不足,提出了基于拟合优先搜索的多场景自适应改进A*算法。首先,引入父节点的启发距离,设计能自适应地图变化的启发式搜索权重,以减少遍历的节点数,提高搜索速度;然后,引入拟合优先搜索进一步增强算法启发性;最后,对初步规划出的路径进行局部剪枝并删除冗余节点,最后得出最终路径。仿真测试结果表明,本文提出的改进A*算法的鲁棒性更强,遍历节点数更少,路径更平滑,搜索速度更快,更适用于移动机器人的日常工作。参考文献:1 朱大奇,颜明重.移动机器人路径规划技术综述J.控制与决策,2 0 1 0,2 5(7):9 6 1-9 6 7.Z h u D a-q i,Y a n M i n g-z h o n g.S u r v e y o n t e c h n o l o g y o f m o b i l e r o b o t p a t h p l a n n i n gJ.C o n t r o l a n d D e c i s i o n,2 0 1 0,2 5(7):9 6 1-9 6 7.2 鲍庆勇,李舜酩,沈峘,等.自主移动机器人局部路径规划综述J.传感器与微系统,2 0 0 9,2 8(9):1-4.B a o Q i n g-y o n g,L i S h u n-m i n g,S h e n H u a n,e t a l.S u r v e y o f l o-c a l p a t h p l a n n i n g f o r a u t o n o m o u s m o b i l e r o b o tJ.T r a n s d u c-e r a n d M i c r o s y s t e m T e c h n o l o g i e s,2 0 0 9,2 8(9):1-4.3 陆新华,张桂林.室内服务机器人导航方法研究J.机器人,2 0 0 3,2 5(1):8 0-8 7.L u X i n-h u a,Z h a n g G u i-l i n.S u mm a r i z a t i o n o n i n d o o r s e r v i c e r o b o t n a v i g a t i o nJ.R o b o t,2 0 0 3,2 5(1):8 0-8 7.4 H a r t p E,N i l s s o n n J,R a p h a e l B.A f o r m a l b a s i s f o r t h e h e u-r i s t i c d e t e r m i n a t i o n o f m i n i m u m c o s t p a t h sJ.I E E E T r a n-s a c t i o n s o n S y s t e m s S c i e n c e a n d C y b e r n e t i c s,1 9 6 8,4(2):1 0 0-1 0 7.5 M a c T T,C o p o t C,T r a n D T,e t a l.H e u r i s t i c a p p r o a c h e s i n r o b o t p a t h p l a n n i n g:A s u r v e yJ.R o b o t i c s a n d A u t o n o m o u s S y s t e m s,2 0 1 6,8 6:1 3-2 8.6 王中玉,曾国辉,黄勃.基于改进双向A*的移动机器人路径规划算法J.传感器与微系统,2 0 2 0,3 9(1 1):1 4 1-1 4 3.W a n g Z h o n g-y u,Z e n g G u o-h u i,H u a n g B o.M o b i l e r o b o t p a t h p l a n n i n g a l g o r i t h m b a s e d o n i m p r o v e d b i d i r e c t i o n a l A s t a rJ.T r a n s d u c e r a n d M i c r o s y s t e m T e c h n o l o g i e s,2 0 2 0,3 9(1 1):1 4 1-1 4 3.7 刘生伟,马钺,孟树峰,等.改进A*算法的A GV路径规划J.计算机应用,2 0 1 9,3 9(S 2):4 1-4 4.L i u S h e n g-w e i,M a Y u e,M e n g S h u-f e n g,e t a l.I m p r o v e d A*a l g o r i t h m f o r p a t h p l a n n i n g o f AGVJ.J o u r n a l o f C o m p u t e r A p p l i c a t i o n s,2 0 1 9,3 9(S 2):4 1-4 4.8 Y u J W,H o u J,C h e n G.I m p r o v e d s a f e t y-f i r s t A-s t a r a l g o-r i t h m f o r a u t o n o m o u s v e h i c l e sC P r o c o f t h e 2 0 2 0 5 t h I n-t e r n a t i o n a l C o n f e r e n c e o n A d v a n c e d R o b o t i c s a n d M e c h a-t r o n i c s,2 0 2 0:7 0 6-7 1 0.9 C h u n Y J,L u o Q H,Y a n X Z.P a t h p l a n n i n g u s i n g a n i m-841C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 4,4 6(1)p r o v e d A-s t a r a l g o r i t h mC P r o c o f t h e 2 0 2 0 1 1 t h I n t e r n a-t i o n a l C o n f e r e n c e o n P r o g n o s t i c s a n d S y s t e m H e a l t h M a n a g e-m e n t,2 0 2 0:2 3-2 6.1 0 Z h a n g H M,L i M L,Y a n g L.S a f e p a t h p l a n n i n g o f m o b i l e r o b o t b a s e d o n i m p r o v e d A*a l g o r i t h m i