基于蚁群融合D*Lite的动态改航路径规划.pdf
《基于蚁群融合D*Lite的动态改航路径规划.pdf》由会员分享,可在线阅读,更多相关《基于蚁群融合D*Lite的动态改航路径规划.pdf(9页珍藏版)》请在咨信网上搜索。
1、基于蚁群融合 D*Lite 的动态改航路径规划张文1,2,方巍1,3,41(南京信息工程大学计算机学院数字取证教育部工程研究中心,南京210044)2(南京信大气象科学技术研究院有限公司,南京210044)3(南京信息工程大学江苏省大气环境与装备技术协同创新中心,南京210044)4(苏州大学江苏省计算机信息处理技术重点实验室,苏州215006)通信作者:方巍,E-mail:摘要:危险天气下的改航与受限区划设和路径规划算法密切相关,本文针对改航环境构建中 Graham 扫描结果存在较大无效区域,提出分块后并行扫描.针对危险天气的突发性,为了适用于复杂环境,提出在增量式的 D*Lite 全局规划
2、路径基础上智能分割、蚁群算法局部搜索的复合结构动态规划方法.通过改进信息素更新策略解决收敛速度慢、耗时长且易陷入局部最优的缺点.实验结果表明,分块并行 Graham 扫描划设的飞行受限区形状更接近实际,面积缩至原先的 48.1%.改进蚁群融合 D*Lite 的复合结构动态路径规划算法 D*Lite-ACO 兼顾全局与局部,将重规划范围控制到当前位置与目标点间,在路径长度、规划时间和迭代范围上的评价指标分别提升 1.2%、40.7%、66.7%.关键词:危险天气;飞行受限区;路径规划;Graham;蚁群算法引用格式:张文,方巍.基于蚁群融合 D*Lite 的动态改航路径规划.计算机系统应用,20
3、23,32(8):250258.http:/www.c-s- Diversion Path Planning Based on Combination of Ant Colony Optimization and D*LiteZHANGWen1,2,FANGWei1,3,41(EngineeringResearchCenterofDigitalForensics,MinistryofEducation,SchoolofComputer&Software,NanjingUniversityofInformationScience&Technology,Nanjing210044,China)2(
4、NanjingXindaInstituteofMeteorologicalScienceandTechnologyCo.Ltd.,Nanjing210044,China)3(JiangsuCollaborativeInnovationCenterofAtmosphericEnvironmentandEquipmentTechnology,NanjingUniversityofInformationScience&Technology,Nanjing210044,China)4(JiangsuProvincialKeyLaboratoryforComputerInformationProcess
5、ingTechnology,SoochowUniversity,Suzhou215006,China)Abstract:Diversioninsevereweatheriscloselyrelatedtothedesignationofforbiddenareasandpathplanningalgorithms.GiventhelargeinvalidareaintheGrahamscanningresultsintheconstructionofthediversionenvironment,thisstudyproposesadelineationmethodofGrahamparall
6、elscanningaftertheareaisdividedintoblocks.Forthesuddenoccurrenceofsevereweatherandcomplexenvironments,thestudyproposesadynamicprogrammingmethodofcompositestructureconductingintelligentsegmentationandantcolonyalgorithmlocalsearchbasedonincrementalD*Liteglobalplanningpath.Thepheromoneupdatingstrategyi
7、simprovedtosolvetheshortcomingsofslowconvergencespeed,longtimeconsumed,andtendencytofallintolocaloptimum.TheexperimentalresultsshowthattheshapeoftheflightforbiddenareasdesignatedbyGrahamparallelscanningbasedonthedividedblocksisclosertoreality,andtheareaisreducedto48.1%oftheoriginalone.D*Lite-ACO,ani
8、mprovedantcolonyfusionD*Litedynamicpathplanningalgorithmforcompositestructures,takesboththeglobalandlocalareaintoaccountandcontrolsthereplanningrangebetweenthecurrentpositionandthetargetedpoint.Theevaluationmetricsinpathlength,planningtime,and计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Ap
9、plications,2023,32(8):250258doi:10.15888/ki.csa.009196http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:国家自然科学基金面上项目(42075007);灾害天气国家重点实验室开放项目(2021LASW-B19);苏州大学计算机信息处理技术省重点实验室开放项目(KJS2275)收稿时间:2023-02-08;修改时间:2023-03-08;采用时间:2023-03-14;csa 在线出版时间:2023-05-19CNKI 网络首发时间:2023-05-23250研究开发Researchan
10、dDevelopmentiterationrangeareimprovedby1.2%,40.7%,and66.7%,respectively.Key words:severeweather;flightforbiddenarea;pathplanning;Graham;antcolonyoptimization(ACO)21 世纪以来危险天气一直是影响航班正点率的首要原因,当计划航路发生危险天气时,航空公司常采用原地等待的方式,导致大量乘客滞留机场.频繁发生航班延误乃至取消事件,将严重影响民航高效、准时的口碑,同时严重制约空管系统的服务水平和效率.确保安全的前提下,合理进行危险天气下的改航路
11、径规划是提高空域容量,保障航空器飞行安全,减少航班延误以及提升民航经济效益的有效途径1.路径规划算法作为改航路径的求解方法,其准确性以及高效性是影响改航结果的关键2.目前,国内外已有不少学者对危险天气下的改航路径规划算法进行研究.李善梅等人3开发了一种基于蒙特卡罗模拟和改进遗传算法的考虑飞行时间可靠性的规划算法,有效提高了航班改航的效率和安全性;Bojorquez 等人4提出了一种基于图形处理单元的并行计算框架,基于 A*算法在风险承受能力下生成飞行器重新路由计划,并可以从其中找到最小的时间和距离轨迹;Wang 等人5利用改进的自适应蚁群算法研究改航路径的相互联系,对航空器飞行时的空域容量和流
12、量进行匹配,降低了规划误差;Tolstaya 等人6提出结合反向强化学习和基于搜索的运动规划算法,融合人工势场创建了自主空中交通管制,从而确保航空器处于安全状态;向征等人7提出了引入人工势场法改进传统蚁群算法中的启发因子信息从而提高路径规划模型中搜索的有效性;赵元棣等人1利用 A*算法分别对栅格法构建的静态和动态空域环境进行快速改航规划建模,减少了计算复杂度的同时实现了快速合理规划路径;陈可嘉等人8同时考虑等待策略和改航策略,设计了两阶段求解算法,使用遗传算法优化等待时长和改航路径后使用“化曲为直”和“二分法”思想调整改航路径;王莉莉等人9将栅格法与动态规划法相结合,针对平行航路提出通过改航优
13、先权分配机制解决飞行经济和安全冲突问题的改航路径规划方法;朱承元等人10利用几何算法预先规划可选改航路径后,使用改进的离散粒子群优化算法探索最优改航路径;陈万通等人11通过几何法处理危险区域凸多边形,并提出一种面向空管的亚轨道碎片危险区预测与路径规划方法,更利于飞机平稳、高效、安全改航.上述文献多对人工势场法、经典规划算法以及智能优化算法 3 大类改航路径规划求解算法改进.本文的主要贡献可以概括为 3 个方面:1)将分块和并行概念引入到 Graham 扫描凹形片状分布的危险天气边界,使得划设的结果更贴近实际,初始环境构建的合理性将直接提升路径规划算法的效率.2)对蚁群算法的信息素更新策略进行改
14、进,采取实时更新获取信息素初始值代入后续全局性更新策略,加快收敛的同时保持了探索新路径的能力,避免陷入局部最优.3)考虑危险天气的突发性,提出在 D*Lite 全局规划路径基础上智能分割,融合改进蚁群局部搜索的复合结构动态改航路径规划算法 D*Lite-ACO(antcolonyoptimization),充分结合两类算法优势,扬长避短.1改进初始环境建模飞行受限区的划设是试验改航路径规划算法的前提和基础,通常为受雷暴、冰雹、强雨雪等恶劣天气影响的区域,指在危险天气下的飞行限制区(flightforbiddenarea,FFA).民航空管部门通常采用雷达探测数据来分析恶劣天气的分布情况,当雷达
15、回波反射率大于 40dBZ 时,为了确保飞行安全问题,航空器将被禁止穿越该区域.改航还需要对未来的飞行受限区位置进行预测.以实时的天气雷达探测图像数据为基础,对雷达回波图进行外推,划设飞行受限区预测位置.对雷达回波图中反射率大于 40dBZ 的危险天气影响区域边界进行提取如图 1 所示.Graham 扫描划设飞行受限区的原理是以边界点位置为基础,通过不断的循环、迭代获取一个凸多边形的区域边界12.经研究发现,当其处理凹形片状分布或散点状分布的危险天气时,划设的结果与实际受限区偏差较大.因此,本文提出分块并行 Graham 扫描划设飞行受限区的方法.根据民航有关航空器绕飞的规定,在两个雷暴体边界
16、之间的距离小于 20 公里的情况下,航空器必须禁止从两者之间穿越.因此,首先需要对提取的危险天气影响区域边界间距小于 20 公里的部分进行合并.接着,2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发251G1,G2,Gn将合并后的飞行受限区视为一个整体,判断提取区域的顶点坐标所形成的多边形是否存在凹形带状分布区域,倘若存在,为了提高划设精度,则需要对其分块的关键点进行确定;倘若不存在,可直接利用 Graham 算法对合并的危险天气影响区域扫描划设.G1,G2,GnGpGqGpGq确定分块关键点的步骤如下:将提取区
17、域的顶点坐标中形成凹形的位置坐标和连接并对线段作中线并与危险天气影响区域边界相交O(p,q)O(p,q)xGtGkO(p,q)于点,以为中心向 轴垂直方向绘制直线,直线与危险天气影响区域的边界相交于点和.此时,贯穿的直线实现了对合并的危险天气影响区域的分块.对危险天气影响区域进行分块后再并行扫描划设的方法不仅使得划设的结果更精细,减小无效区域面积,而且并行一定程度上也减少了 Graham 扫描划设的时间,提高了效率.分块并行 Graham 扫描划设的处理流程如图 2 所示.(a)雷达基数据图像(b)危险天气影响区域(c)提取危险天气边界图 1基于雷达回波图提取危险区域危险天气影响区域提取边界B
18、lockBlockBlock凸包 1凸包 2凸包 3线程并行线程并行组合外扩飞行受限区图 2分块并行 Graham 扫描处理流程图2复合结构动态改航路径规划算法 2.1 改进信息素更新策略蚁群算法是从自然界蚂蚁觅食行为获得的灵感,是一种启发式群体智能优化算法.研究发现,蚂蚁初始的运动方向是随机的,其经过的路径上会释放出一种物质,称之为信息素,蚂蚁间通过该物质相互交流.蚂蚁将根据信息素浓度来决定来选择下一步的运动方向,信息素浓度越大的路径被选择的机率也就越大,最终能得到一条出发点到目的点最短路径.路径上释放的信息素会逐渐消失,信息素的更新计算如式(1)、式(2)13所示:ij(t+1)=(1)i
19、j(t)+ij(t)(1)ij=mk=1kij(2)(0 1)ijij其中,挥发系数表示路径上信息素的挥发程度,表示栅格 与栅格 路径上的信息素浓度.常用的蚁群算法多采用全局性更新策略,蚂蚁搜索的收敛速度较快,能尽早找出一条拟最优路径.然而,由于全局过早收敛,蚂蚁将会更快地集中在当前循环信息素浓度最高的一条路径上,从而阻碍发现更优解,导致最终搜索结果陷入局部最优.局部实时性信息素更新策略却恰恰与之相反.蚂蚁每进行一次栅格选择,都将根据距离长度进行局部信息素更新,虽然导致收敛速度较慢,但却更易发现最优解.针对上述两种信息素更新策略的特点和局限性,本文将提出一种将实时计 算 机 系 统 应 用ht
20、tp:/www.c-s-2023年第32卷第8期252研究开发ResearchandDevelopment性与全局性融合的信息素更新策略对蚁群算法进行改进.ij首先采用局部实时性信息素更新策略对初始点放置的蚂蚁由栅格 到栅格 的每段路径均进行信息素更新.经过 M 次循环后,每次迭代过程中选择当前循环的蚂蚁进行信息素的更新,此时的信息素增量计算如式(3)所示:kbestij=Q/dij(3)Qdijijkbestkbestij其中,表示当前迭代路径上的总信息素浓度,表示栅格 和栅格 的路径,表示当次循环中表现最好的蚂蚁,表示当前迭代最优蚂蚁的信息素增量值.ij接着为了尽可能减少信息素浓度受外界因
21、素影响而造成的误差,采用 M 次循环中蚂蚁信息素增量的均值作为栅格 到栅格 路径上的信息素初始值,其计算如式(4)所示:initij=Mn=1kbestij(n)/M(4)使用信息素局部实时更新策略使得蚂蚁不会过早收敛于一条不是最优解的路径上,而是持续探索新的路径,避免蚂蚁陷入局部最优.最后,采用信息素全局性更新策略,融合前 M 次循环获得的信息素初始值,对蚂蚁经过路线的信息素全局更新.这种融合信息素初始值的更新规则如式(5)所示:ij(t+1)=(1)ij(t)+initij(5)这种先对蚂蚁进行信息素局部实时更新,获取栅格两点间路径的初始信息素值后,再使用全局性信息素更新策略融合初始信息素
22、值,对蚂蚁进行后续信息素更新的蚁群算法很好地结合了两种信息素更新策略的优势.蚂蚁在迭代过程中既保持了局部信息素更新策略持续探索新路径的能力,以便找到更多可行解,又保持了全局信息素更新策略较快收敛的优势.搜索过程中的蚂蚁根据路径上的信息素浓度和启发式信息计算下个栅格选择概率如式(6)所示:pkij(t)=ij(t)ij(t)uallowediu(t)nij(t),j allowedk0,其他(6)pkij(t)tijijij其中,表示蚂蚁 k 在时刻 由栅格 选择栅格 的概率;表示信息素重要程度因子;表示启发函数的重要程度因子;表示栅格 与栅格 路径上的信息素浓ijij度;表示栅格 与栅格 间的
23、启发函数.2.2 改进信息素更新策略改进信息素更新策略的蚁群算法伪代码如算法 1.算法 1.改进信息素更新策略的蚁群算法Initializenumberofantsm,numberofiterationsM,pheromonevolatilizationcoefficient,informationelicitationfactor,expectedelicitationfactor.RepeatForCurrentiterationnumberninMdoForcurrentnumberofantsk=1,2,mdojallowedkIfthenextgridThenpkij(t)ij(t)
24、ij(t)/uallowedkiu(t)nij(t)Elsepkij(t)0j;/*栅格 不被允许访问*/ijkbestQ/dijUpdatepheromonesinrealtime;End forEnd forijinitMn=1ijkbest(n)/M;/*信息素初始值赋值用于全局迭代*/RepeatForCurrentiterationnumbernMdoForcurrentnumberofantsk=1,2,mdoij(t+1)(1)ij(t)+ijinitUpdatepheromones;End forEnd forUntil allantsfinishtheiteration.Un
25、tilthemaximumiterationisreachedortheoptimalsolutionisobtained.pkijMijinitij算法 1 首先对蚁群算法的参数初始化,随机将m 只蚂蚁放置在栅格初始点,根据状态转移方程计算蚂蚁选择下一个栅格的概率,依据对蚂蚁进行移动,前轮遍历每次移动都将实时更新栅格 到栅格 间的信息素.当所有蚂蚁都搜索出一条到达目的点的路径,选择表现最好的蚂蚁搜索路径作为当前最优解,并将M 次最优的信息素局部更新值的均值作为初始信息素值代入后续全局信息素更新策略的迭代过程,直至达到最大迭代次数或得到最优解.2.3 D*Lite-ACO针对危险天气的随机性与
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 融合 Lite 动态 航路 规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。