基于拟合优先搜索的多场景自适应改进A*算法.pdf
《基于拟合优先搜索的多场景自适应改进A*算法.pdf》由会员分享,可在线阅读,更多相关《基于拟合优先搜索的多场景自适应改进A*算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、 基于拟合优先搜索的多场景自适应改进A*算法*沈克宇,游志宇,刘永鑫(西南民族大学电气工程学院,四川 成都 6 1 0 2 2 5)摘 要:针对传统A*算法存在遍历节点数多、转折角度大和搜索速度慢的问题,提出基于拟合优先搜索的多场景自适应改进A*算法。首先,引入父节点的启发距离以减少遍历节点数和提高搜索速度,并量化场景地图信息,利用自适应控制原理实现启发权重的适时调整,以增强算法鲁棒性;其次,采用拟合优先搜索策略,进一步增强算法的启发性;接着,通过局部剪枝和冗余节点删除对路径进行平滑处理,减少遍历节点数和转折角度;最后,进行仿真测试。测试结果表明,所提算法遍历节点数更少、转折角度更小、搜索速度
2、更快。关键词: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
3、 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
4、 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
5、 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
6、 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
7、 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
8、 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
9、 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。局部路径规划需要硬件设备能实时采集周围场景地图信息,
10、对环境误差和噪声有较高的鲁棒性。全局*收稿日期: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
11、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
12、X(2 0 2 4)0 1-0 1 4 2-0 8路径规划基于先验全局地图信息,规划出的路径精度取决于获取的场景地图信息的准确度。在全局路径规划算法中,基于启发式搜索的A*算法4,5拥有出色的路径最优性、寻路完备性和搜索高效性,多被应用于静态场景地图的路径规划中,一直是研究人员研究改进的重点。文献6 通过改变距离计算方式与函数权重来缩短寻路时间、减少冗余节点数量。文献7 将切比雪夫距离作为启发式函数因子,同时引入父节点增强其影响力,使得搜索速度极大提升。文献8 通过扩展到2 0搜索邻域,并设置了安全距离,使规划出的路径更平滑且距离更短。文献9 设计了新型距离计算方式,使得最终规划出的路径距离更
13、短。文献1 0 针对复杂场景地图引入安全因子使路径尽量避开危险区域,适用于机器人运行。文献1 1,1 2 都采用双向搜索方式以增强算法实时性,文献1 2 还引入了扇形邻域扩展,使搜索更有导向性。文献1 3 利用模拟退火法取代传统算法的距离判断方式,使得搜索更快地向目标节点进行。文献1 4 通过引进时间因子对估价函数进行改进,使得改进算法可以节约规划时间、降低路程成本。文献1 5 在传统A*算法中引入动态窗口法,提升路径平滑处理的灵活性并满足移动机器人非完整性约束条件。从上述文献中可以看出,对A*算法的改进主要包括优化距离计算函数、扩展邻域以及与其它智能算法相结合,但这些改进的普适性和鲁棒性较弱
14、,且部分对计算机性能要求较高。本文针对部分文献中的改进A*算法存在鲁棒性差、遍历节点数多、路径转折角度较大和搜索速度较慢的问题,基于传统A*算法,在二维静态环境下以移动机器人为载体,提出一种兼顾算法鲁棒性和普适性且计算效率较高的基于拟合优先搜索的多场景自适应改进A*算法。首先,通过自适应控制机制实现启发式搜索,根据地图变化适时调整权重。其次,引入拟合优先搜索,增强算法的启发性。接着,通过路径剪枝和冗余节点删除机制,对路径进行导向规划和平滑处理。在相同栅格场景地图中,传统A*算法与本文改进A*算法的仿真结果表明,本文改进A*算法在路径规划时遍历节点更少、路径更平滑、搜索速度更快,对多场景地图具有
15、更强的鲁棒性和普适性。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算法,遍历节点会
16、增多,搜索速度将大大降低;若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
17、)曼哈顿距离的计算公式如式(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*算法在进行路径规划时,需要遍历的节点数较多、搜索速度慢、鲁棒性较差,而且规划出的
18、路径存在许多冗余节点,路径总转折角过大而不适合移动机器人运动学原理,这些不足都限制了A*算法的应用。本文从自适应权重调整、拟合优先搜索以及局部剪枝与冗余节点删除这3个方面对传统A*算法进行改进,以保证改进后算法最终规划出的路径相对最优,增强鲁棒性和搜索效率,减少遍历节点数和总转折角度,从而缓解移动机器人的存储压力,降低能源损耗。341沈克宇等:基于拟合优先搜索的多场景自适应改进A*算法3.1 自适应权重调整传统A*算法在遍历节点时存在循环访问判断的情况,搜索效率较低。因此,本文引入父节点并增强其启发能力,以减少遍历节点数,同时提高搜索速度。为了增强算法的鲁棒性和普适性,同时避免因启发函数过强导
19、致规划出的路径出现更多局部最优解,本文设计了能随场景地图变换的自适应权重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)表
20、示当前节点位置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*算法和增加自适应权重调整的算法测试结果对比算法遍历节点/个寻
21、路时间/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
22、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)为当前节点与邻接节点之间横纵坐标的变化
23、数值,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所示,以目标节点为中心,向外画圆时,搜索过程中
24、会出现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 向量夹角
25、表示记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)的启发性和导向性,提高搜索速度。但该函数取值应该适中,若是过大则无法用于复杂地图环境,若是过小则路径优化不够明显。改
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 拟合 优先 搜索 场景 自适应 改进 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。