![点击分享此内容可以赚币 分享](/master/images/share_but.png)
基于改进D*Lite的二维路径连续动态规划算法.pdf
《基于改进D*Lite的二维路径连续动态规划算法.pdf》由会员分享,可在线阅读,更多相关《基于改进D*Lite的二维路径连续动态规划算法.pdf(10页珍藏版)》请在咨信网上搜索。
1、1042Radio Communications TechnologyVol.49 No.6 2023doi:10.3969/j.issn.1003-3114.2023.06.008引用格式:傅亮,刘峰,刘书勇,等.基于改进 DLite 的二维路径连续动态规划算法J.无线电通信技术,2023,49(6):1042-1051.FU Liang,LIU Feng,LIU Shuyong,et al.Two-dimensional Path Continuous Dynamic Programming Algorithm Based on Improved DLiteJ.Radio Communic
2、ations Technology,2023,49(6):1042-1051.基于改进 DLite 的二维路径连续动态规划算法傅 亮1,刘 峰2,刘书勇2,韩新宇2(1.中国航空无线电电子研究所 民机航电系统部,上海 200241;2.哈尔滨工程大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)摘 要:广泛应用于路径规划问题的 DLite 存在运行速度慢、容易斜穿障碍物边界节点且只能执行单次动态路径重构等问题。基于此,引入人工势场(Artificial Potential Field,APF)引力场的思想,提出了一种在既定路线上持续产生突变障碍的连续动态路径规划 DLite 改进算法(
3、Continuous DLite,CDLite)。对原始切比雪夫代价估计算子进行改进,优化路线斜走与非斜走实际代价。引入引力算子,提出一种全域代价估计算子改进键值算子。对规避障碍物提出一种方向禁忌矩阵,避免斜穿危险节点。基于冗余点删除机制规划路线进行优化,生成较为光滑的折线。实验结果表明,CDLite 基于多规模栅格地图均成功预规划路线,且运行时间相较实验对比算法减少约 35%,在连续动态规划模式中相较实验对比算法减少约 60%。关键词:DLite;路径规划;人工势场;栅格法;连续动态规划中图分类号:TP301.6 文献标志码:A 开放科学(资源服务)标识码(OSID):文章编号:1003-3
4、114(2023)06-1042-10Two-dimensional Path Continuous Dynamic Programming Algorithm Based on Improved DLiteFU Liang1,LIU Feng2,LIU Shuyong2,HAN Xinyu2(1.Civil Aircraft Avionics Department,Chinese Aeronautical Radio Electronics Research Institute,Shanghai 200241,China;2.College of Computer Science and T
5、echnology,Harbin Engineering University,Harbin 150001,China)Abstract:DLite,which is widely used in path planning,has some problems,such as slow running speed,tending to cross obsta-cle boundary nodes,and being able to only perform a single dynamic path reconstruction.Based on this,an idea of Artific
6、ial Potential Field(APF)gravitational field is introduced,and a dynamic path planning Continuous DLite(CDLite)improved algorithm that continuously produces abrupt obstacles on a given route is proposed.The original Chebyshev cost estimation operator is improved to opti-mize actual cost of oblique an
7、d non-oblique routes.By introducing the gravitational operator,a global cost estimation operator is proposed to improve the key value operator.A directional taboo matrix is proposed to avoid diagonally passing through dangerous nodes.Finally,based on the redundant point deletion machine value,the pl
8、anning route is optimized to generate a smoother broken line.Experimental results show that CDLite successfully pre-plans routes based on multi-scale grid maps,and the running time is reduced by about 35%compared with other algorithms,and about 60%compared with other algorithms in continuous dynamic
9、 planning mode.Keywords:DLite;route plan;artificial potential field;gird-based method;continuous dynamic programming收稿日期:2023-08-10基金项目:黑龙江省自然科学基金(JJ2019LH2160);国防基础科研项目(JCKY2021604B002)Foundation Item:Heilongjiang Provincial Natural Science Foundation of China(JJ2019LH2160);National Defense Basic R
10、esearch Project(JCKY2021604B002)2023年第49卷第6期无线电通信技术10430 引言路径规划1是让目标对象基于环境模型下寻找一条经过起止节点的无碰撞障碍物的安全路线优化问题,它广泛应用于移动机器人、空中无人机、自动驾驶车辆、水面无人艇等领域2-8。基于规划模式可划分为静态路径规划与动态路径规划两大类。静态路径规划常用算法有图搜索算法9-11和智能优化算法。图搜索算法如 Dijkstra、A、RRT 等,智能优化算法如蚁群算法、遗传算法、粒子群算法、蝙蝠算法等12-15。静态路径规划算法实施要求之一是需要全区域的地形信息,对未知地形则不具备规划能力。为解决在未知
11、领域进行路线搜索的问题,提出了动态路径规划算法,如 D、LPA、DLite 等16-18。DLite 算法是融合 D和 LPA提出的一种反向搜索的动态路径规划算法,应用在未知环境下进行快速路线搜索,可以对未知突变障碍进行重规划,是一种高效的规划算法,但是它依然存在易受运动物体影响及路径贴近障碍物等问题,因此众多研究学者对其进行了改进。吴涛等人19引入跳点搜索概念,仅对跳点进行访问,能够有效优化路径长度。杜轩等人20结合人工势场(Artificial Potential Field,APF)法对 DLite 规划路线进行重规划,使得目标物体在移动中能够与障碍物保持有效的安全距离,但本身并未对 D
12、Lite 算法进行改进。张毅等人21针对原有 Boustrophedon 单元分解法进行改进重构,提取关键单元,引导正确搜索方向,有效提高规划速度。戴年慧等人22进入安全系数阻止危险节点作为路径优先选择节点以避免斜穿过障碍,导致冗余点过多。以上改进算法仅对预规划路径进行单次动态重构,并没有进行多次重构优化,没有体现动态规划的多样性。针对以上问题,本文提出了一种改进 DLite的二维路径连续动态规划算法(Continuous DLite,CDLite)。本文算法基于栅格法进行环境建模,记nm 矩阵。优化原始 DLite 算法的切比雪夫启发估计函数,使其在估计数值上更加贴近实际路线规划。引入人工势
13、场的引力场概念,作为补充启发估计函数,并提出了一种全域启发估计算子。引入人工势场的斥力场概念,提出了一种方向禁忌矩阵,能够避免斜穿栅格障碍节点。优化重规划模式,使其能够在连续产生动态障碍的条件下对路径进行持续重构。最后引入冗余点删除机制,使得规划路线更加平滑。1 相关工作1.1 DLite 算法DLite18是由 Sven Koenig 和 Maxim Likhachev于 2002 年提出的一种基于 LPA和 D的动态路径规划算法。LPA是一种基于 A和 Dynamic SWSF-FP思想的正向传播增量式动态路径规划算法,但正向搜索会因为很多分支导致效率下降,因此 DLite融入 D的逆向搜
14、索思想,从目标节点反向搜索起始节点,能够有效地减少节点访问次数,减少搜索时间。DLite 是一种起始节点可变化的反向规划算法,因此更适合应用于未知环境或预规划路线突变障碍的情况。DLite 算法通过不断更新节点值执行路径搜索过程,其定义如式(1)所示:keys=k1k2=min(g(s),rhs(s)+h(s,sstart)+kmmin(g(s),rhs(s),(1)式中:keys是由 k1和 k2组成的二维矩阵,表示为 s节点的键值;sstart为当前开始节点,sgoal为目标节点,slast为重构路径之前的 sstart节点,g(s)为 sgoal节点到s 节点的历史最小实际代价值;rhs
15、(s)为 sgoal节点到s 节点的启发估计值;km 为键值修饰器,是 slast节点到 sstart节点的实际移动距离。DLite 与 LPA最大的不同在于 key 值定义,通过引入 km 因子修饰 key,使得启发估计值的 sstart节点是可变化的,可以减少不必要节点的计算操作,从而大大提高算法效率,也使得 key 值比较对于实际而言更有意义。由式(1)可知 k1由最小实际代价值、启发估计值、键值修饰器累和求得,其具体定义如式(2)(5)所示:g(s)=0,minsSucc(s)(c(s,s)+g(s)s=sgoal,otherwise,(2)rhs(s)=0,minsSucc(s)(c
16、(s,s)+g(s)s=sgoal,otherwise,(3)h(s,sstart)=max(xs-xsstart,ys-ysstart),(4)c(s,s)=(xs-xs)2+(ys-ys)2,(5)1044Radio Communications TechnologyVol.49 No.6 2023式中:Succ(s)为 s 节点的后继节点集合;为单步移动代价;c(s,s)为边缘实际代价函数,即 s 节点到边缘 s节点的欧氏距离,xsysxsys为 s,s的横纵坐标值;h(s,sstart)为 s,sstart的切比雪夫距离,xsysxsstartysstart为 s,sstart的横纵坐
17、标;算法核心在于不断遍历节点并计算 keys放入待检测队列(Priority Queue)。同时由式(2)(3)可知,g(s)和 rhs(s)定义相同,但区别为 g(s)为历史最小值、rhs(s)为当前计算值,取二者最小值用于更新 keys,共计 3 种不确定状态如下所示:若 rhs(s)=g(s),局部一致状态。此状态表示结点 s 处于预估与实际基本没有差错的稳定状态。如无外界影响,将一直保持此状态。若 rhs(s)g(s),则处于局部欠一致状态。此状态表示节点 s 周围节点发生障碍物突变导致旧有解失效,已经收到了附近新障碍物直接或间接的影响,因此需要将其放入优先队列中进行进一步判断。DLi
18、te 算法主要功能包括预规划路径和动态规划路径,具体如下所示:预规划路径:算法初期会通过更新全局地图信息,根据式(1)计算相应扩散节点的 keys,并将其置于优先队列中,然后计算优先队列最小 keys,计算规则为先按照 k1升序排序,再按照 k2升序排序,最后优先队列中首项即为所求,更新该 s 节点的最小实际代价值,根据 3 种局部状态执行相应操作,遍历边缘节点寻找最优 keys作为其前继节点,重复以上操作,直到遍历到 sstart节点,功能结束。动态规划路径:当预规划路径的节点突变为障碍物,会重新计算突变节点的 keys,将受到突变节点影响的所有边缘节点全部置于优先队列中,再执行预规划路径功
19、能,完成单次动态路径规划。1.2 人工势场 人工势场算法是路径规划和局部避障运动中较为常用的方法,该算法的基本思想是在移动点和障碍物周围定义势场,移动点的运动依靠势场力进行驱动。人工势场23是由 Khatib 于 1986 年提出的一种虚拟力场,它将目标与障碍物看作产生引力与斥力的物体,对其投入场内物体使其沿着场内合力方向进行移动。主要方法为建立引力场 Uatt(q)和斥力场 Urep(q),如式(6)(7)所示:Uatt(q)=122(q,qgoal),(6)Urep(q)=121(q,qobs)-10()2,(q,qobs)00,(q,qobs)0,(7)式中:为引力尺度因子,为斥力尺度因
20、子;(q,qgoal)为物体与目标的欧氏距离,(q,qobs)为物体与障碍物的欧氏距离,0为障碍物的影响半径。Uatt(q)和 Urep(q)的负梯度方向即为引力和斥力的方向,负梯度值即为物体受到引力和斥力的值,如式(8)(9)所示:Fatt(q)=-Uatt(q)=(q,qgoal),(8)Frep(q)=-Ureq(q)=1(q,qobs)-10()12(q,qobs)(q,qobs),(q,qobs)00,(q,qobs)0,(9)式中:为引力尺度因子,为斥力尺度因子,(q,qgoal)为物体与目标的欧氏距离,(q,qobs)为物体与障碍物的欧氏距离,0为障碍物的影响半径。2 CDLit
21、e 改进算法2.1 改进启发估计算子 在进行动态路径规划时,针对移动点当前位置附近的节点,使用传统的 DLite 算法来估计启发式值。具体而言,使用切比雪夫距离作为计算方式,该距离是在向量空间中测量两个点之间的一种方法,它定义为两个点在各个坐标上数值差的绝对值中的最大值。切比雪夫距离也被称为棋盘距离,因为它类似于在棋盘上移动棋子的最短步数。在设定的场景中,目标节点周围的邻接节点与目标节点的切比雪夫距离都是 1,这意味着在横向、纵向和斜向移动时,到达邻接节点的代价是相同的。然而,在实际情况中,当目标节点向预定节点移动时,“斜走”“先直走再横走”到达预定节点的代价是不同的。2023年第49卷第6期
22、无线电通信技术1045因此,需要改进传统启发估计算子以匹配实际路径规划的路径代价,基于式(10)(12)对其进行改进。h(s,sstart)=1diffmin+2(diffmax-diffmin),(10)式中:diffmin=min(xs-xsstart,ys-ysstart),(11)diffmax=max(xs-xsstart,ys-ysstart),(12)式中:1为斜走代价加权因子,2为非斜走代价加权因子,xsysxsstartysstart为 s,sstart的横纵坐标,diffmin为 s节点移动到 sstart节点的最短斜走步数,diffmax-diffmin为 s 节点移动到
23、 sstart节点的最短非斜走步数。采用12加权因子区分斜走与非斜走单步代价,可以区分实际规划问题中的斜走距离与非斜走距离的比例,即等腰直角三角形中斜边与直角边的比例,因此设定 1=22。2.2 改进 Key 键值算子2.2.1 引入人工势场引力算子人工势场法定义目标点引力场如式(6)所示,引力场引导移动点向目标点运动,在移动点和目标点间无障碍的理想条件下,移动点和目标点坐标间连线距离始终为最短距离;算法不需要对全局轨迹进行搜索,规划时间短、效率高,满足实时和轨迹生成安全性的要求。定义 hatt(s)为移动点与目标点的启发估计代价如式(13)所示,即引入人工势场引力算子作为补充启发代价算子。h
24、att(s)=(xs-xsgoal)2+(ys-ysgoal)2,(13)式中:为引力尺度因子,xsysxsgoalysgoal为 s,sgoal的横纵坐标。2.2.2 全域启发估计算子DLite 算法的启发估计算子如式(1)所示,通过计算起始点到目标点的代价值标识移动点的启发效果,在局部规划中是一种盲目性的试错路径规划,在复杂环境中带来更多的时间效率损耗。为改进keys键值算子,本文提出全域启发估计算子 hwhole替换 h(s,sstart),如式(14)(15)所示:keys=k1k2=min(g(s),rhs(s)+hwhole+kmmin(g(s),rhs(s),(14)其中:hwh
25、ole=h(s,sstart)+hatt(s),(15)式中:g(s)和 rhs(s)定义如式(2)(3)所示,h(s,sstart)和 hatt(s)定义如式(10)和式(13)所示。式(1)中 h(s,sstart)为 s,sstart的切比雪夫距离,由 2.1 节可知 hwhole内 h(s,sstart)算子改进 h(s,sstart)算子的实际路径规划路径代价,提升规划路径精度;由2.2.1 节可知,hwhole内新增的 hatt(s)算子引导移动点始终向目标点方向移动,不必通过分别计算邻域 8 个方向的结果后做方向选择,加快算法收敛速度。2.3 引入方向禁忌矩阵DLite 算法在规
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 Lite 二维 路径 连续 动态 规划 算法
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。