基于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 优化。滤选蚁过滤了部分可能较差的路径，