基于多种群合作演化的无人机协同侦察任务规划研究
2023-06-01帅伟伟任开君
帅伟伟,汪 君,任开君,杨 健,林 洁
(1.解放军95795 部队,广西 桂林 541003;2.中国电子科技集团第十五研究所,北京 100080)
0 引言
无人机能够自主飞行,具备独立执行任务能力,是现代信息化战争中的一种新型作战平台。利用多无人机进行协同侦察,需要考虑无人机航时、侦察时长、任务载荷、中途维护时常等,并综合考虑基地数量、无人机数量、侦察间隔、目标侦察频次等因素,在时空域上规划出无人机航路和时间,并确定侦察每一任务点所使用的任务载荷。其复杂性主要体现在难以获得满足时间、空间、任务载荷等多重约束的多样性有效解[1-3],目前常用遗传算法、蚁群算法等启发式算法进行搜索[4-8],能够较为高效地寻找到可行解,但无法保证解的多样性。本文借鉴多种群合作演化思路[9-10],对传统遗传算法进行改进,用不同种群对解空间进行全局和局部两个尺度的搜索,并通过并行成长和信息迁移,实现种群间的合作演化,以此在时空域上对无人机协同侦察任务进行高效规划。如何合理描述多无人机协同侦察任务规划问题,选取有效的搜索算法,以保证搜索的高效性和解的多样性是本文的研究重点。
1 无人机协同侦察任务建模
1.1 问题描述
在无人机协同侦察常见任务中,多个基地需要派遣多架无人机对多个任务目标执行侦察任务,无人机具有多种型号,搭载有一种或多种任务载荷,任务期间可以在具有保障能力的基地进行维护续航,不同目标点需要在一定时间间隔内采用不同任务载荷进行侦察,且载荷侦察顺序、频次都有要求。为提高侦察效率,降低保障压力,需对多无人机的航路以及对应时间进行规划。
针对多无人机协同侦察任务,可采用图论描述方法对其进行描述,该方法将无人机可能的路径以无向图的方式表达出来,无向图的节点和边集如下:
式中,A 为目标集合;B 为基地集合;V 为无向图的节点集合;E 为无向图的边集,表示V 中所有可能的路径。
1.2 决策变量
1.3 状态变量
1.4 约束条件
2)飞行时间约束:无人机单次最小飞行时间小于最大续航时间T0,当天T1点前必须返回出发基地,可表示为:
3)任务载荷约束:无人机仅能携带起航基地所拥有的任务载荷,可表示为:
1.5 任务收益
1.5.1 任务处置收益
任务处置收益是对当前任务完成情况的一个衡量,但无法对无人机侦察航路的优化潜力进行评估,存在着不同轨迹但收益完全相同的情况。同时,任务处置收益还是一个整数型收益,在优化求解过程中容易丢失梯度信息而陷入局部解中,因此,通过引入任务潜力收益和时间成本收益进行改善。
1.5.2 任务潜力收益
任务潜力主要为评估不同规划航路中无人机的富余侦察能力,富余侦察能力越大,代表该条规划航路鲁棒性越强,其定义如下:
1.5.3 时间成本收益
时间成本收益实际上也体现了规划航路的富余潜力,与任务潜力收益不同的是,其取值连续性强,航路点细微变化都必然带来时间成本收益的改变,因此,能够提供细微的梯度辅助信息,保证算法更快更好地收敛。其定义如下:
该值反映了剩余时间百分比,取值在0~1 之间,变化连续使其可作为任务处置收益的辅助收益指标。在实际求解过程中,任务潜力收益与时间成本收益之和优化后期也小于1,不会偏离最终的任务处置数量。
2 基于多种群合作演化的任务规划算法设计
多种群合作演化过程中,不同种群在不同尺度上并行搜索,这里主要采用两个种群分别在全局和局部两个尺度搜索,全局搜索主要保证解的多样性;局部搜索则是在当前解邻域范围进行搜索,优化解的质量,两者并行进行,共同保证解的多样性和有效性。合作演化则是保证不同种群的迁移演化,实现全局搜索与局部搜索的信息共享与统一,而不仅仅将其当作物理隔绝的两个独立种群,有利于提高搜索效率。
2.1 基本流程
图1 为多种群合作演化遗传算法的基本流程。
图1 多种群合作演化示意图Fig.1 Schematic diagram of multi-group cooperative evolution
2.1.1 全局搜索
全局搜索主要是对染色体中的每个基因以相同概率进行交叉变异,以保证搜索解尽可能分布在整个解空间,保证解的多样性。
2.1.2 局部搜索
局部搜索主要是在全局优解基础上,对时间、中转基地基因以较高概率交叉变异,对路径点以较低概率交叉变异,实现在全局优解邻域空间搜寻更优解。
2.1.3 合作演化
并行搜索后都将个体最优解放入优解池,分别按照独立的概率迁移到各自种群内,通过若干代迭代,将实现全局搜索与局部搜索的信息共享与统一,而不仅仅将其当作物理隔绝的两个独立种群。
2.2 交叉变异
染色体编码采用的是混合编码,其中,时间基因为连续量,其他基因为离散量。对于离散的任务点序列,采取两点交叉和多点变异,两点交叉即在两个个体编码串中随机设置两个交叉点,并交换交叉点之间的部分染色体;多点变异则是随机选择染色体中多个变异点,变异点个数和变异后数值都由随机数生成。
2.3 合作演化
合作演化的重点是将全局搜索得到的优解逐步传递用于局部搜索,局部搜索得到的更优解进一步传递优化全局搜索的解集合,在此过程中,既要保证解的质量,也要保证解的多样性,以免提前收敛,无法发挥并行搜索的优势。
对于全局搜索的每个解,依次根据收益指标和多样性指标采取轮盘赌方法随机选择解,并以概率p 加入到优解池中,局部搜索则以概率p 随机从优解池中选择解进行局部优化,并将优化后的解加入到优解池,并传递给全局搜索。为了保证全局搜索和局部搜索保持染色体个数不变,每次从优解池选择优解都需从原解集淘汰相同数量。
3 多无人机协同侦察任务规划模型求解
3.1 查找单架无人机有效路径
由于时间、空间等多重约束,每条染色体对应的无人机路径难以保证是一条有效路径,因此,根据算法1 约束查找染色体对应的无人机有效路径。
算法1 单架无人机有效路径查找算法已知:遗传算法搜索得到的初始序列images/BZ_178_795_1899_1072_1947.png;侦察时间代价矩阵T(n×n);最大侦察时间images/BZ_178_535_2032_566_2065.png。求:满足航程约束的有效路径序列Pv。1:初始化①初始化合理路径列表images/BZ_178_693_2264_829_2315.png;②初始化无人机总飞行时间t=0。2:重复执行算法流程3-5 共n-1 次,循环序号为i。3:对任一返航基地j,如果images/BZ_178_669_2455_982_2509.png,代表无人机飞往下一目标后能够返回出发基地或者飞往任一基地进行维护,则跳转到步骤4,否则跳转到步骤5;4:将pi+1 加入Pvimages/BZ_178_503_2653_643_2693.png,images/BZ_178_661_2649_847_2694.png;5:寻找最近的无人机基地j,判断能否当天飞往j 后返航到出发基地,能够则将基地j 加入Pv,images/BZ_178_750_2775_936_2820.png,否则,跳转到步骤2。
3.2 统计任务目标有效侦察次数
对于每个待侦察的任务目标,要求利用一种或多种侦察载荷,在约定的侦察间隔内进行一次或多次侦察,为了计算任务收益值,需要根据算法2 递归查找有效侦察次数,以判断任务目标是否成功侦察。
算法2 有效侦察次数递归查找算法已知:被侦察时间序列images/BZ_178_1618_613_2004_673.png;被侦察载荷序列images/BZ_178_1618_695_2041_753.png。求:当前有效侦察时间序列Tl;有效侦察载荷序列Dl。1:初始化Tl、Dl 为空;2:重复执行算法流程L 次,循环序号为i;3:重复执行算法流程L-i 次,循环序号为j;4:对于每一个元素images/BZ_178_1581_1129_1694_1178.pngimages/BZ_178_1712_1130_1844_1177.png,如果,则执行步骤5,否则继续执行步骤4;5:且images/BZ_178_1320_1200_1415_1242.pngimages/BZ_178_1321_1274_1418_1313.pngimages/BZ_178_1438_1276_1555_1313.png表示Tl 元素个数如果,,images/BZ_178_1575_1264_1757_1316.png,其中,images/BZ_178_1873_1266_1950_1316.pngimages/BZ_178_1357_1338_1531_1390.png,则结束,否则跳转到步骤2。
3.3 算法性能评估
使用5 架无人机从3 个基地出发协同侦察15个任务目标,并按照表1 设置算法参数进行仿真求解,其中一次结果如下页图2 所示,能够看出5 架无人机很好地完成了对任务目标点的全覆盖。
表1 算法参数表Table 1 Algorithm parameter
图2 多无人协同侦察结果图Fig.2 The result of multi-UAV cooperative reconnaissance
为了比较本文算法与常规的单种群遗传算法的优劣,对任务处置收益、任务潜力收益、时间成本收益进行比较如表2 所示,并给出图3 所示的综合收益对比曲线。为了保证公平性,单种群遗传算法的染色体个数为多种群的2 倍。
表2 收益对比表Table 2 Comparison on efficiency
图3 综合收益对比曲线Fig.3 The comparison curve of the comprehensive benefits
表2 为10 次仿真结果的平均结果,其中,多种群合作演化遗传算法中任务处置收益33 为当前仿真条件下任务处置收益的饱和值,表示此时能够实现有效侦察次数33 次,完成了当前要求的侦察任务。而单种群遗传算法由于缺乏并行的局部搜索环节,仅靠收敛阶段对邻域小范围的细致搜索,解的质量较之多种群更差,同时算法收敛也更慢,如图3所示。
4 结论
本文研究在多种约束条件下的多无人机规划问题,提出基于多种群合作演化的无人机协同侦察算法,该算法对规划问题进行分层描述,确定单架无人机有效路径查找算法,采用多种群合作演化在全局和局部两个尺度进行搜索,在确保搜索效率的同时,通过并行成长和信息迁移,实现种群间的合作演化,实现了在时空域上对无人机协同侦察任务的高效规划。
仿真结果表明,该算法与单种群搜索算法相比,在任务处置效益、任务潜力效益、时间成本效益等方面均有提升,但由于多种群信息迁移过程中加入了新的参数,提高了参数选择的难度。下一步工作将考虑种群多样性和收敛性设计参数自动选择算法,提高算法灵活性。