基于改进狼群算法的多无人机协同多目标分配

2022-10-09周同乐韩增亮

导航定位与授时 2022年5期

周同乐，陈谋，韩增亮，王勤

(南京航空航天大学自动化学院，南京 210016)

0 引言

在航空航天领域，无人机(Unmanned Aerial Ve-hicle，UAV)是近年来最有前途和挑战性的军事装备之一。无人机具有造价低廉、使用方便、隐蔽性好、作战范围广、能够避免人员伤亡的特点，在未来空战中的地位与作用不断提升，受到了各大军事强国的广泛关注。

为了提高作战效率，提升无人作战系统对敌杀伤概率，多无人机协同作战已成为新的发展趋势。相较于单机作战，多机协同作战的探测范围更加广泛、干扰范围更加广阔，且杀伤能力更加强大。研究无人机对敌目标的任务分配，对有效地毁伤敌方目标，保障我方无人机安全，充分发挥无人作战飞机的作战效能，降低战争开销具有重要的军事意义。

无人机协同任务分配在现代信息化战争中发挥着极为重要的作用，其相关技术得到了国内外学者的广泛关注和研究。对于双机追逃问题，多采用微分对策和矩阵对策法，文献[6]将微分对策与机器博弈相结合，基于机器博弈中的变值思想，改进了传统的单纯以角度最优作为代价函数的微分对策模型。文献[7]研究了基于博弈论的无人机战场攻防决策算法，通过零和博弈计算得到无人作战飞机应对策略集合。为了有效处理战场信息的不确定性，贝叶斯网络经常用于无人机的任务分配及其评估技术研究。动态贝叶斯网络基于先验知识进行推理和学习，能够有效地处理空战环境中的不确定性。文献[10]对无人空战整个过程进行分析，基于这些态势因素建立无人作战飞机任务分配模糊贝叶斯网络，实现无人机任务分配。

除上述方法之外，针对多无人机协同多目标任务分配问题，启发式搜索算法具有较好的鲁棒性、灵活性和分布性，得到了国内外学者的关注与研究。文献[12]分析了无人作战飞机攻击排序对任务总收益和代价的影响，运用遗传算法(Genetic Algorithm，GA)求解动态环境下多无人机协同任务分配问题。为了克服粒子群(Particle Swarm Optimization，PSO)算法的不足，避免陷入局部最优，文献[13]提出了基于量子粒子群算法实现多机协同任务分配。此外，蜂群算法和狼群(Wolf Pack Search，WPS)算法等启发式全局智能优化算法也在解决无人机任务分配问题上得到了广泛应用。WPS算法作为一种新型启发式全局智能优化算法，基于自然界中狼群的活动行为在搜索空间内进行寻优。自然界中，狼群组织严密，等级森严，分工明确，一般情况下分为头狼、探狼和猛狼三种等级，通过每匹狼各自履行自己的职责进行团结协作。

狼群算法相较于粒子群算法、遗传算法等启发式算法，求解精度更高，收敛速度更快。文献[17]提出了基于领导者策略的狼群算法，在寻优过程中由领导者指引搜寻全局最优解，通过实验证明了基于领导者策略的狼群算法具有更高的搜索效率。文献[18]将狼群置于文化算法种群空间，并依据头狼位置建立信仰空间，仿真实验表明该算法收敛速度与寻优精度均得到加强。为了保持WPS算法的随机性和多样性，文献[19]增加了随机生存更新规则，并将算法应用于求解PID控制问题。文献[20]在传统WPS算法的基础上，融入非线性单纯形法，增强局部搜索能力。文献[21]基于改进狼群算法解决无人机路径规划问题，该方法由头狼利用映射、扩展和收缩产生新的航路点，不断向最优航路点靠近，取得较好的优化效果。传统改进群智能算法的措施虽然能够在特定问题中发挥一定的作用，但在多无人机协同多目标任务分配问题中依然存在着鲁棒性差、泛化能力弱以及易陷入局部最优等问题。

鉴于狼群算法的优越性，本文提出了一种基于多策略规则的新型狼群算法，主要创新点如下：

1)根据狼群的不同分工以及搜索属性，建立了基于自主游走机制的头狼产生规则；

2)设计了基于多策略知识库的探狼游走机制和基于自适应动态调整步长的猛狼奔袭和围攻方式，取代了传统狼群算法单一的搜索机制。

从而对狼群算法的随机性进行智能化约束与控制，保证算法能够高效智能地解决多无人机协同多目标任务分配问题。

1 问题描述

本文研究了架无人机对个敌方目标场景下的任务分配问题。分配原理如图1所示。

图1 多无人机协同多目标任务分配原理图Fig.1 Schematic diagram of multi-UAV cooperative multiple targets task assignment

当确定无人机集合和目标集合后，在空战环境的影响下，分析执行各个任务的收益和代价，形成无人机任务分配方案，确定每架无人机具体的任务集合。

首先，定义决策变量为

(1)

在此基础上，针对实际空战中战场环境以及无人机性能，结合任务目标，建立多无人机协同多目标任务分配目标函数。任务分配目标函数主要考虑以下几个方面：

1)空战态势。即环境中目标与无人机的相对态势因素，空战态势函数设计为

=++

(2)

其中，为角度优势；为距离优势；为能量优势；、、为权值因子。

2)攻击代价。攻击代价包括威胁代价、航程代价和目标意图代价。

威胁代价，指无人机攻击任务目标时，可能受到对应目标的攻击被毁伤而产生的代价，无人机攻击目标的威胁代价1具体设计为

(3)

式中：为与目标最近的威胁源的威胁程度；为与作战目标最近的威胁源之间的距离；为无人机被目标击毁的概率。

无人机攻击目标的航程代价2具体设计为

(4)

式中：为无人机与目标的距离；为无人机集合与目标的最大距离。

目标意图代价，目标对无人机的意图越危险，其对无人机的意图代价越大。具体如表1所示。

表1 目标意图代价表

3)攻击收益。攻击收益主要由无人机对应目标的价值决定，无人机攻击目标的攻击收益为

(5)

式中：为无人机对目标的毁伤概率；为目标的战略价值，由目标本身的类型及战略重要程度决定。

4)无人机性能。无人机相对于目标的性能优势设计为

式中：和分别为无人机和目标的性能参数，与无人机运动能力、通信能力、载荷能力及攻击范围相关。

综上所述，充分考虑空战环境态势、攻击收益代价及无人机性能，建立如下目标函数

(6)

式中：为无人机完成所有任务的时间。

约束条件为

(7)

(8)

max{}≤

(9)

约束条件(7)保证所有敌方目标均会被攻击到；约束条件(8)为无人机使能约束，即分配给无人机的任务总量不应超过其载弹量；约束条件(9)为时间约束，即无人机需在指定时间内完成所有任务，其中为无人机的飞行速度。

2 WPS算法搜索策略

对多无人机协同多目标任务分配模型的求解可以抽象成对目标函数(6)及约束条件(7)、(8)与(9)的优化问题。本文基于多策略规则的新型狼群算法，通过多种规则提升了WPS算法的搜索效率，以获得最终的任务分配结果。

狼群行为示意图如图2所示。

图2 狼群行为示意图Fig.2 Schematic diagram of wolf pack behaviors

头狼具有领导作用，需要指挥狼群的各个成员尽快捕捉到优质的猎物；探狼负责打探游猎，通过感知猎物气味判定与猎物的距离，并把猎物信息实时汇报给头狼；狼群中剩下的所有狼称为猛狼，主要负责围攻猎物，当头狼接收到探狼发送的猎物信息后，召唤猛狼对猎物发起围攻。当狼群捕获到猎物后，将根据发现并抓捕猎物的顺序对猎物进行分配，能力越强的狼将优先分配到充足食物而能够继续保持强健体魄，少数弱小且贡献小的狼则会因为食物紧缺而被自然淘汰，保证了狼群的优质性。

根据狼群的这些特征，WPS算法将寻优过程与狼群捕食猎物过程相对应，通过游走、召唤、围攻三种智能行为对目标进行寻优。为了提高WPS算法的搜索效率及避免陷入局部最优，本文在以下几个方面进行了改进。

2.1 基于自主游走机制的头狼产生规则

头狼即具有最佳目标函数值的人工狼。在迭代过程中，若出现具有更高目标函数值的人工狼，则需要对头狼位置进行更新。

为了加快狼群算法的收敛速度，在围攻行为结束之后，头狼进行自主游走。即对头狼附近区域进行进一步开拓与搜索，保证头狼的优越性。

2.2 基于多策略的探狼游走规则

探狼游走是狼群算法中搜索行为的核心，为了提高狼群算法的解算效率与优化质量，设计了一个包含多策略游走规则的专家知识库，取代传统狼群算法中的探狼随机游走行为。多策略探狼游走规则示意图如图3所示。

图3 多策略探狼游走规则示意图Fig.3 Schematic diagram of multi-strategy search wolves scouting rules

基于个体知识的探狼游走规则

传统的探狼游走规则是WPS算法最基本的搜索规则，能够保证算法最基本的搜索能力。因此，为了维持新算法的基本搜索能力，仍保留原有的探狼游走规则。第个搜索空间内探狼第个游走位置,为

,=,+rand(1,-1)·(,-,)

(10)

式中：,为第个探狼的位置，,∈{1,2,…，}且≠。

基于历史知识的探狼游走规则

为了提高算法的收敛速率，探狼会优先向记忆中的最佳位置进行探索，具体形式为

(11)

基于信息交互的探狼游走规则

为了提高探狼的寻优能力，与当前局部最优解进行信息交互，具体形式为

(12)

式中：,为取值范围[0,1]的随机数；,为取值范围[-1,1]的随机数，且≠。

基于反向精英策略的探狼游走规则

为了避免WPS算法陷入局部最优，一部分探狼向远离头狼的位置对新的猎物进行探索。

(13)

最终，探狼按式(14)更新自己的位置。

(14)

式中：为概率因子，依照均匀分布[0,1]随机取值。

2.3 基于自适应步长的猛狼奔袭和围攻方式

头狼发起召唤，吸引猛狼靠近，当猛狼距离头狼还有一定距离时，猛狼以较大奔袭步长向头狼迅速靠近；当猛狼逐渐靠近头狼后，以较小步长在猎物附近进行小范围精细搜索。自适应步长调整示意图如图4所示。

图4 自适应步长调整示意图Fig.4 Schematic diagram of adaptive step length adjustment

随着迭代次数值的增加，狼群搜索步长将基于线性变化进行自适应调整，具体形式为

(15)

3 基于多策略狼群算法的多无人机协同多目标任务分配

在多无人机协同多目标任务分配中，搜寻最优解的过程即是为无人机搜寻最优的任务目标集合。因此，无人机序列编号以与目标序列编号相对应的方式来表示无人机的分配方案。

具体编码方式如图5所示。

图5 多无人机协同多目标任务分配编码方式示意图Fig.5 Schematic diagram of multi-UAV cooperative multiple targets task assignment coding scheme

图5中，每一个双向箭头表示将对应编号的目标分配给相应编号的无人机。

针对多无人机协同多目标任务分配问题，分别定义人工狼距离、游走算子和召唤算子。

人工狼距离，人工狼与之间的距离定义为

(16)

式中：⊕表示异或操作。

游走算子(,)，设人工狼的位置为=(1,2,…,,…,)，根据探狼游走规则，取其中两个互不相同的元素和，组成一个二维数组(,)，,∈{1,2,…,}且≠，执行游走算子(,)操作,即随机生成个二维数组，并按顺序将相应位置编码的数值进行交换。

召唤算子(,,)，设人工狼的位置为=(1,2,…,,…,)，头狼的位置为=(,,…,lead,…,lead)，召唤算子(,,)表示从中随机选取长度的子序列替换中相同位置的编码值，并对其他位置编码值进行调整,以保证所有编码值仅出现一次。

基于狼群算法的多无人机协同多目标任务分配具体步骤如下。

3.1 初始化

将狼群捕猎空间即任务分配方案的搜索空间抽象为×的欧式空间，其中为人工狼群初始化后的人工狼总数，为我方无人机序列与目标无人机序列的编码长度，以人工狼的位置=(1,2,…,,…,)表示任务分配方案，元素表示第个人工狼第位编码的值，当=时表示将目标纳入无人机的任务集合。人工狼通过目标函数值调整位置，进行寻优，这里选用式(6)的目标函数，即