乐健驿, 宋业新, 陈 洋

(海军工程大学,湖北 武汉 430033)

0 引言

无人机(Unmanned Aerial Vehicle,UAV)自问世以来,在各个领域中都得到了广泛的应用。在军事应用方面,无人机以其具有的无生命危险性、大过载、高机动性和经济可承受性等优点,使其备受青睐。军用无人机也经历了从任务简单的靶机,到具备综合侦察监控、空域巡逻、火力定位、实施精确打击能力的察打一体无人机的发展。自上世纪九十年代以来,无人机在世界上各局部战争中使用的频次逐步增多,尤其是近几年爆发的叙利亚战争、纳卡地区战争中,无人机群大量投入使用。因此,无人机协同任务规划也成为各国学者研究的热点问题之一[1～8]。在算法创新方面,文献1针对多无人机协同搜索攻击任务规划问题,提出了智能自组织算法,将全局优化问题分解为多个局部优化问题,再通过无人机之间的信息交换,对整个系统做出最优决策。在应用背景与模型创新方面,文献2根据多机场起降,多种侦查设备挂载的背景模型,利用改进的遗传算法对最优侦查效率的问题进行了求解;文献3,4考虑了各个任务的时间约束,分别采用了市场分布式拍卖算法与遗传算法进行了求解。在任务规划的鲁棒性研究方面,文献4～7分别以凸函数差分算法、鲁棒过滤嵌入式任务分配算法、计算不确定多属性决策问题的权值向量等方法,对不确定环境下多无人机协同任务规划问题进行了求解。

从无人机任务规划的应用背景来看,现有研究大多建立在陆基起降的无人机基础之上,而舰载无人机的任务规划有其自身特点。一方面,陆基起降的无人机,其放飞、着陆地点均为固定地点,而舰艇为移动平台,其放飞点与着舰点均不固定,增加了问题求解的复杂度。另一方面,舰艇在海面航行过程中,不同海域的海洋环境不同,过大的海浪会导致舰体大幅度横摇、纵摇、垂荡,对无人机的离舰、着舰构成安全威胁,因此在任务区域内,只有部分海域适合无人机起降,而舰艇在适合无人机起降的海域内活动的时间有限,因此无人机起降存在时间约束。本文以舰载多无人机协同对海面目标攻击的任务为背景,综合考虑存在多个适合无人机起降海域的情况下,结合起降平台的时间约束,对该任务规划问题进行讨论。

1 多舰载无人机协同海上目标攻击问题的描述

1.1 问题的描述

设有一艘水面舰艇,舰艇上载有n架舰载无人机,对已知的海上m个固定目标进行协同攻击。舰艇依次航行至适合无人机起降的海域,组织无人机放飞、着舰等活动。舰艇在组织无人机放飞、着舰的时候,会在该海域逗留一段时间,称为窗口时间。无人机放飞以后,可以选择不同路径依次对目标进行攻击,任务完成以后返回舰艇。为方便起见,将适合无人机起降的海域抽象为二维平面上的坐标点,称为起降点。

无人机一共有两个装备外挂点,分别为武器外挂点以及电子干扰吊舱外挂点。武器外挂点可以选择不同的装备挂载,不同的武器对不同的目标能造成不同的损毁程度。而电子干扰吊舱外挂点只能选择一种电子干扰吊舱挂载。电子干扰吊舱能有效对攻击目标的反击进行干扰,提高无人机的存活概率。而不同的装备挂载选择,使无人机产生的油耗不同,从而有不同的空中续航时间。因此要求无人机选择合适的挂载装备,起飞、着舰点,以及攻击路径,使得攻击收益最高,而损毁概率最小。

1.2 基本假设与说明

1)无人机挂载武器攻击距离有限,只有飞行至固定目标节点附近时,才能对该节点的目标进行攻击,此时飞行距离近似为两节点之间的距离。另外,无人机可以依次对不同目标进行攻击,一架无人机对同一目标只攻击一次。

2)无人机对目标的攻击能瞬时完成,攻击不额外耗费空中续航时间。

3)任务前需对任务海域内的海底暗礁、浅滩、水雷等威胁舰艇航行安全的因素进行综合评估,舰艇航迹由任务前制定的航行计划确定,每个起降点的时间窗口唯一。

4)无人机若不能在空中续航时间内顺利返回舰艇,则因燃料耗尽而坠毁。

5)无人机返航后需要例行机械检查,做日常保养维护,因此在任务期间,各无人机最多只能放飞一次。

2 无人机任务规划模型的建立

2.1 符号描述

U={ui|1≤i≤n}为舰载无人机集合。

VS={vi|1≤i≤p}为起降点集合。

VT={vi|p+1≤i≤p+m}为攻击的目标节点集合。

V=VS∪VT为所有节点集合。

T={tv|v∈VS}为舰艇在各个起降点对应的时间窗口集合。集合T中所有元素均为时间轴上的连续闭区间。

W={wi|1≤i≤l}为无人机所有可选择挂载的武器集合。

cij,i,j∈V为无人机在该路径上飞行所耗费的空中时间。无人机在该路径上飞行所耗费空中时间与其飞行方向无关,即cij=cji。

ak表示第k个无人机在的总的造价成本,包括无人机自身造价成本与该无人机所有挂载装备的造价成本。

Pk表示第k个无人机在任务路径航行时被对方部署的防空武器造成毁伤概率的总和。

β∈(0,1)表示电子干扰吊舱的干扰效率。无人机未挂载电子干扰吊舱时,遭到反击的毁伤概率为P,挂载以后的毁伤概率为P(1-β)。

τ(w,y),w∈W,y∈{0,1}表示无人机空中续航时间。该参数依赖于无人机挂载装备的决策,其中w表示无人机挂载武器的选择,y=0表示未挂载电子干扰吊舱,y=1表示挂载了电子干扰吊舱。

2.2 决策变量的描述

2.3 目标函数及约束条件

2.3.1 攻击收益目标函数

无人机按照任务决策,依次对选定目标进行攻击。因此该目标函数为全体无人机对所有目标的攻击收益之和,要使其最大化。即:

(1)

(1)式中,目标节点j受到无人机攻击造成毁伤概率总和为:

2.3.2 无人机损毁目标函数

无人机依照任务安排,在对目标进行依次攻击时,在各路径上将遇到对方防空火力的攻击。该目标函数为全体无人机在路径上损伤概率之和,要使其最小化,即:

(2)式中,单个无人机任务路径航行时被对方部署的防空武器造成毁伤概率的总和为:

2.3.3 约束条件

约束条件(3)保证无人机在各路径航行所耗费的空中续航时间要小于挂载装备以后的最大续航时间,使其能在续航时间内完成预定的任务。

(4)

约束(4)表明无人机只能选择一种武器挂载。

约束条件(5)表明无人机从任务起始节点出发,经历任务所需时间以后,舰艇要处于其着舰点的窗口时间内,保证了无人机完成任务后能在预定时间内返回舰艇。

(6)

(7)

(8)

约束(6)、(7)、(8)保证无人机对每个任务目标只攻击一次,且不会困在某一个任务节点中。

(9)

约束(9)保证无人机从舰艇出发,任务结束要回到舰艇。

3 利用双种群优化算法求解

多无人机协同攻击任务规划问题是典型的NP-hard问题。和传统的多无人机协同攻击任务规划相比,多舰载无人机协同海上目标攻击任务规划,存在无人机放飞点、返航着舰点的选择不唯一,且放飞、返航着舰点都存在窗口时间,因此该问题的约束条件更强。以传统的方法求解,算法很容易陷入收敛停滞,Pareto前沿的可行解更难以求得。本文采用双种群算法[8](Double Population Optimization Algorithm,DPOA)对其进行求解。其步骤为:

第一步:初始化系统,设置可行解种群规模大小、不可行解种群规模大小、交叉概率、变异概率以及最大迭代次数。

第二步:随机产生初始解,并按照约束条件,生成初代可行解种群,不可行解种群。

第三步:判断迭代循环条件,若达到最大迭代次数则退出运算;若不满足,进入第四步。

第四步:将可行解种群、不可行解种群分别依照预设概率进行交叉、变异,并对可行解种群、不可行解种群分别进行更新。

第五步:自增迭代次数,跳转至第三步。

3.1 基因编码及种群的更新

单无人机染色体编码仍采用经典的编码方式,以m+4维整数向量的编码方式进行编码,如式(10)所示:

(10)

其中,固定第一位染色体编码为起降点VS中随机一个元素,作为无人机放飞的起降点。第二位至第m+2位染色体,则为攻击目标集VT与起降点集合VS中随机的一个元素并集,并对其进行随机排序,代表该无人机对各节点的依次访问顺序。当第i位编码(1≤i≤m+2)为起降点集合VS中的元素时,表明该无人机已经规划出从舰艇出发,返回舰艇着舰的简单路径,i+1～m+2位染色体标识的节点不再进行访问。第m+3位染色体为0-1决策变量yk,标记该无人机是否挂载电子干扰吊舱,第m+4位染色体表示为挂载的武器编号。舰载无人机的全体染色体编码,形成一个n×(m+4)的矩阵,便为一个完整的任务规划方案。

由于染色体编码为单个无人机的染色体向量组合而成的整数矩阵编码,因此遗传操作将矩阵编码拆分为染色体向量,对应染色体向量进行交叉、变异再进行合并。染色体向量的遗传操作与经典遗传算法相同,本文的交叉算子采取部分映射交叉法,变异算子采取两点互换变异[9]。

3.2 种群的更新

(11)

计算最劣Pareto等级个体的拥挤密度,删除拥挤密度较小的个体,直到满足种群规模要求。

不可行解种群的更新与可行解种群更新类似。若不可行解种群大小超过预设种群大小,则保留部分目标空间较优的个体,剔除目标空间劣势个体。式(11)中dii为个体i与个体j在目标函数空间上的欧式距离,N为预设种群规模。

4 仿真实验

4.1 参数的比较实验

以3架舰载无人机协同对6个海上目标进行攻击为例。仿真中主要参数设置如表1～表7所示。给定无人机造价成本为80。表1中,v0～v2为无人机起降点,v3～v8为攻击目标节点。

表1 无人机在各任务节点航行所耗费空中时间

表2 攻击目标价值属性

表3 各武器对目标的毁伤概率

表4 无人机空中续航时间

表5 无人机在各路径航行被毁伤概率

表6 无人机挂载武器造价

表7 舰艇在各起降点的时间窗口

为验证不同参数下算法的可行性与有效性,分别对部分参数进行调整进行纵向对比实验。

算例1电子干扰吊舱造价成本为10,干扰吊舱的效率为0.8。

算例2电子干扰吊舱造价成本为80,干扰吊舱的效率为0.4。

算例3电子干扰吊舱造价成本为80,干扰吊舱的效率为0.8。

表8 算例1仿真结果

表9 算例2仿真结果

表10 算例3仿真结果

从仿真结果来看,各组解均为可行解。其中算例1、算例3中,电子干扰吊舱干扰效率较高,因此规划结果中,各无人机均选择挂载电子干扰吊舱。而算例2中,电子干扰吊舱干扰效率显著下降,且造价提高,因此都没选择挂载电子干扰吊舱。在武器选择方面,大多数都选择对目标毁伤度较高的2号、3号攻击武器,实验结果符合客观事实,任务规划能达到预期效果。

4.2 算法性能的比较实验

采取以经典的NSGA-2与SPEA2等多目标算法进行横向对比实验。为保证公平性,所有算法均采用相同的交叉、变异算子,交叉概率、变异概率和最大迭代次数均相同,分别为0.7、0.3、500。NSGA-2的最大种群规模为160;SPEA2初始种群规模为100,外部归档集种群规模为60,选择策略为锦标赛选择法。DPOA设置可行解种群为100,不可行解种群为60。

三种算法分别对4.1中的三个算例各进行80次实验,并对实验结果进行比较。实验编程方法、运行环境与4.1相同。

为了定量评估算法的求解性能,采用文献11中建议的反转世代距离(Inverted Generational Distance,IGD)进行测试评估。其基本计算公式为:

(12)

式(12)中,P为给定算法在目标空间获得的一个解集,P*为目标空间均匀分布的真实Pareto解集。d(z*,P*)为真实Pareto前沿上的点z*∈P*与P的最小欧氏距离,|P*|为P*的基数。由于本算例中真实Pareto解集为未知,因此P*取三种算法80次实验结果并集的非支配解集进行近似替代。反转世代距离越小,表示算法收敛性和解集的分布越好。

图1～图3分别为三个算例中各算法80次实验全体解集的分布图,表11为三个算例中各算法80次实验的平均反转世代距离以及平均计算耗时。

图1 算例1中各算法解集的分布图

图2 算例2中各算法解集的分布图

图3 算例3中各算法解集的分布图

表11 各算法的平均反转世代距离与耗时

从图1～图3中可以看到,三种算法都收敛,但双种群优化算法在本文算例中解集的分布与收敛情况更好。采用Wilcoxon秩和检验对各组反转世代距离的实验数据进行了显著性比较,显著性水平设置为0.05,双种群优化算法显著优于其他两种算法。本文算例中,因存在时间窗口、以及空中续航时间的约束,可行解基因经过遗传变异操作以后,可能变成不可行解,而不可行解基因经过遗传变异操作以后,可能成为可行解。双种群进化算法避免将可行解与不可行解进行直接比较,将可行解、不可行解同时迭代进化,从而能保留不可行解中的优秀基因片段,使算法有效避免陷入局部最优。

5 小结

本文研究了一种复杂海洋环境下移动起降平台的舰载多无人机任务规划问题,在这一问题的背景下,建立了多目标任务规划模型。针对该模型约束条件强,传统进化算法难以求解的特点,采用了双种群进化算法,仿真结果验证了该算法的可行性。但在算法方面,Harmonic距离要计算个体到种群中其他所有个体的目标空间欧式距离,计算量大,与其他经典优化算法相比,耗时更多。如何减少计算量,提高算法稳定性,还需要进一步深入探讨。