考虑子系统执行能力的多无人机协同任务规划

张鸿运, 王 磊, 张 旭, 丁 宇, 吕 琛, 王昕炜

(1. 大连理工大学数学科学学院, 辽宁 大连 116024; 2. 可靠性与环境技术重点实验室, 北京 100191;3. 北京航空航天大学可靠性研究所, 北京 100191; 4. 北京航空航天大学可靠性与系统工程学院,北京 100191; 5. 大连理工大学工程力学系, 辽宁 大连 116023; 6. 大连理工大学工业装备结构分析国家重点实验室, 辽宁 大连 116023)

0 引 言

随着智能型电子计算机技术的发展,具有高灵活性、高自主性和高智能性的无人机技术迅速成熟起来。在面对突变的战场态势时,无人机可以自主决策[1],大大改进了无人机生存能力低的问题,提高了无人机在作战中的应用优势。无人机的制造成本与寿命周期维护费用远比训练高效的飞机作战人员低。应用无人机替代有人机，可以避免作战人员在紧张情况下出现操作失误,执行侦查敌方复杂环境、打击高危目标等任务时可以避免人员伤亡。此外，无人机还具备体积小、灵活性强、隐蔽性好、续航时间长等特点,在实际作战中发挥着至关重要的作用[2]。相比中大型无人机,小型无人机因其优异的突防能力,被广泛地用于实际作战中。但是，单个小型无人机的执行能力有限,在执行任务过程中面临侦查范围小、执行任务耗时长、攻击力弱等问题,导致作战任务无法高效完成。因此，无人机蜂群协同作战应运而生[3],其不仅可提高任务完成的速度和质量,而且可以通过动态调整任务分配以应对突发状况的出现[4]。为保证小型无人机蜂群协同作战任务的高效完成,有必要对相应的任务分配技术开展深入的研究[5]。

目前,国内外不少学者已经对多无人机协同作战任务分配问题进行了研究[6]。文献[7]针对异构无人机编队在反雷达作战中的协同任务分配问题,提出了一种考虑时间窗的改进混合整数线性规划任务分配算法。文献[8]针对环境中的风险,构造了一种新的分配问题的随机公式,提出了两种动态规划近似方法(一步法和两步前瞻法)，对构建的动态规划问题进行求解。文献[9]扩展了用于连接网络的基线算法处理无人机通信范围有限的问题,提出了基于市场的分散分配算法。但是，传统的优化算法[10-12]只适用于求解小规模任务分配问题。在实际多无人机协同作战任务分配问题中，存在着多种约束条件,如无人机攻击次数约束[13]、任务时序约束[14]、可飞行轨迹约束[15]等,将所有的约束条件整合到任务分配模型中会导致非确定多项式难题[16],计算的复杂度会随着求解规模的增大呈指数增长。新兴的智能优化算法[17]不仅能够降低计算量,而且在有限时间内能快速找到问题的最优解,因此许多学者使用遗传算法[18-19]、蚁群算法[20-21]、果蝇算法[22]、粒子群优化算法[23]、狼群算法[24]等求解多无人机协同任务分配问题。为了提高求解效率,部分学者对现有智能算法加以改进,或进行复合[25]。文献[26]在求解多无人机侦察任务分配问题时,通过对传统蚁群算法进行改进,将信息素分为隶属信息素和序列信息素,同时引入负反馈机制加速算法收敛,该算法综合考虑不同无人机的性能和异构目标的特点，但未考虑需要对目标执行多个任务，以及任务之间存在时序的情况。文献[27]在求解多功能异构无人机任务分配问题时,通过引入多群机制提高果蝇优化算法的全局搜索能力,在基于气味的搜索阶段进行双搜索策略切换,而在基于视觉的搜索阶段使用贪婪选择策略达到快速寻优的目的,但该算法缺乏对执行目标差异的考虑,并且在求解大规模任务分配问题时会由于搜索强度不足而陷入局部最优。文献[28]根据适应度值对粒子群进行阶层划分,并引入独立权重的思想提高算法的搜索能力,提出的算法可以有效求解复杂约束条件下无人机协同任务分配问题,对于实际作战具有一定贡献价值,但在求解大规模任务分配问题时存在局限性。在众多的智能优化算法中,文献[29]提出的狼群算法由于具有良好的全局收敛性和计算鲁棒性,并且特别适用于高维问题的求解,而在近年来被广为研究。文献[30]通过自适应机制,将增强随机分形搜索中的高斯游走引入狼群算法，提高了算法的收敛精度和鲁棒性。文献[31]采用基于有向图的方法和新的元启发式优化方法共同改进狼群算法,但是有向图解锁方式的引入会降低计算效率和收敛速度。文献[32]在离散的狼群算法中融入粒子群和遗传算法思想,提出的算法在大规模任务分配问题中表现出优秀的搜索能力,但没有考虑时序约束以及无人机和目标的个体差异,不能有效地应用于实际作战。上述研究显示,狼群算法能够高效求解多无人机协同任务分配问题,且在大规模问题的求解上具有更佳的鲁棒性以及效率。但是，在针对其目前的研究中,并没有较全面地考虑实际作战问题中存在的各类约束。

小型无人机由于其自身的优良特性而被广泛地应用于实际作战中,但是小型无人机的体积小,承载资源有限,每架小型无人机至多可执行一次攻击任务。此外,如果无人机反复在敌方空域执行攻击任务,容易被敌方的反导系统锁定,这不仅会导致任务执行失败，而且也会危及无人机自身安全。另外,由于每架小型无人机的用途需求不一致，其配备的各传感器性能存在差异,导致无人机各子系统的装备性能各不相同,定义的子系统能力矩阵直观形象地展示出无人机在各子系统上的差异,并将无人机任务执行能力和子系统能力联系起来。而敌方目标的规模大小、危险性和精密程度因其作用和所处环境的不同而不同,因此目标要求无人机具备的最差装备性能也各不相同,定义的目标能力需求矩阵可直接展示出目标任务之间的差异。然而,现有研究中鲜有考虑包含无人机各子系统执行能力的差异以及目标对无人机能力约束条件的无人机蜂群任务分配问题,而这些限制非常符合无人机作战的实际情况。因此，有必要研究在子系统能力约束条件下的无人机蜂群协同任务分配问题。

本文针对异构无人机蜂群协同任务分配问题建模,在无人机子系统能力约束、任务时序约束和攻击次数约束等多个约束条件下,最小化时间代价和资源代价。根据求解问题的特点,提出一种基于拍卖机制的改进狼群算法(auction mechanism based improved wolf pack algorithm,AMIWPA),引入子系统能力矩阵,从而实现无人机异构性与任务执行能力的统一描述。本文考虑对目标执行多个任务的情况,故采用矩阵编码方式,为了快速求解无人机蜂群任务分配问题,在算法设计过程中融入遗传算法思想,通过相邻行交换操作和间隔列交叉操作实现个体狼的位置更新,并在狼群更新阶段引入第三优狼以增强种群的多样性,有效地避免算法陷入局部最优。此外,提出基于拍卖机制的修正策略，对违反攻击次数约束的非可行解进行调整。将本文提出的算法与基于拍卖机制的改进粒子群优化算法(auction mechanism based improved particle swarm optimization algorithm,AMIPSOA)和基于拍卖机制的改进模拟退火算法(auction mechanism based improved simulated annealing algorithm,AMISAA)进行对比实验,仿真结果表明所提算法具有更好的寻优性和收敛性。

1 模 型

1.1 问题描述

本文以小型无人机群在模拟二维战场环境中对多个目标执行一系列任务为背景,研究多功能异构无人机蜂群协同任务分配的问题。

假设坐落在机场的Nu架小型无人机组成无人机蜂群，对敌方的Nt个目标执行任务,无人机集合为U={U1,U2,…,UNu},目标集合为T={T1,T2,…,TNt},需要对每个目标依次执行识别、攻击和评估。对于目标的这3类任务,要么都执行,要么都不执行,并且任务之间必须严格按照顺序执行。k∈K,K={1,2,3}为对应的任务集合(k=1代表识别任务;k=2代表攻击任务;k=3代表评估任务),Nk表示需要对每个目标执行的任务数量。显然，Nk=3。

在任务场景中,每架无人机都具备3个子系统,分别为识别、攻击和评估,M表示无人机的子系统集合。无人机的异构性主要体现在子系统不同的装备性能上,与无人机配备的传感器有关,使用子系统执行能力衡量子系统装备性能的好坏,进一步评估无人机执行任务的能力水平。例如,无人机U1配备了高分辨率视觉传感器,无人机U2配备了低分辨率视觉传感器,因此无人机U1识别子系统的执行能力可以达到80%,即具有较强的目标识别功能,无人机U2识别子系统的执行能力只能达到20%,视觉传感器的分辨率限制了无人机U2的目标识别功能,无人机U2不能满足对特定目标的识别要求,如小尺寸且构造复杂的目标或背景环境复杂的目标。综上所述,无人机执行任务的前提是必须满足任务要求的执行能力。

为了能直观地反映无人机和目标的异构性,本文定义无人机能力矩阵Xc和目标能力需求矩阵Xcr。无人机能力矩阵展示了每架无人机具备的子系统以及相应子系统的能力值,从而在统一的框架下描述无人机的异构性与任务执行能力。若无人机存在某个能力水平为0的子系统,则表明无人机不具备执行相应任务的能力,间接反映出无人机的异构性;若无人机的某子系统能力水平大于0,则直接反映了无人机执行任务的能力水平。通过与各目标执行不同任务的能力需求进行对比,从而判断无人机是否可以对特定目标执行特定任务。以5架无人机和3个目标为例,表1和表2给出了无人机能力矩阵和目标能力需求矩阵。对于T1的识别任务,由表2可知执行T1的识别任务要求无人机识别子系统达到最低能力值的60%。由表1可知,U1～U5识别子系统的能力值分别为60%、50%、90%、40%、30%,因此只有U1和U3有能力执行T1的识别任务。

表1 无人机能力矩阵

表2 目标能力需求矩阵

为了避免不确定因素对研究问题的影响,现作出如下假设:

(1) 在任务执行过程中,没有禁飞区、地形障碍以及突发威胁;

(2) 目标的地理信息是已知且静止的;

(3) 无人机由当前位置飞到下一位置的距离用欧式距离来计算;

(4) 无人机始终保持匀速飞行;

(5) 不同无人机执行同一任务的耗时相同;

(6) 无人机在执行任务过程中不会被毁坏;

(7) 无人机被分配多个不同种类任务时,执行顺序在前的同类任务优先执行。

1.2 代价函数

由于战场环境的变化莫测,任务执行的时间敏感性极高,因此必须在较短的时间内完成所有任务。由于目标任务的执行按照识别、攻击、评估的顺序进行,为了最小化任务完成时间,也就是尽可能让目标的最后一项任务结束时间最早,因此任务完成时间就是最晚的评估任务结束时间。同时，为了高效利用资源,应最小化无人机消耗的燃油量。

无人机燃油量的消耗主要受飞行路程的影响,由于已假设无人机匀速飞行,飞行路程的长短可以通过飞行时间来量化,因此无人机耗油量可通过无人机总飞行时间来量化。无人机的飞行时间由两部分组成,无人机从初始位置飞向目标的时间和无人机从前序目标飞向执行目标的时间。

定义ui k表示执行目标i的k任务的无人机编号;PTui k表示无人机ui k的执行目标i的前序目标,PTui k=0表示无人机ui k无前序目标,意味着无人机从初始位置直接飞到目标i执行k任务;PTSui k表示无人机ui k的前序任务;TOui k·i表示无人机从初始位置飞到目标i的飞行时间;TPTui k·i表示无人机ui k从前序目标PTui k飞到执行目标i的飞行时间。

因此,目标函数为

(1)

式中:ti k表示目标i的k(k=1,2,3)任务执行完成时间,具体计算公式如下:

(2)

式中:定义ti·0=0。由于目标i评估任务的开始是在识别和攻击任务完成的基础上,根据式(2)，计算ti3时需要先计算ti1和ti2。tk表示k任务的执行时间,目标i的k任务执行完成时间ti k主要受到无人机ui k在前序目标任务执行完成时间、无人机ui k飞到目标i的时间和目标i的k-1任务执行完成时间的影响。当无人机ui k飞向目标i执行k任务,如果TOui k·i时刻无人机ui k到达目标i,目标i的k-1任务未执行完成,无人机ui k需等待目标i的k-1任务执行完成才能执行k任务,则无人机ui k开始执行目标i的k任务的时间为ti·(k-1)=max(TOui k·i,ti·(k-1)),此时无人机ui k执行目标i的k任务的结束时间为ti·(k-1)+tk。如果TOui k·i时刻目标i的k-1任务已经执行完成,则目标i的k任务的执行完成时间ti k受到无人机ui k是否有前序目标任务的影响,若无人机ui k无前序目标任务,则无人机ui k开始执行目标i的k任务的时间为TOui k·i=max(TOui k·i,ti·(k-1)),此时无人机ui k执行完成目标i的k任务的时间为TOui k·i+tk。若无人机ui k有前序目标任务,则无人机ui k开始执行目标i的k任务的时间为tPTui k·PTSui k+TPTui k·i=max(tPTui k·PTSui k+TPTui k·i,ti·(k-1)),此时无人机ui k执行完成目标i的k任务的时间为tPTui k·PTSui k+TPTui k·i+tk。

1.3 约束条件

(1) 每架无人机的攻击次数是有限的,至多执行一次攻击任务。

(3)

(2) 多机协同约束,每个目标上的多个任务可以被不同的无人机执行,但每个任务仅由一架无人机执行一次,且必须保证所有的任务都被执行。

(4)

(3) 无人机子系统能力约束,无人机u对目标i执行k任务必须满足相应子系统的能力值高于目标i的k任务要求的最低能力值。

(5)

(4) 任务时序约束ti k的计算如式(2)所示。式(2)由两项构成,前项是任务开始执行时间,主要受到tPTui k·PTSui k、TPTui k·i和ti·(k-1)的影响；后项是任务执行时间,tk为大于零的常数。因此，由式(2)可知,目标i的k任务执行结束时间一定晚于目标i的k-1任务执行结束时间。

1.4 问题建模

本文使用整数规划模型描述多功能异构无人机蜂群协同任务分配问题,优化所有无人机执行任务的累计资源消耗和任务完成时间,构建的数学模型目标函数如式(1)所示，约束条件如式(2)～式(5)所示。

2 狼群算法原理

狼是喜爱群居生活的动物,狼群之间的团结协作一次又一次完成了围捕猎物活动,在捕猎活动中每个个体都有明确的社会分工。根据职责，将狼分为头狼、探狼和猛狼。头狼是离猎物最近的狼,感知到的猎物气味浓度最大,是整个狼群的指挥,指挥狼群朝猎物方向行进并迅速捕获猎物；探狼通过对周围环境进行探索,朝着猎物气味最浓的方向前进；猛狼则负责对猎物进行围攻。狼群相互传递信息,通过分工合作完成猎物的捕抓活动,图1展示了狼群围捕猎物的过程。基于狼群抓捕猎物的行为活动和猎物分配的规则抽象得到狼群算法。狼群算法的主体包括3种智能行为(游走行为、召唤行为、围攻行为)和两条规则(“胜者为王”的头狼产生规则，“强者生存”的狼群更新机制)。

图1 狼群捕猎过程Fig.1 Hunting process of wolves

(1) 头狼产生规则

初始化狼群产生N只狼,选择具有最优目标函数值(感知到的猎物气味最浓)的狼作为头狼。在迭代过程中,如果存在一只狼的目标函数值优于当前的头狼,则进行头狼的更新。如果同时存在多只狼的目标函数值是更优的,则随机选取一只作为新的头狼。头狼不参加后续智能行为，直接进入下次迭代,直至被更优的狼所替代。

(2) 游走行为

在狼群中，除头狼外，位置最优的Snum只狼作为探狼,探狼执行游走行为。Snum随机取[N/(α+1),N/α]中的整数,α为探狼的比例因子。探狼从当前的位置出发,试探性地沿着h个方向向前行走,由于每只探狼存在个体差异,探索环境的细致程度不一致,因此h是从[hmin,hmax]中随机选取的整数。h越大,侦查得越细,游走步长为stepa。记录下沿着每个方向前进一步探狼感知到的猎物气味浓度,每个方向侦察完后让探狼返回初始位置,直至侦查完所有方向,最后探狼沿着猎物气味浓度最大的方向前进，并更新探狼的位置。

比较探狼在新位置上感知到的猎物气味浓度和当前头狼感知到的猎物气味浓度,如果探狼在新位置上感知到的猎物气味更浓,则探狼取代当前头狼成为新的头狼,整个狼群直接开始召唤行为,否则探狼继续执行游走行为直至达到最大的游走次数Tmax。

(3) 召唤行为

Mnum(Mnum=N-Snum-1)只猛狼听到头狼发出的召唤以较大的步长快速地向头狼奔去,奔袭步长为stepb。在奔袭途中,如果猛狼在新位置感知到的猎物气味浓度比当前头狼感知到的猎物气味浓度更浓,则猛狼取代当前头狼成为新的头狼,整个狼群直接开始围攻行为,否则猛狼继续向头狼逼近，直至猛狼和头狼之间的距离小于给定的距离阈值dnear。

(4) 围攻行为

在围攻行为中,猛狼将联合探狼对猎物进行围攻,此时狼群已经比较接近猎物(头狼的位置视为猎物的位置),只需在小范围内进行精细搜寻,因此猛狼和探狼以较小的步长对猎物实施围攻抓捕,围攻步长为stepc。如果猛狼和探狼在新位置感知到的猎物气味浓度比其在原始位置感知到的猎物气味浓度大,则更新其位置,否则保持原始位置不动。

(5) 狼群更新机制

猎物根据由强到弱的原则进行分配,老弱病残的狼奔跑速度缓慢,离猎物较远,只能分到少量食物甚至没有食物,最终会被饿死。因此,目标函数值最差的R只狼会被消灭,为了维持狼群的数量,同时会产生R只新狼。R越大,则新狼的数量越多,有利于维持狼群的个体多样性,但是R的数值不能太大,否则狼群趋向执行随机搜索；同时，R也不能过小,否则不利于维持种群的多样性,并且减弱了狼群开拓搜寻猎物新领域的能力。在每次的捕猎过程中,猎物的大小和数量会有差异,故饿死的狼的数量总是不等的,因此R是[N/2β,N/β]中的随机整数,β是狼群的更新比例因子。

3 基于改进狼群的多任务种类协同分配优化算法

狼群算法适用于变量连续变化的问题,但是任务分配问题是一个离散问题,每个变量都属于整数集合。因此,有必要根据任务分配问题的离散性对个体的编码方式进行改进,使之符合任务分配问题的整数离散特征。对于异构无人机蜂群协同任务分配问题的求解，可以概述为对具有单目标函数和包含多个约束的优化问题的求解,通过种群优化寻找最优分配方案,并将遗传算法思想引入到个体更新中，以实现快速寻优。

狼群算法与异构无人机蜂群协同任务分配问题的对应关系如下:狼个体-可行任务分配方案;狼位置变动-任务分配方案变动;狼感知猎物气味浓度-目标函数值。

3.1 整数矩阵编码

个体狼的编码是异构无人机蜂群协同任务分配问题求解的前提,也是设计狼群算法的关键。狼群中的每个个体都对应着一个可行的任务分配方案,也就是说个体的编码需要给出所有任务的分配情况。针对多功能异构无人机的特性,仅根据目标来分配无人机会导致任务无法完成,这是由于目标不同和任务之间的差异导致对无人机的需求能力不一致,所分配的无人机不一定有能力执行该目标的所有任务,因此需要对目标的每个任务分配无人机。目标和任务是两个不同的维度,因此需引入矩阵编码方式对个体进行编码。

在矩阵编码中,每一行对应一个目标,每一列对应一类任务,需要对每个目标执行3类任务且任务之间必须满足严格的时序约束,因此矩阵有且仅有3列,依次对应识别、攻击和评估任务,矩阵中的编码值表示无人机编号。以5架无人机和3个目标为例,根据矩阵编码方式,个体狼的编码是一个3行3列的矩阵,如图2所示。第1行的3个编码值2、3、5分别表示分配U2执行T1的识别任务,U3执行攻击任务,U5执行评估任务。

图2 任务分配矩阵Fig.2 Task assignment matrix

3.2 种群优化

传统狼群算法主要针对连续问题寻优,更新迭代公式也仅仅适用于变量连续变化的情况。因此，根据本文研究问题的特点,有必要对个体的更新方式进行改进。为了提高算法的收敛速度和寻优能力,需要在个体更新中引入交叉算子,但是个体的更新会导致违反攻击次数约束,对此需要提出基于拍卖机制的修正策略,实现对非可行解的调整,最后在狼群更新阶段引入第三优狼来提高狼群的质量和多样性,避免陷入局部最优。

探狼的游走行为实质上是对解空间的随机探索,为了更高效地获得最优解,需要对解进行合理更新,但是解的变动不宜过小,否则收敛速度缓慢,解的变动也不宜过大,否则会由于搜索不细致从而得不到最优解。因此，根据问题的特点并结合遗传算法中基因片段交叉的思想,游走阶段的个体更新主要是对两个相邻目标编号的stepa个连续任务对应的无人机编号进行互换,即对个体采用行变换操作,将由stepa个位于同行的相邻元素组成的片段与相邻行对应位置的元素进行互换。与一般的更新方式，如随机从矩阵中选取stepa个任务重新分配无人机相比,这样的更新方式更有利于快速收敛到最优解,因为通常而言将目标上的连续stepa个任务分配给同一架无人机执行耗费的时间和资源是最少的。如果目标上的连续stepa个任务由不同的无人机执行,会直接增加无人机飞往目标的时间和资源消耗,而随机从矩阵中选取stepa个任务重新分配无人机会使得连续任务由同一无人机执行的概率大幅下降,降低算法的收敛速度。

游走阶段的更新操作具体实现过程如下:首先，随机生成一个二维数组(i,k),i∈T,k=1,2,3,根据二维数组确定在矩阵中的位置,二维数组中的i表示第i行,二维数组中的k表示第k列,找到对应编码值,将包含该编码值在内且位于同一行的连续stepa个元素组成的片段和相邻行对应位置的编码值进行交换。如图3所示,随机生成的二维数组是(2,1),stepa=2。

图3 游走阶段的位置更新Fig.3 Position update of wandering phase

头狼的召唤行为体现了对狼群的指挥,是猛狼快速收敛到当前最优解的关键,也决定了算法的收敛速度。为了快速向头狼靠拢,个体的更新会参考当前最优个体,从当前最优个体中复制部分信息。具体实现过程如下:首先随机生成stepb个二维数组,根据二维数组确定猛狼编码矩阵的stepb个编码位,从头狼编码矩阵中复制对应编码位的数值。如图4所示,设置stepb=4,随机生成的stepb个二维数组分别为(1,1),(2,3),(3,2),(3,3)。

图4 召唤阶段的位置更新Fig.4 Position update of calling phase

探狼和猛狼的围攻行为可以理解为在猎物周围进行紧密地搜索,避免算法过早陷入局部最优。具体实现操作如下:首先随机生成stepc个二维数组,根据二维数组确定个体狼需要更新的编码位,将需要更新的编码值与间隔列对应位置的编码值交换,若交换的那列超出矩阵的索引范围,则采用模数取余法确定交换的那列。如图5所示,设置stepc=1,随机生成的二维数组为(2,2),位置(2,2)的编码值应该与间隔一列对应位置(2,4)的编码值交换,但目前研究问题只考虑了3类任务,矩阵的最大列数为3,位置(2,4)不存在,因此采用模数取余法,故与第1列对应位置的编码值进行互换,即将位置(2，2)的编码值与位置(2,1)的编码值互换。

图5 围攻阶段的位置更新Fig.5 Position update of sieging phase

在狼群更新中,R只最弱小的狼会被饿死,为了维持狼群的数量,需要生成新狼以实现狼群的进化,传统狼群算法中新狼的产生与初始化种群一样,生成的新狼不具备强竞争力,无法快速收敛到最优解,因此有必要改进新狼的产生方式。通过在种群更新阶段引入头狼、次优狼和第三优狼,让生成的新狼继承强者的优势基因从而增强竞争力,改进的方式既要克服传统狼群算法的缺点，又要提高算法的收敛速度。具体实现过程如下:首先需要确定变异概率a,a是介于0～1的随机数,如果0

3.3 基于拍卖机制的修正策略

由于个体狼的位置更新产生新的任务分配方案,可能不满足无人机攻击次数约束而生成非可行方案,为了对非可行方案进行调整,提出了基于拍卖机制的非可行方案修正策略。

对于新的任务分配方案,首先检查分配方案中执行攻击任务的无人机,如果无人机编号各不相同,说明没有违反约束,否则将违反约束的无人机执行的攻击任务作为拍卖任务,所有拍卖任务构成拍卖任务集。机场发布拍卖活动且每轮只拍卖一个任务,已经执行攻击任务的无人机不再参与竞拍活动,其余有能力执行拍卖任务的无人机根据自身执行任务的目标函数值对拍卖任务进行出价，并将竞拍信息(竞拍任务和竞拍价格)发送给机场,机场从所有接收到的竞拍信息中选择出价最高的无人机。如果有两个或多个无人机出价相同,则从中随机选择一个,再将竞拍结果(竞拍任务和中标无人机)反馈给所有参与本轮竞拍的无人机,已拍卖的任务从拍卖任务集中删除,本轮中标的无人机不再参与后续竞拍活动。

基于拍卖机制的修正策略可以概括为以下4个步骤。

步骤1拍卖任务发布。当前的任务分配方案违反攻击次数约束时,由机场发布拍卖活动,每轮竞拍只拍卖一个任务,如图6所示。

图6 拍卖任务发布Fig.6 Auction task release

步骤2反馈竞拍信息。有能力执行拍卖任务的无人机对拍卖任务进行出价,然后向机场反馈自己的竞拍信息(竞拍任务和竞拍价格),如图7所示。

图7 反馈竞拍信息Fig.7 Feedback on bidding information

步骤3签约。机场对所有竞拍信息进行处理,根据竞拍价格挑选出最合适的无人机,并向所有参与本轮竞拍的无人机发送拍卖结果,如图8所示。

图8 签约Fig.8 Signing

步骤4本轮签约的无人机执行拍卖任务，且不再参与后续拍卖活动,并将已拍卖任务从拍卖任务集中删除,进入下一轮竞拍,直至拍卖任务集为空集。

3.4 基于拍卖机制的改进狼群算法

改进狼群的异构无人机蜂群协同任务分配算法步骤如下。

步骤1初始化狼群以及算法参数。设定参数:种群数量N、最大迭代次数Maxgen、探狼的比例因子α、最大游走次数Tmax、距离阈值dnear、狼群更新因子β、游走步长stepa、召唤步长stepb和围攻步长stepc。

步骤2判断攻击次数约束是否满足。若满足,则转至步骤3;若不满足,采用基于拍卖机制的修正策略,再转至步骤3。

步骤3计算每个个体狼的目标函数值,并对目标函数值进行排序，挑选出头狼。

步骤4判断是否达到最大迭代次数。如果达到则输出最优解,否则转至步骤5。

步骤5判断是否达到最大游走次数。如果达到则转至步骤6,否则继续执行游走行为,若探狼在游走过程中,产生了比头狼更优的解,则取代头狼转至步骤6。

步骤6判断猛狼与头狼的距离是否小于给定的距离阈值dnear。如果小于则转至步骤7,否则继续执行召唤行为,若猛狼在途中,产生了比头狼更优的解,则取代头狼转至步骤7。

步骤7猛狼联合探狼执行围攻行为。

步骤8按照“强者生存”的更新机制实现狼群的更新,再转至步骤2。

综上,AMIWPA的流程如图9所示。

图9 AMIWPA流程图Fig.9 Flow chart of AMIWPA

4 算例仿真

本文在Windows 10 操作系统上,基于Matlab环境实现AMIWPA的仿真实验,PC机配置为11th Gen Intel(R) Core(TM) i5-1135G7@2.40 GHz 2.42 GHz,16G内存。狼群算法的参数设置为:狼群规模大小N=50,探狼的比例因子α=4,最大游走迭代次数Tmax=10,给定的距离阈值dnear=3,狼群的更新比例因子β=0.4,游走步长stepa=2,召唤步长stepb=4,围攻步长stepc=1。此外,无人机对目标执行识别、攻击和评估任务的时间分别为10 min、5 min、10 min。

本文采用3个仿真场景对AMIWPA进行验证,仿真场景1和仿真场景2为小规模,这两个场景主要用于验证AMIWPA算法的可行性和有效性。仿真场景3为大规模,在此场景下将AMIWPA与其他两种改进算法进行对比，进一步验证AMIWPA算法的性能。

本文采用的两种对比算法为AMIPSOA和AMISAA,由于粒子群优化算法和模拟退火算法的标准形式均可用于求解连续型优化问题,因此本文在采用粒子群优化算法和模拟退火算法这两类经典算法求解本文问题时,先对这两种算法进行转化,为了让粒子群优化算法和模拟退火算法的求解效率更高,在转化的基础上做了相应改进,在此简要介绍这两种算法。

在AMIPSOA中,个体采用与本文一致的矩阵编码方式。其中，惯性权重为ω,学习因子c1和c2是随迭代次数变化的量,基于粒子群优化算法的核心思想,个体按照如下方式进行更新：首先随机生成介于0和1之间的更新概率a,如果a<ω,则个体通过变异操作进行更新；如果a

在AMISAA中,个体仍然采用矩阵编码方式,个体的更新主要通过突变的形式，即从编码矩阵中随机选择任务重新分配无人机,对于新解再使用Metropolis准则判断是否可以被接受,若可以被接受,则检查是否违反约束,如果违反,则采用基于拍卖机制的修正策略进行调整；否则直接用新解替换当前解。

4.1 算例1

仿真场景1中有8架无人机和5个目标,表3给出了无人机的初始位置和能力矩阵,表4给出了目标的初始位置和能力需求矩阵,采用本文提出的AMIWPA获得的最优任务分配方案(如表5所示)。为了直观地展示无人机的飞行情况,图10绘制了无人机执行任务的飞行路线。从获得的任务分配方案中可以看出,无人机U1和U4未分配到任务,由于存在任务时序约束,U6先对目标T1执行识别任务,再由U3对T1执行攻击和评估任务。对于T2,U8先对其执行识别任务,随后U2对其执行攻击任务,最后由U8执行评估任务。同样,T3～T5的任务也满足时序约束,由此可知,所有目标的3类任务均满足时序约束且均分配无人机执行,并且每个目标的攻击任务均由不同无人机执行。另外,由目标能力需求矩阵可知,目标T1的识别、攻击和评估任务要求无人机相应子系统具备的最低能力值分别为70%、40%、50%。任务分配方案显示，U6执行目标T1的识别任务,U3执行目标T1的攻击和评估任务。由无人机能力矩阵可知,U6的识别子系统的能力值为70%,U3的攻击和评估子系统的能力值分别为60%和70%,显然满足无人机子系统能力约束。仿真结果与实际问题相符,说明任务分配结果是可行的,因此采用AMIWPA求解异构无人机蜂群协同任务分配问题是可行的。

表3 算例1无人机参数设置

表4 算例1目标参数设置

表5 算例1任务分配方案

图10 算例1无人机飞行路径Fig.10 Unmanned aerial vehicle flight path in case 1

4.2 算例2

为了进一步验证AMIWPA的有效性,将问题规模扩大,仿真场景2中有15架无人机和8个目标,表6和表7具体给出了无人机和目标的相关参数设置。

表6 算例2无人机参数设置

表7 算例2目标参数设置

采用AMIWPA对算例2进行求解,获得的任务分配方案如表8所示,相应无人机的飞行路径如图11所示。由算例2可以看出,随着仿真场景规模的扩大,AMIWPA仍然能够有效地求解考虑子系统能力约束的无人机蜂群任务分配问题。例如，对于目标T4的任务分配,先由U6对T4执行识别和攻击任务,再由U7对T4执行评估任务,从最小化资源消耗的目的出发,由一架无人机执行完目标的所有类任务为最优选择。但是结合本文研究问题的特点,无人机子系统能力约束的限制使得T4的评估任务不得不分配给其他无人机执行,因为U6评估子系统的执行能力远低于T4评估任务的需求能力。算例2的仿真结果表明,采用AMIPWA求解考虑子系统能力约束的无人机蜂群任务分配问题是十分有效的。

表8 算例2任务分配方案

图11 算例2的无人机飞行路径Fig.11 Unmanned aerial vehicle flight path in case 2

4.3 算例3

为了进一步验证AMIWPA在异构无人机蜂群任务分配应用下的稳定性和收敛性,进行仿真对比实验,将AMIWPA与AMIPSOA、AMISAA进行比较,采用3种算法对仿真场景3(100架无人机和80个目标)下的异构无人机蜂群协同任务分配问题进行求解。每种算法独立求解20次,最大迭代次数为1 000,获得的目标函数值的统计结果如表9所示,表9包含20次求解获得的最小值fbest、最大值fworst、平均值favg以及每种算法的平均计算时间Tavg，以及最优值的标准差std。

表9 3种算法在算例3中运行20次获得的目标函数值

由表9中的结果可知,AMIWPA的整体性能优于其他两种改进算法。一方面,AMIWPA在多次求解中获得的最优值的标准差比AMIPSOA和AMISAA获得的标准差小,说明AMIWPA具有较好的稳定性。另一方面,在20次求解中,AMIWPA获得的最差目标函数值比AMISAA和AMIPSOA获得的最优目标函数值更优,说明AMIWPA在每次求解中获得的最优解始终优于其他两种改进算法获得的最优解。此外,采用AMIWPA求解的计算时间也是最短的。因此,与AMISAA和AMIPSOA相比,本文提出的AMIWPA具有更好的稳定性和寻优能力。

为了直观地对AMIWPA的收敛性进行分析,绘制了3种算法在仿真场景3中求解异构无人机蜂群协同任务分配问题得到的收敛曲线,如图12所示。

图12 算例3中3种算法收敛曲线对比Fig.12 Convergence curve comparison of three algorithms in case 3

随着迭代次数的增加,3种算法得到的目标函数值均呈现下降的趋势,其中AMIWPA的下降速度最为显著,AMISAA次之,二者呈现近似指数的收敛速度;AMIPSOA的收敛速度最为缓慢,呈现近似线性的收敛速度。另外，3种算法获得的解均被优化,其中AMIWPA的解优化强度最大。因此，所提算法不仅具有最快的收敛速度，还具有最强的优化能力,具体原因分析如下：首先,AMIWPA融入了遗传算法中的染色体交叉变异思想,有效地提高了种群多样性。其次,狼群算法本身独特的三阶段搜索方式和本文改进的更新方式加强了解空间的探索,提高了算法的搜索能力。此外,引入基于拍卖机制的修正策略可以获得局部最优解,从而加速寻优历程,相比随机地处理非可行解,还提高了计算效率。最后,不同于传统的狼群算法,AMIWPA在种群更新阶段引入第三优狼来产生新狼,不仅增加了种群的多样性，还可以有效地避免局部极值。

由上述3个算例可以明显看出,不管是对于大规模场景还是小规模场景,AMIWPA在求解异构无人机蜂群协同任务分配问题上都具有良好的性能,且在大规模任务场景下,相比于其他两种改进算法,AMIWPA不仅能够有效跳出局部最优位置,而且拥有更好的稳定性、寻优性，以及更快的收敛速度。

5 结 论

利用狼群算法适用于求解大规模离散优化问题的特点,针对子系统能力约束条件下的多机协同任务分配问题,提出了一种融合拍卖机制和带有遗传算法特点的狼群算法。对于无人机之间以及目标之间存在的差异,提出的能力矩阵直观形象地将无人机异构性与子系统能力、目标异构性与目标任务需求能力两两关联；根据任务的异构性,结合无人机子系统能力,构建异构无人机蜂群协同任务分配问题模型,将任务完成时间和无人机燃油消耗作为评价指标,考虑了子系统能力约束、攻击次数约束和任务时序约束等多个约束。此外,在狼群算法中引入遗传算法思想实现头狼、探狼和猛狼位置的更新，以实现快速寻优,采用基于拍卖机制的修正策略处理非可行解以提高计算效率,并在狼群更新阶段引入第三优狼提高狼群的质量和多样性。最后，通过3个模拟仿真实验,验证了本文所提算法的性能。