基于蚁群融合D＊Lite的动态改航路径规划.pdf

基于蚁群融合 D*Lite 的动态改航路径规划张文1,2,方巍1,3,41(南京信息工程大学计算机学院数字取证教育部工程研究中心,南京210044)2(南京信大气象科学技术研究院有限公司,南京210044)3(南京信息工程大学江苏省大气环境与装备技术协同创新中心,南京210044)4(苏州大学江苏省计算机信息处理技术重点实验室,苏州215006)通信作者:方巍,E-mail:摘要:危险天气下的改航与受限区划设和路径规划算法密切相关,本文针对改航环境构建中 Graham 扫描结果存在较大无效区域,提出分块后并行扫描.针对危险天气的突发性,为了适用于复杂环境,提出在增量式的 D*Lite 全局规划路径基础上智能分割、蚁群算法局部搜索的复合结构动态规划方法.通过改进信息素更新策略解决收敛速度慢、耗时长且易陷入局部最优的缺点.实验结果表明,分块并行 Graham 扫描划设的飞行受限区形状更接近实际,面积缩至原先的 48.1%.改进蚁群融合 D*Lite 的复合结构动态路径规划算法 D*Lite-ACO 兼顾全局与局部,将重规划范围控制到当前位置与目标点间,在路径长度、规划时间和迭代范围上的评价指标分别提升 1.2%、40.7%、66.7%.关键词:危险天气;飞行受限区;路径规划;Graham;蚁群算法引用格式:张文,方巍.基于蚁群融合 D*Lite 的动态改航路径规划.计算机系统应用,2023,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(NanjingXindaInstituteofMeteorologicalScienceandTechnologyCo.Ltd.,Nanjing210044,China)3(JiangsuCollaborativeInnovationCenterofAtmosphericEnvironmentandEquipmentTechnology,NanjingUniversityofInformationScience&Technology,Nanjing210044,China)4(JiangsuProvincialKeyLaboratoryforComputerInformationProcessingTechnology,SoochowUniversity,Suzhou215006,China)Abstract:Diversioninsevereweatheriscloselyrelatedtothedesignationofforbiddenareasandpathplanningalgorithms.GiventhelargeinvalidareaintheGrahamscanningresultsintheconstructionofthediversionenvironment,thisstudyproposesadelineationmethodofGrahamparallelscanningaftertheareaisdividedintoblocks.Forthesuddenoccurrenceofsevereweatherandcomplexenvironments,thestudyproposesadynamicprogrammingmethodofcompositestructureconductingintelligentsegmentationandantcolonyalgorithmlocalsearchbasedonincrementalD*Liteglobalplanningpath.Thepheromoneupdatingstrategyisimprovedtosolvetheshortcomingsofslowconvergencespeed,longtimeconsumed,andtendencytofallintolocaloptimum.TheexperimentalresultsshowthattheshapeoftheflightforbiddenareasdesignatedbyGrahamparallelscanningbasedonthedividedblocksisclosertoreality,andtheareaisreducedto48.1%oftheoriginalone.D*Lite-ACO,animprovedantcolonyfusionD*Litedynamicpathplanningalgorithmforcompositestructures,takesboththeglobalandlocalareaintoaccountandcontrolsthereplanningrangebetweenthecurrentpositionandthetargetedpoint.Theevaluationmetricsinpathlength,planningtime,and计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(8):250258doi:10.15888/ki.csa.009196http:/www.c-s-中国科学院软件研究所版权所有.Tel:[phone]基金项目:国家自然科学基金面上项目(42075007);灾害天气国家重点实验室开放项目(2021LASW-B19);苏州大学计算机信息处理技术省重点实验室开放项目(KJS2275)收稿时间:2023-02-08;修改时间:2023-03-08;采用时间:2023-03-14;csa 在线出版时间:2023-05-19CNKI 网络首发时间:2023-05-23250研究开发ResearchandDevelopmentiterationrangeareimprovedby1.2%,40.7%,and66.7%,respectively.Key words:severeweather;flightforbiddenarea;pathplanning;Graham;antcolonyoptimization(ACO)21 世纪以来危险天气一直是影响航班正点率的首要原因,当计划航路发生危险天气时,航空公司常采用原地等待的方式,导致大量乘客滞留机场.频繁发生航班延误乃至取消事件,将严重影响民航高效、准时的口碑,同时严重制约空管系统的服务水平和效率.确保安全的前提下,合理进行危险天气下的改航路径规划是提高空域容量,保障航空器飞行安全,减少航班延误以及提升民航经济效益的有效途径1.路径规划算法作为改航路径的求解方法,其准确性以及高效性是影响改航结果的关键2.目前,国内外已有不少学者对危险天气下的改航路径规划算法进行研究.李善梅等人3开发了一种基于蒙特卡罗模拟和改进遗传算法的考虑飞行时间可靠性的规划算法,有效提高了航班改航的效率和安全性;Bojorquez 等人4提出了一种基于图形处理单元的并行计算框架,基于 A*算法在风险承受能力下生成飞行器重新路由计划,并可以从其中找到最小的时间和距离轨迹;Wang 等人5利用改进的自适应蚁群算法研究改航路径的相互联系,对航空器飞行时的空域容量和流量进行匹配,降低了规划误差;Tolstaya 等人6提出结合反向强化学习和基于搜索的运动规划算法,融合人工势场创建了自主空中交通管制,从而确保航空器处于安全状态;向征等人7提出了引入人工势场法改进传统蚁群算法中的启发因子信息从而提高路径规划模型中搜索的有效性;赵元棣等人1利用 A*算法分别对栅格法构建的静态和动态空域环境进行快速改航规划建模,减少了计算复杂度的同时实现了快速合理规划路径;陈可嘉等人8同时考虑等待策略和改航策略,设计了两阶段求解算法,使用遗传算法优化等待时长和改航路径后使用“化曲为直”和“二分法”思想调整改航路径;王莉莉等人9将栅格法与动态规划法相结合,针对平行航路提出通过改航优先权分配机制解决飞行经济和安全冲突问题的改航路径规划方法;朱承元等人10利用几何算法预先规划可选改航路径后,使用改进的离散粒子群优化算法探索最优改航路径;陈万通等人11通过几何法处理危险区域凸多边形,并提出一种面向空管的亚轨道碎片危险区预测与路径规划方法,更利于飞机平稳、高效、安全改航.上述文献多对人工势场法、经典规划算法以及智能优化算法 3 大类改航路径规划求解算法改进.本文的主要贡献可以概括为 3 个方面:1)将分块和并行概念引入到 Graham 扫描凹形片状分布的危险天气边界,使得划设的结果更贴近实际,初始环境构建的合理性将直接提升路径规划算法的效率.2)对蚁群算法的信息素更新策略进行改进,采取实时更新获取信息素初始值代入后续全局性更新策略,加快收敛的同时保持了探索新路径的能力,避免陷入局部最优.3)考虑危险天气的突发性,提出在 D*Lite 全局规划路径基础上智能分割,融合改进蚁群局部搜索的复合结构动态改航路径规划算法 D*Lite-ACO(antcolonyoptimization),充分结合两类算法优势,扬长避短.1改进初始环境建模飞行受限区的划设是试验改航路径规划算法的前提和基础,通常为受雷暴、冰雹、强雨雪等恶劣天气影响的区域,指在危险天气下的飞行限制区(flightforbiddenarea,FFA).民航空管部门通常采用雷达探测数据来分析恶劣天气的分布情况,当雷达回波反射率大于 40dBZ 时,为了确保飞行安全问题,航空器将被禁止穿越该区域.改航还需要对未来的飞行受限区位置进行预测.以实时的天气雷达探测图像数据为基础,对雷达回波图进行外推,划设飞行受限区预测位置.对雷达回波图中反射率大于 40dBZ 的危险天气影响区域边界进行提取如图 1 所示.Graham 扫描划设飞行受限区的原理是以边界点位置为基础,通过不断的循环、迭代获取一个凸多边形的区域边界12.经研究发现,当其处理凹形片状分布或散点状分布的危险天气时,划设的结果与实际受限区偏差较大.因此,本文提出分块并行 Graham 扫描划设飞行受限区的方法.根据民航有关航空器绕飞的规定,在两个雷暴体边界之间的距离小于 20 公里的情况下,航空器必须禁止从两者之间穿越.因此,首先需要对提取的危险天气影响区域边界间距小于 20 公里的部分进行合并.接着,2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发251G1,G2,Gn将合并后的飞行受限区视为一个整体,判断提取区域的顶点坐标所形成的多边形是否存在凹形带状分布区域,倘若存在,为了提高划设精度,则需要对其分块的关键点进行确定;倘若不存在,可直接利用 Graham 算法对合并的危险天气影响区域扫描划设.G1,G2,GnGpGqGpGq确定分块关键点的步骤如下:将提取区域的顶点坐标中形成凹形的位置坐标和连接并对线段作中线并与危险天气影响区域边界相交O(p,q)O(p,q)xGtGkO(p,q)于点,以为中心向 轴垂直方向绘制直线,直线与危险天气影响区域的边界相交于点和.此时,贯穿的直线实现了对合并的危险天气影响区域的分块.对危险天气影响区域进行分块后再并行扫描划设的方法不仅使得划设的结果更精细,减小无效区域面积,而且并行一定程度上也减少了 Graham 扫描划设的时间,提高了效率.分块并行 Graham 扫描划设的处理流程如图 2 所示.(a)雷达基数据图像(b)危险天气影响区域(c)提取危险天气边界图 1基于雷达回波图提取危险区域危险天气影响区域提取边界BlockBlockBlock凸包 1凸包 2凸包 3线程并行线程并行组合外扩飞行受限区图 2分块并行 Graham 扫描处理流程图2复合结构动态改航路径规划算法 2.1 改进信息素更新策略蚁群算法是从自然界蚂蚁觅食行为获得的灵感,是一种启发式群体智能优化算法.研究发现,蚂蚁初始的运动方向是随机的,其经过的路径上会释放出一种物质,称之为信息素,蚂蚁间通过该物质相互交流.蚂蚁将根据信息素浓度来决定来选择下一步的运动方向,信息素浓度越大的路径被选择的机率也就越大,最终能得到一条出发点到目的点最短路径.路径上释放的信息素会逐渐消失,信息素的更新计算如式(1)、式(2)13所示:ij(t+1)=(1)ij(t)+ij(t)(1)ij=mk=1kij(2)(0 1)ijij其中,挥发系数表示路径上信息素的挥发程度,表示栅格 与栅格 路径上的信息素浓度.常用的蚁群算法多采用全局性更新策略,蚂蚁搜索的收敛速度较快,能尽早找出一条拟最优路径.然而,由于全局过早收敛,蚂蚁将会更快地集中在当前循环信息素浓度最高的一条路径上,从而阻碍发现更优解,导致最终搜索结果陷入局部最优.局部实时性信息素更新策略却恰恰与之相反.蚂蚁每进行一次栅格选择,都将根据距离长度进行局部信息素更新,虽然导致收敛速度较慢,但却更易发现最优解.针对上述两种信息素更新策略的特点和局限性,本文将提出一种将实时计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第8期252研究开发ResearchandDevelopment性与全局性融合的信息素更新策略对蚁群算法进行改进.ij首先采用局部实时性信息素更新策略对初始点放置的蚂蚁由栅格 到栅格 的每段路径均进行信息素更新.经过 M 次循环后,每次迭代过程中选择当前循环的蚂蚁进行信息素的更新,此时的信息素增量计算如式(3)所示:kbestij=Q/dij(3)Qdijijkbestkbestij其中,表示当前迭代路径上的总信息素浓度,表示栅格 和栅格 的路径,表示当次循环中表现最好的蚂蚁,表示当前迭代最优蚂蚁的信息素增量值.ij接着为了尽可能减少信息素浓度受外界因素影响而造成的误差,采用 M 次循环中蚂蚁信息素增量的均值作为栅格 到栅格 路径上的信息素初始值,其计算如式(4)所示:initij=Mn=1kbestij(n)/M(4)使用信息素局部实时更新策略使得蚂蚁不会过早收敛于一条不是最优解的路径上,而是持续探索新的路径,避免蚂蚁陷入局部最优.最后,采用信息素全局性更新策略,融合前 M 次循环获得的信息素初始值,对蚂蚁经过路线的信息素全局更新.这种融合信息素初始值的更新规则如式(5)所示:ij(t+1)=(1)ij(t)+initij(5)这种先对蚂蚁进行信息素局部实时更新,获取栅格两点间路径的初始信息素值后,再使用全局性信息素更新策略融合初始信息素值,对蚂蚁进行后续信息素更新的蚁群算法很好地结合了两种信息素更新策略的优势.蚂蚁在迭代过程中既保持了局部信息素更新策略持续探索新路径的能力,以便找到更多可行解,又保持了全局信息素更新策略较快收敛的优势.搜索过程中的蚂蚁根据路径上的信息素浓度和启发式信息计算下个栅格选择概率如式(6)所示:pkij(t)=ij(t)ij(t)uallowediu(t)nij(t),j allowedk0,其他(6)pkij(t)tijijij其中,表示蚂蚁 k 在时刻 由栅格 选择栅格 的概率;表示信息素重要程度因子;表示启发函数的重要程度因子;表示栅格 与栅格 路径上的信息素浓ijij度;表示栅格 与栅格 间的启发函数.2.2 改进信息素更新策略改进信息素更新策略的蚁群算法伪代码如算法 1.算法 1.改进信息素更新策略的蚁群算法Initializenumberofantsm,numberofiterationsM,pheromonevolatilizationcoefficient,informationelicitationfactor,expectedelicitationfactor.RepeatForCurrentiterationnumberninMdoForcurrentnumberofantsk=1,2,mdojallowedkIfthenextgridThenpkij(t)ij(t)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.Untilthemaximumiterationisreachedortheoptimalsolutionisobtained.pkijMijinitij算法 1 首先对蚁群算法的参数初始化,随机将m 只蚂蚁放置在栅格初始点,根据状态转移方程计算蚂蚁选择下一个栅格的概率,依据对蚂蚁进行移动,前轮遍历每次移动都将实时更新栅格 到栅格 间的信息素.当所有蚂蚁都搜索出一条到达目的点的路径,选择表现最好的蚂蚁搜索路径作为当前最优解,并将M 次最优的信息素局部更新值的均值作为初始信息素值代入后续全局信息素更新策略的迭代过程,直至达到最大迭代次数或得到最优解.2.3 D*Lite-ACO针对危险天气的随机性与突发性,本文先采用具有动态避障重规划能力的 D*Lite 算法对改航路径进行全局规划.采用反向搜索模式,以减少搜索节点数.当初始规划路径上检测到突发危险物时,将重规划的范围控制在目标点与当前航空器之间,避免对已规划的有效路径的无效计算.针对全局规划在密度较高环境下,效率低下、数据量大、规划路径不平滑等缺陷,在全局规划路径的基础上分割局部区域使用改进的蚁2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发253群算法进行搜索.为了减小蚂蚁局部搜索的范围,从而减少迭代时间,局部区域的分割将建立在全局规划路径的基础上.仅对全局规划路径的周边区域范围采用改进的蚁群算法进行搜索,很大程度上避免对无效区域的迭代计算.目前,民航的管制工作规定当计划航线上出现危险天气时,绝对禁止航空器从危险天气影响区域的上、下方垂直改航或从当中穿越,因此本文研究的改航环境是二维的,以从飞行受限区的安全边界绕飞为出发点,提出相关策略.以 77 的栅格图为例说明,箭头表示由起始点到目标点全局规划的路径,基于全局规划路径分割局部区域如图 3 所示.StartGoalabc图 3基于全局规划路径分割局部搜索区域Xdef圆点表示起始点,五角星表示目标点,小圆点表示对全局初始路径的分割点,路径上的方块区域分别代表了分割出的不同局部搜索的范围.其分割的依据是根据全局规划结果自定义局部初始横向,分割局部的个数如式(7)所示:Nlocal=(Wo1)/Xdef1(7)Nlocal xH yHxy xH yH分别对局部区域遍历获取分割局部区域的关键值与,它们分别对应着局部区域分割的最大 轴与 轴范围.计算和如式(8)所示:xH=xio,abs(xHxH1)abs(xioxH1)且i 1,StepH)yH=yio,abs(yHyH1)abs(yioyH1)且i 1,StepH)xH=xH,yH=yH,i=StepH(8)HH 1,Nlocal iH1(xH1,yH1)H(xH,yH)其中,表示当前遍历的局部区域,.表示从上个关键点到当前关键点StepHxH1Hx0=xstartyH1y0=ystartxioyio的全局路径迭代,表示这段范围全局规划路径的遍历格点数.表示上一个局部区域的关键点,当为 1 时,;表示上一个局部区域的关键点,.表示全局规划路径上点的横坐标,表示全局规划路径上点的纵坐标.PH1PH2PH3PH4PH1(xH11,yH1+1)PH2(xH+1,yH1+1)PH3(xH+1,yH1)PH4(xH11,yH1)分割的局部区域的坐标点分别对应,.由图 3 可知,在全局路径基础上分割确定局部范围后,再进行改进的蚁群算法搜索的方法,使得局部搜索的范围总和明显降低,更有利于效率的提升.rhsrhs将栅格初始化后的全部未知区域视为自由空间,采用 D*Lite 算法从目标点开始向初始点反向增量式地搜索最优路径.增量式的思想可以理解为在学得模型之后,当再接收到新的障碍样本时,算法能够重复利用之前搜索过程中的获得的信息,来规划出新的可以避开危险天气障碍的路径,规划算法无需完全重新规划,有效地减少了重规划关联的节点数以及降低重规划的次数.引入权值(right-handside)作为父节点到当前点的最小代价值,的计算如式(9)所示:rhs(s)=minsSucc(s)(c(s,s)+g(s),s,sstart0,otherwise(9)对于未知环境的全局规划 D*Lite 算法具有良好的性能,然而在精细规划问题上却无法应对局部复杂环境.蚁群算法是一种融入人类智能的通用型随机优化算法,改进的蚁群算法在高密度环境中可以很好地实现避障和规划最优路径,分布式的特征以及较强的鲁棒性使其模型只需稍加修改便可与其他启发式算法结合使用.复合结构 D*Lite-ACO 的整体流程如图 4所示.3实验结果分析 3.1 改航环境构建由中国气象数据网可知,2022 年 4 月 25 日我国华东地区多地持续具有恶劣天气,本文将采用当日上午10 点 36 分的华东地区雷达拼图作为改航环境,采用分块并行 Graham 算法对提取的危险天气影响区域划设凸包,进而对飞行受限区栅格化处理构建改航路径规划的初始环境.试验资料来源于国家气象数据中心(http:/ 1:100000 下进行.计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第8期254研究开发ResearchandDevelopment首先根据民航规定的安全飞行间距,对危险天气影响区域边界间距较小的模块进行合并,选取合并后的最大区域作为危险天气下划设飞行受限区域的对象进行试验.然后对最大区域边界的坐标定点进行提取,对整个区域进行分块,尤其以凹陷处作为关键位置.分割线与区域的交点必须重复引入相邻分块是后续零散凸包组合的关键.为了验证本文所提出的对飞行受限区分块后采用 Graham 算法并行扫描划设静态飞行受限区方法的有效性,将本文所提方法划设和 Graham 算法直接划设凹形带状分布危险天气影响区域的结果进行比较.基于 Graham 扫描法的凸包划设实验对比结果如表 1 所示.开始栅格初始化、设置全局目标节点基于全局规划路径分割局部区域范围改进蚁群算法局部避障路径搜索分割区域是否全部局部规划结束是否到达目标节点结束YYYYNNNN是否到达目标点选择子节点中代价最小的点是否检测到突发危险天气障碍更新当前新起点以及受影响点的权值计算最短路径全局规划 D*Lite图 4复合结构 D*Lite-ACO 整体流程图表 1基于 Graham 划设对比实验方法精准度偏差度面积(cm2)Graham0.4400.560187.72分块并行Graham0.9150.08590.37观察表 1 可知,本文所提方法划设的危险天气凸包面积仅占 Graham 算法直接划设凸包面积的 48.14%,这也印证了分块后采用 Graham 算法并行划设的方法能够有效剔除由 Graham 算法划设原理导致的凹形区域的无效面积.本文所提方法在划设精确度上提升了0.475,划设的结果更接近危险天气影响区域的实际形状.改航环境的合理性是进行路径规划求解算法研究的基础,飞行受限区域面积的减小也将直接提高路径规划阶段的选择性,所以使用本文所提方法划设的静态飞行受限区可以取得更好的结果.3.2 改航算法的对比和验证为了验证改进的信息素更新策略对蚁群算法搜索结果的影响,构建初始栅格环境进行实验.设置每次迭2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发255M=50=7=0.3代的蚂蚁数量,表示信息素重要程度的参数=1,启发函数的重要程度因子,信息素的蒸发系数,将蚁群算法采用本文改进的信息素更新策略与全局更新、局部更新策略下搜索路径的结果进行对比.分别采用全局性更新策略、局部性更新策略以及本文所提改进的信息素更新策略进行对比实验.观察不同信息素更新策略下蚁群算法搜索的最小路径长度和迭代过程中收敛曲线的变化趋势.任取试验中某次蚁群搜索结果为例,采用不同信息素更新策略的蚁群算法对相同环境进行搜索的收敛曲线变化趋势对比如图 5 所示.80706050403020100最短路径0102030405060迭代次数改进的更新策略全局更新策略局部更新策略图 5收敛变化趋势对比图ijinit全局性更新策略下的蚁群算法相比局部实时性更新,其收敛曲线能较快趋向平稳.局部实时性更新策略下的蚁群算法由于需要不断更新,收敛曲线趋向平稳所需时间相对较长.但是,由于其一直保持着搜索新路径的能力,该策略下的蚁群算法搜索的最小路径长度明显低于全局更新策略下的搜索结果.采用本文所提方法的蚁群算法在迭代次数为 10 时便已趋向平缓,这是由于引入信息素初始值使得后续路径信息素浓度的更新无限接近最优值,从而显著加快了蚁群算法的收敛速度,甚至比全局性更新策略下收敛趋向平稳所需迭代时间更短.同时,改进的信息素更新策略下搜索出的最小路径长度也明显优于全局性更新策略,基本趋向局部更新策略下搜索路径的最优解.由此可见,本文所提改进的信息素更新策略将保持新路径搜索的能力和收敛速度快的优势完美结合,无论是在最小路径长度还和迭代收敛速度方面,都取得了最好的效果.为了进一步验证本文提出的全局规划基础上融合改进蚁群算法局部搜索的复合结构动态路径规划算法的可行性与有效性,构建 5050 且障碍物设置相对复杂的栅格环境,采用当前应用最为广泛的全局规划算法 A*、BidirectionalA*、AnytimeRepairingA*(ARA*)、LifelongPlanningA*(LPA*)、D*、AnytimeD*、D*Lite 等分别进行初始的全局规划,比较融合蚁群算法进行局部搜索前各类全局规划算法性能的差异.全局路径规划算法进行初始规划以及重规划的对比测试结果如表 2 所示.表 2全局路径规划算法对比测试方法是否支持动态初始规划重规划长度(cm)时间(s)长度(cm)时间(s)A*-ACON68.4972.162BidirectionalA*-ACON68.4971.440ARA*-ACON68.4972.704LPA*-ACOY68.4971.93271.4260.2158D*-ACOY68.4971.91478.7400.0469AnytimeD*-ACOY68.4971.99171.4260.2381D*Lite-ACOY68.4971.89071.4260.1350由表 2 可知,各类算法起初对静态环境中规划的全局路径长度相等,这是由于静态环境下 D*Lite 类动态规划算法与 A*算法一样,都是利用启发式搜索提高效率,规划路径的方式与 A*算法一致.为了验证几类动态规划算法的重规划能力,在初始规划路径的相同位置添加突发障碍物对重规划的结果进行比较.实验发现 D*Lite-ACO 全局重规划在路径长度上效果较差,其他动态规划算法重规划路径长度也基本一致.为了验证上述方法在动态环境下的重规划性能,本文对几种方法规划的初始路径进行分析研究,选择在全部初始路径都经过的相同位置添加突发障碍物,对几种方法的重规划结果进行比较分析.实验结果如表 2 所示,A*-ACO、BidirectionalA*-ACO 和 ARA*-ACO 不能适用于动态环境,其余几种方法具有动态重规划性,除了D*-ACO 动态重规划的性能较差,其余几种方法动态重规划的路径长度也相同.下面将这几种方法作具体对比分析:AnytimeD*-ACO 在全局规划过程中引入了 Anytime的概念,但本文全局规划的目的在于较快获取全局初始路径用于对局部区域进行分割搜索,因此 Anytime类算法反复求精的过程是非必要的,反而影响了路径规划效率.LPA*-ACO 与 D*Lite-ACO 都采用了增量式的模式进行路径规划,可以充分利用之前搜索过程中的存计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第8期256研究开发ResearchandDevelopment储信息,因此这两种方法在对动态环境进行重规划时,具有良好的性能.不过,LPA*-ACO 重规划的路径考虑的范围始终为固定的起始点与目标点之间,假设航空器位置已经发生了变动,则其根据环境信息变动重新规划的由起始点到目标点的路径对于航空器所在位置而言很有可能并非最优路径.而本文提出的 D*Lite-ACO复合结构动态改航路径规划方法则采用反向搜索的方式,能够将重规划的区域范围设定在航空器当前所在位置与目标点之间,重规划的起始点可以随航空器位置的变化而不断更新,在确保路径为当前航空器最优解的同时,也减少了对已规划路径的无效搜索.在初始规划路径上添加相同障碍物后,LPA*-ACO、D*-ACO、D*Lite-ACO 的动态全局重规划路径对比结果如图 6 所示.由图 6 和表 2 可知,D*Lite-ACO 全局重规划路径相对平滑且长度较短,且反向搜索的特征也使其规划全局路径时,大大减少了访问节点的数量.(a)全局初始规划路径(b)LPA*-ACO 全局重规划(c)D*-ACO 全局重规划(d)D*Lite-ACO 全局重规划图 6动态规划算法重规划路径对比图为了进一步验证对全局规划路径分割后采用改进的蚁群算法对复杂环境进行局部搜索的路径规划效果更佳,将改进的蚁群算法 PDG-ACO14与本文所提 D*Lite-ACO 复合结构动态改航路径规划方法在相同环境信息下进行路径规划对比实验,详细结果如表 3 所示.观察表 3 发现,基于全局初始路径智能分割局部区域的策略将改进的蚁群算法的遍历范围缩小了 66.7%,显著提高了搜索效率.与改进的蚁群 PDG-ACO 相比,本文所提方法在规划的路径长度上减少了 1.2%,总耗时上降低了 40.7%.另外,比 D*Lite 算法直接规划的结果在路径长度方面也有所提升,可以发现复杂环境下的最优解.D*Lite-ACO 算法相比直接采用改进的蚁群2023年第32卷第8期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发257算法处理复杂环境的改航路径规划问题,无论是在规划路径长度、处理时间,还是在迭代范围方面都有明显优势.最为重要的是,这种复合结构改航路径规划在动态环境中具备迅速重规划性.表 3复杂环境下蚁群算法路径规划对比实验方法路径长度(s)时间(s)迭代格点数(块)范围占比(%)PDG-ACO69.32627.8082500100D*Lite-ACO68.48616.47283433.34总结initij为了实现危险天气下高效、安全的改航路径规划,对实时以及外推提取的危险天气区域分块,Graham 算法并行扫描后,对外扩的飞行受限区进行栅格化处理.为了加快蚁群算法的收敛速度、避免陷入局部最优,对其信息素更新策略进行改进,采用实时信息素更新算得初始信息素带入后续的全局更新策略.考虑危险天气的突发性特征,同时尽可能提高改航路径规划效率,提出 D*Lite 算法规划全局路径,在此基础上智能分割局部区域采用改进的蚁群算法进行局部搜索的复合结构动态改航路径规划算法 D*Lite-ACO.实验结果表明,D*Lite-ACO 赋予蚁群算法动态重规划的性能,且大大降低了蚁群局部搜索的遍历范围,有效提高了路径规划效率,确保了航空器的飞行安全.参考文献赵元棣,李瑞东,吴佳馨.动态危险天气下改航路径快速规划方法.中国科技论文,2020,15(6):678681,689.doi:10.3969/j.issn.2095-2783.2020.06.0121王瑛,周楚涵.改航路径规划问题研究综述.空军工程大学学报(自然科学版),2021,22(1):18,84.2李善梅,徐维.面向飞行时间可靠性的航班改航路径规划.中国安全科学学报,2022,32(8):98103.doi:10.16265/ki.issn1003-3033.2022.08.06393BojorquezO,DolanN,ChenJ.Aircraftreroutingunderrisktolerance during space launches.Proceedings of the 20204AIAA Scitech 2020 Forum.Orlando:AIAA,2020.15891603.Wang SJ,Cao X,Li HY,et al.Air route networkoptimization in fragmented airspace based on cellularautomata.Chinese Journal of Aeronautics,2017,30(3):11841195.doi:10.1016/j.cja.2017.04.0025Tolstaya E,Ribeiro A,Kumar V,et al.Inverse optimalplanning for air traffic control.Proceedings of the 2019IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems(IROS).Macao:IEEE,2019.75357542.6向征,张文奇,张文军.雷暴天气下基于多航空器冲突避让的路径规划.中国安全科学学报,2019,29(8):151156.doi:10.16265/ki.issn1003-3033.2019.08.0247陈可嘉,陈琳琳.危险天气下航班等待与改航的实时集成优化.南京航空航天大学学报,2019,51(6):763771.doi:10.16356/j.1005-2615.2019.06.0058王莉莉,刘子昂.针对平行航路的改航路径规划研究.重庆交通大学学报(自然科学版),2020,39(8):4550,58.9朱承元,晏楠欣.恶劣天气下多航空器改航路径的仿真优化算法.交通信息与安全,2021,39(2):109117.doi:10.3963/j.jssn.1674-4861.2021.02.01410陈万通,田书雨.高密度航天发射期间亚轨道碎片危险区快速预测与改航路径规划方法.交通运输工程学报,2022,22(2):268276.11AnPT,HuyenPTT,LeNT.AmodifiedGrahamsconvexhullalgorithmforfindingtheconnectedorthogonalconvexhullofafiniteplanarpointset.AppliedMathematicsandComputation,2021,397:125889.doi:10.1016/j.amc.2020.12588912Tian H.Research on robot optimal path planning methodbased on improved ant co