基于Dubins-双蚁群算法的搜潜航路规划_王牧原.pdf

引用格式:王牧原，马良荔，陈鹏先，等 基于 Dubins 双蚁群算法的搜潜航路规划J 电光与控制，2023，30(7):106-110 WANG M Y,MA LL,CHEN P X,et al Aerial submarine search route planning based on Dubins-double ant colony optimizationJ Electronics Optics Control,2023,30(7):106-110基于 Dubins 双蚁群算法的搜潜航路规划王牧原1，2，马良荔1，陈鹏先1，刘立国1(1 海军工程大学，武汉430000;2 中国人民解放军 92975 部队，浙江 宁波315000)摘要:针对航空搜潜浮标距离近、偏航角较大的特点，提出 Dubins 路径和双蚁群算法相结合的航路规划算法。对比传统航路规划先确定直线航路再进行平滑处理的方式，所提算法在迭代寻路阶段将直线路径转化为 Dubins 路径，减少了转弯半径约束下无法抵达目标的风险;同时以 Dubins 距离作为判优基准，相比直线距离，更加接近全局最优;并且增加偏航距离扰动参数，引导蚂蚁选择直线距离和偏航角均较小的目标;发挥不同蚁群的信息素负反馈作用，促使寻找新路径，提升寻路能力。仿真结果表明，该算法加快了规划收敛速度，有效缩短了航路距离，缩短幅度平均达14 6%以上。关键词:航空搜潜;航路规划;Dubins 路径;蚁群算法中图分类号:E953;TP301 6文献标志码:Adoi:10 3969/j issn 1671 637X 2023 07 019Aerial Submarine Search oute Planning Based onDubins-Double Ant Colony OptimizationWANG Muyuan1，2,MA Liangli1,CHEN Pengxian1,LIU Liguo1(1 Naval University of Engineering,Wuhan 430000,China;2 No 92975 Unit of PLA,Ningbo 315000,China)Abstract:According to the characteristics of close distance and large yaw angle of aerial submarine searchbuoy,a route planning algorithm combining Dubins path and double ant colony algorithm is proposedCompared with the traditional route planning that the linear route is firstly determined and thensmoothed,the algorithm converts the straight path into the Dubins path in the iterative pathfindingstage,which reduces the risk of not reaching the target under the constraint of the turning radius,and theDubins distance is used as the benchmark for judging,which is closer to the global optimal than the straight-line distance Moreever,the parameters of yaw distance disturbance are added to guide ants to choose targetswith smaller straight-line distance and yaw angle,and use the negative feedback of pheromones in differentant colonies to promote the search for new paths and improve the wayfinding ability The simulation resultsproves that the algorithm accelerates the convergence speed of planning,effectively shortens the totaldistance of the route,and the average shortening range is more than 14 6%Key words:aerial submarine search;route planning;Dubins path;ant colony algorithm0引言航空反潜具备反应速度快、机动灵活等优势，是反潜体系中的重要组成部分1。搜潜设备一般包括声呐浮标(简称浮标)、磁探仪、雷达等。为发挥浮标最大效益，飞机需要按预设或临时制定航路依次通过指定位置，并进行浮标投放。因此，航路规划直接影响到飞收稿日期:2022-05-25修回日期:2022-06-16作者简介:王牧原(1993)，男，重庆合川人，硕士，助工。通讯作者:马良荔(1968)，女，辽宁沈阳人，博士，教授，博导。行时间和浮标效能发挥，对于反潜作战水平的提升至关重要。航路规划的基本步骤2 为:1)将实际环境构建为平面或三维空间，初步规划飞行航迹;2)通过优化算法进行航路寻优，如目前应用最广的粒子群算法、遗传算法、蚁群算法3 等启发算法，这些算法模拟生物界不断试错获取空间信息，以在正反馈循环中逼近最优解的方式，迭代发现最优直线路径;3)航路平滑处理，使用平滑算子法、滤波法、B 样条曲线法4 等方法，通过抽样、逼近和插值等方式，将折线转化为平滑的曲线。搜潜航路规划本质上是一个具有移动角度约束的Vol 30No 7July 2023第 30 卷第 7 期2023 年 7 月电光与控制Electronics Optics Control王牧原等:基于 Dubins 双蚁群算法的搜潜航路规划旅行商问题5，但和常规规划略有不同，存在航路点相对较多、浮标间距较小、偏航较大等特点。孙启豪等6 将浮标抽化为平面上点集，用蚁群算法生成复杂点阵下的直线航路;毛杰等7 使用 Lazy Theta*算法，将平面栅格化，允许任意角度改变栅格内路径方向，以进行平滑处理。当前主要存在 3 个问题:1)浮标间距小于转弯半径时，可能出现无法平滑路径、不能抵达目标的情况;2)栅格内平滑、抽样等方式，属于以直代曲，效果与设定栅格边长、抽样次数有关，较真正的最短曲线路径有一定差距;3)未考虑对操作时间的限制，有必要将算法运行速度作为指标。针对这些问题，本文采用基于 Dubins 路径的改航方式，到达下个浮标之前，已调整航向至后续浮标，减少载机不可达的风险。并与自适应蚁群算法相结合，提出 D-ACO(Dubins-Ant Colony Optimization)算法，将平滑处理提前至寻优阶段，以 Dubins 距离作为判优基准，缩短了航程。同时，在蚁群转移规则中增加偏航距离扰动，使寻路不仅与信息素浓度和直线距离相关，也考虑偏航角度影响。但计算 Dubins 距离较为复杂时，会降低算法速度，因此在 D-ACO 基础上划分双蚁群，提出 D-DACO(Dubins-Double Ant Colony Optimization)算法，两个种群分别发挥快速扩展新路径和稳定收敛的作用，提高寻路效率。1常规航路规划方法1 1自适应蚁群算法蚁群算法指模拟蚂蚁觅食过程中释放信息素，间接确定路径的方法。蚂蚁被信息素所吸引，选择浓度较高的路径，又沿途积累信息素，构成正反馈。蚁群持续迭代，向最优解的方向进化，最终趋于最短路径。蚂蚁根据伪随机比例规则选择下一目标。设 n 为浮标总数，m 为每次迭代的蚁群数量，dij为浮标 i 与浮标 j 之间的直线距离，各个浮标间的初始信息浓度相同，A 为蚂蚁未经过的浮标集合，s 为任一浮标，由浮标i 至浮标 j 转移概率为pij(t)=ij(t)ij(t)sA is(t)is(t)j A0j A(1)式中:ij(t)为 t 时刻浮标 i 与浮标 j 之间的信息素浓度;ij(t)为启发信息，一般取值 1/dij;为启发因子，表示信息素的重要程度，0;为期望因子，表示启发函数的重要程度，0。蚂蚁遍历一次完整路径后，进行信息素更新，即ij(t+1)=ij(t)(1 )+mk=1ij(t)(2)kij(t)=Q/L蚂蚁 k 经过路径(i，j)0其他(3)式中:为防止算法停滞而设置的信息素挥发系数，0 1;kij(t)为本次迭代时蚂蚁 k 在路径(i，j)遗留的信息素;L 为路径距离;Q 为信息素强度。传统蚁群算法搜索较慢，且缺乏初始信息素，容易出现局部最优。经研究，已发展出如下自适应优化8:1)结合贪心算法9，根据浮标距离设置初始信息素浓度，加快收敛速度;2)引入最大最小蚂蚁系统10，限定信息素范围，保持随机性，防止过早收敛陷入局部最优;3)采用精英策略11，只允许更优的蚂蚁更新信息素，且对每次迭代的最优蚂蚁增加额外的信息;4)结合 opt 算法12，选取待优化路径的数条边，断开后尝试不同的连接方式，产生更多新路径，提高算法多样性，增强搜索能力。1 2Dubins 路径Dubins 路径13 是在一定曲率条件下，连接同一平面内具有特定方向向量的任意两点间的最短路径，由最大曲率或直线段组成。表现形式为:过起始点和终点两侧分别作圆，该圆与速度方向相切，其中，逆时针旋转的圆弧记作 L1，顺时针旋转的圆弧记作，两个圆之间的切线记作 S。形成从起始点到切线点 1，从切线点 1 到切线点 2，从切点 2 到终止点共 3 段路径。依据每段路径的方向，Dubins 路径集合 D=LSL，S，SL，LS，L，LL。Dubins 路径的6 种基本情况见图1。图 1Dubins 路径的 6 种基本情况Fig 1Six basic situations of Dubins path为保证设备和人员处于良好状态，应尽量保持直线飞行，故舍弃 L 和 LL 模式。当偏航角大于最大转弯角时，飞机按照剩余 4 种情况中距离最短的路径改航，即浮标间的 Dubins 路径;否则，判定飞机可以通过即时机动驶向目标，继续直线或折线行进。2基于 Dubins 路径的双蚁群算法2 1D-ACO 算法常规航路规划偏向于选择直线距离较近的目标，701第 7 期在迭代结束、路径已固定后，才进行一次平滑处理，与真正的最优路径可能存在较大差距。为更接近真实最短航路，D-ACO 算法在迭代过程中，对每只蚂蚁都采用2-opt 算法优化，产生两条浮标序列，将其转化为 Dubins 路径，再进行判优。过程中，在转移概率计算中引入偏航距离扰动 d，发生改航时，在直线距离 d的基础上增加 d，改变启发函数，进而倾向于选择直线距离和偏航角均较小的浮标，启发函数 的算式为ij(t)=1dij+d(4)式中，d 0，4r)区间内，与偏航角、转弯半径 r 呈比例关系的随机值。算法流程如图 2 所示。图 2D-ACO 算法流程Fig 2Flow chart of D-ACO algorithm2 2D-DACO 算法在 D-ACO 算法基础上，引入滤选蚁和精确蚁的概念，采用双蚁群系统，建立负反馈机制14，保证了全局最优性，且一定程度上提升了运行速度。2 2 1基本原理定义 1滤选蚁先进行直线加偏航扰动距离的近似计算，有选择性地进行 2-opt 优化，再计算 Dubins 距离判优;若近似解小于当前最优解，认为该路径具备优的特性，无需 2-opt 优化。滤选蚁过滤了部分可能较差的路径，减少了计算量，起快速寻路的作用。定义 2精确蚁即 D-ACO 算法中的蚂蚁，固定生成两条路径，直接精确计算的 Dubins 距离，起防止遗漏更优路径、促进收敛的作用。为了保证前期快速取得成效，后期稳定收敛，算法开始时滤选蚁占比较大，随后逐渐增加精确蚁比例。2 2 2转移规则改进两种蚁群的信息素相互独立，吸引自身种群，而对对方种群产生排斥效果，促使蚂蚁偏离已选择过的序列，开辟新路径。两种蚁群也具备信息素交互机制，每迭代一定次数，吸取部分对方种群信息素，保持差异的同时，保证迭代向更优推进，可表示为ij=(1 u)ij+uij(5)式中:ij为对方蚁群的信息素;u 为对方种群信息素的影响能力，0 u 1。双蚁群信息素共同作用下，改进后的转移概率为pij(t)=ij(t)ij(t)sA is(t)is(t)fijjA0jA(6)fij=ij/(ij+uij)(7)式中，f 代表两个蚁群的信息素综合效果。2 2 3算法流程双蚁群算法进行航路规划的具体步骤为:1)参数初始化，建立浮标距离矩阵、偏航角矩阵和信息素矩阵，运行一次贪心算法以改进信息素初始浓度;2)先后投入滤选蚁和精确蚁，按各自规则寻路和更新信息素;3)根据迭代次数调整种群数量，重复步骤 2);4)达到最大迭代次数后，输出最终航路，算法结束。具体流程如图 3 所示。图 3D-DACO 算法流程Fig 3Flow chart of D-DACO algorithm801第 30 卷电光与控制王牧原等:基于 Dubins 双蚁群算法的搜潜航路规划3仿真验证为检验 D-DACO 算法的性能，本文使用 JupyterNotebook 软件仿真，以飞机为原点，采用随机数据和截取 TSPLIB 中的 st70，eli51，eli101 作为浮标，模拟飞机按照各算法的航路规划情况。随机数据中，生成相邻两点的间距与浮标作用范围相关，模拟搜潜环境;TSPLIB 是旅行商问题常用数据集，主要包括城市坐标，点距相对较大，更接近常规航路规划。3 1参数设置设飞机的速度 v 恒为 350 km/h，最大转弯角 为15，浮标作用距离 3 km，即浮标间隔 6 km。g 为重力加速度，根据r=v2/(gtan)(8)算得飞机机动最大转弯半径 r 为 3 6 km。蚁群参数对算法影响巨大:种群数量 m 过小时，结果不稳定，数量过大时，运行速度慢。据研究 15，m 08n，12n，0，5，0，5 时，算法效果较好。2-opt 算法减少了 m 的需求量，取 m=0 6n，=1，=5，=0 9，=02，迭代次数为 150。由于浮标数量、间距可变，为适应不同的搜潜条件，不设置固定 Q 值，取贪心算法直线距离的 1/2。3 2仿真结果将未加入偏航距离扰动的算法记作 D-ACO-1 和D-DACO-1，分别与 D-ACO 算法和 D-DACO 算法比较。路径长度与迭代关系分别如图 4、图 5 所示。图 415 枚浮标仿真结果Fig 4Simulation result of 15 buoys图 528 枚浮标仿真结果Fig 5Simulation result of 28 buoys结果显示，D-DACO 算法和 D-ACO 算法的最短距离和平均距离都明显低于未加入扰动的算法，距离下降的梯度更大。当 n=15 时，D-DACO 算法和 D-ACO算法在第 30 代左右就趋于稳定，而 D-ACO-1 算法和D-DACO-1 算法分别在 62 代和 87 代以后才找到最短路径;当 n=28 时结果相近，D-ACO-1 算法和 D-DACO-1算法陷入了局部最优。说明偏航距离扰动有效增强了算法收敛性和全局最优性。将先规划直线航路再平滑的方式记作 ACODu-bins。以算法运行一段时间(本次实验取 3 s)后的距离 Lt、算法终止的平均距离 Lave、最短距离 Lmin及其比值 rratio和总运行时间 t 为指标，在不同数据集上反复验证。10 次仿真的结果如表 1 所示。表 1仿真结果Table 1The simulation resultsn 数据源算法Lt/kmLave/km Lmin/km rratio/%t/s9随机生成15随机生成28随机生成35随机生成20截取st7050截取eli51101 eli101ACODubins255372553725537 1000 23D-ACO22129220332199686133 74D-DACO22012218032156184433 44ACODubins273282732827328 1000 71D-ACO24512278422231833711 03D-DACO240492281622265834910 18ACODubins477684776845484 1003 84D-ACO428313951237831831745 29D-DACO414413823636529803141 21ACODubins639685761153331 1007 58D-ACO522964779745697856977 38D-DACO523574685145551854169 97ACODubins443634436344363 1001 53D-ACO370537053705835220 86D-DACO370537053705835219 84ACODubins842587476471641 10022 46D-ACO7384261967592148265 155 71D-DACO7245360328590898248 142 7ACODubins173419 157931 150408 100194 01D-ACO 148164 127338 1171287787 749 51D-DACO 144339 120643 1154567676 667 09由表 1 可得出以下结论。1)精度方面。D-DACO 算法和 D-ACO 算法的最短距离和平均距离相近，D-DACO 算法略优;浮标数量少于50 时，D-DACO算法较初始算法缩短了 19 89 km，大于50 时缩短了数百公里，性能最少提升了146%以上。2)速度方面。D-DACO 算法的运行时间比 D-ACO算法更短，且差距随浮标数量增加而增大;虽然运行时间长于原始算法，但距离下降更快，3 s 内距离下降至原始算法的12%182%。可以在预设航路时，运行算法至完全收敛，发现目标需临时规划时，限时输出结果。901第 7 期3)实验在 TSPLIB 和随机数据取得了同样的效果，说明 D-DACO 算法不仅适用于搜潜航路规划，对常规航路规划也展现出良好的适应性。eli51 中前 15 个点的模拟航路如图 6 所示，其中“”为起点。图 6模拟航路Fig 6Simulation route4结论针对搜潜航路规划特点和需求，提出基于 Dubins路径的双蚁群(D-DACO)算法，其特点如下:1)同步进行寻路和路径平滑，将直线路径转化为Dubins 路径后再比较判优，降低了目标不可达的风险，缩短了航路距离;2)引入偏航距离扰动，改善蚁群转移概率，提高了选中距离和角度都较小的浮标的概率，加快收敛，同时扩大寻路范围，提升全局最优性;3)将单蚁群扩展为双蚁群，建立正负反馈机制，有助于破除局部最优。通过区分滤选蚁和精确蚁，分别发挥快速寻路和稳定收敛作用，缩短运行时间，提升算法效率。多组数据仿真验证了 D-DACO 算法在收敛性和最优性的提升，短时间内也能输出可接受的较优航路，同时满足提前规划和临时规划两种需求，并且该算法对于常规航路仍然适用。参 考 文 献 1 王新为，谭安胜 反潜巡逻机作战使用研究综述 J 军事运筹与系统工程，2015，29(4):72-79 2 樊娇，雷涛，韩伟 无人机航迹规划技术研究综述 J 郑州大学学报(工学版)，2021，42(3):39-46 3DOIGO M The ant system:an autocatalytic optimizingprocess C/Proceedings of the First European Confer-ence on Artificial Life Paris:s n,1991:120-141 4 田疆 无人机三维约束多目标航迹规划 D 兰州:兰州理工大学，2018 5 赵鑫，杨雄飞，钱育蓉 改进的蚁群优化算法求解旅行商问题 J 计算机工程与设计，2022，43(4):962-968 6 孙启豪，蔡爱华 航空搜潜布阵航路优化研究 J 电光与控制，2017，24(4):39-42 7 毛杰，张昊，李海燕 基于 Lazy Theta*算法的反潜巡逻飞机航路规划研究 J 舰船电子工程，2020，40(12):40-43，47 8 JIAO Z Q，MA K,ONG Y L,et al A path planning meth-od using adaptive polymorphic ant colony algorithm forsmart wheelchairsJ Journal of Computational Science,2018,25:50-57 9 曹建秋，徐鹏，张广言 基于贪心策略下混合蚁群算法的无人机航迹规划 J 重庆交通大学学报(自然科学版)，2021，40(9):9-16，23 10 刘保季，李法德，宋占华，等 基于改进最大最小蚁群算法的方格蔟采茧机采茧路径优化J 蚕业科学，2021，47(5):435-442 11 袁梦顺，陈谋，邵书义，等 基于改进精英蚁群算法的无人机三维航迹规划 J 火力与指挥控制，2022，47(2):37-42 12 GULCU S,MAHI M,BAYKAN O K,et al A parallel co-operative hybrid method based on ant colony optimizationand 3-opt algorithm for solving traveling salesman prob-lem J Soft Computing,2018,22(5):1669-1685 13DUBINS L E On curves of minimal length with a con-straint on average curvature and with prescribed initialand terminal positions and tangentsJ American Jour-nal of Mathematics，1957,79(3):497-516 14 杨康，游晓明，刘升 引入熵的自适应双种群蚁群算法 J 计算机工程与应用，2019，55(19):66-73 15 向永靖 蚁群算法中参数设置的研究 以 TSP 为例 J 现代信息科技，2020，4(22):95-98，102011第 30 卷电光与控制