基于交替方向网络进化博弈的无人机集群任务分配

彭雅兰，段海滨，魏 晨

1) 北京航空航天大学自动化科学与电气工程学院仿生自主飞行系统研究组，北京 100083 2) 鹏城实验室，深圳 518000

无人机（Unmanned aerial vehicle, UAV）是一种“平台无人，系统有人”的无人驾驶飞行器.电子信息与人工智能技术的迅猛发展使无人机在战争中的地位日益提高.随着作战任务的多样性、复杂性和危险性不断增强，未来空战的作战方式将不再局限于单机作战，而逐步向无人化、智能化和集群化发展[1].

作为无人机集群自主协同控制技术的重要内容之一，无人机集群任务分配是指基于一定的环境态势信息和无人机集群状态，为每架无人机分配一个或一组有序任务，使得集群综合效能达到最大[2].任务分配问题是一个非确定性多项式（Nondeterministic polynomially, NP）问题，其求解方法有匈牙利算法（Hungarian algorithm）、穷举法（Enumeration method）以及人工神经网络（Artificial neural network, ANN）、遗传算法（Genetic algorithm,GA）等基于现代优化理论的研究方法[3-4].当任务分配问题中涉及的变量规模不断增大时，过大的计算代价是NP问题的求解难点，多数时候，问题求解计算的实时性难以保障，无法满足在线动态任务分配要求.无人机集群动态任务分配本质上是一个多约束、强耦合的复杂多目标整数优化问题，其决策量是离散的，且满足约束条件的解不止一个，需要在解集中选择出能够满足决策者意图的最优解[5].

国内外学者针对无人机集群任务分配展开了诸多研究.针对无人机集群协同搜索任务分配问题，王瑞和肖冰松[6]提出了一种基于改进鸽群优化和马尔科夫链的方法，通过建立蜂窝状环境模型，降低对搜索区域的重复搜索，从而提高了无人机集群任务分配效率；Luo等[7]考虑无人机的有限执行能力和任务资源需求，以全局收益最大化为目标，提出了一种基于拍卖机制的任务分配算法来得到无人机的无冲突任务序列；为研究资源分配对子任务的影响，Zhang等[8]提出了一种基于多目标粒子群优化算法，通过构建多目标分配模型来优化任务资源分配；Yavuz等[9]提出了一种适用于大规模无人机集群任务分配问题的算法，根据位置信息将无人机集群进行聚类处理后再利用匈牙利算法进行任务分配，并利用蚁群算法为每个任务子集规划最优路线；针对多目标监视任务，Li等[10]提出了一种基于惰性贪婪样本的无人机集群任务分配算法，对非单调目标函数进行求解，并通过调整采样频率来优化任务分配效率.

交替方向法（Alternating direction method of multipliers, ADMM）是一种典型利用“分而治之”思想的算法[11].近年来由于在统计学习、语音识别与图像处理等领域中，对大规模非光滑系数优化问题求解的迫切需求，交替方向法得到了大量关注和研究[12].交替方向法采用分解-协调过程，分步协调各个子问题的解决方案，以寻求全局最优，在凸函数优化问题上显现出良好的求解效果.针对单个无人机任务策略生成问题，考虑无人机多类属性与任务需求多元素制约，利用交替方向法将单无人机任务收益函数中的多个变量进行拆分求解.

无人机集群协同任务分配问题中涉及多个智能体之间的冲突与合作，为解决这一问题，网络进化博弈在问题建模和算法设计方面都有较好优势[13].将每架无人机定义为一个博弈参与者，利用网络进化博弈的纳什均衡策略，通过参与者与邻居间的信息交互进行自身行动策略调整，最终达到全局最优策略.

本文设计了一种基于交替方向网络进化博弈的无人机集群任务分配算法，融合交替方向法与网络进化博弈算法的优势，将无人机集群任务分配过程拆分为局部收益优化与全局收益优化两部分.首先，考虑无人机自身能力特性与任务资源需求异质性，求解单无人机局部最优收益任务分配策略.最后，利用网络进化博弈模型，考虑任务执行过程中机间协作与冲突，通过每个博弈参与者与邻域内无人机个体进行实时信息交互，从而得到全局最优任务收益分配策略.

1 系统建模

1.1 无人机集群任务分配模型

无人机集群任务分配问题可描述为：求得一个N架无人机协同执行M项任务的无冲突全覆盖任务分配方案，以最大限度提高无人机集群完成所有任务的全局收益与执行效率.全局收益函数为局部收益函数之和，任务执行成本是每个局部收益函数的重要因素.

1.1.1 代价函数设计

假设无人机集群U={ui|i∈ (1,2,···，N)}协同执行任务集合，其中N为总无人机数量，M为总任务数量[14].对于无人机i，其可单独执行的任务集合为，si为的子集，无人机i可执行的备选任务组合为式中ni为所有子集总数.为简化分析，假设每架无人机可执行任务组合都存在一个非空可执行任务子集.对于无人机集群协同任务分配问题，假设当且仅当两架无人机共同执行同一任务时，两架无人机之间存在通信链路并进行信息交互，与无人机i有信息交互的所有无人机组成无人机i的邻居集合Ψi，表示为：

由于无人机能力特性与每项任务执行资源需求不同，所以各架无人机执行不同任务时的执行成本也有差异.为有效完成某一项任务，无人机需要向任务点位置移动，且无人机需要具备完成该任务的载荷资源，因此，考虑任务执行成本由负载成本与航路成本组成.任务所需执行时间越长，无人机需要携带的燃料就越多，即负载成本随实际执行时间单调增加，无人机i执行任务组合si的负载成本LCi(si)具体计算公式为[15]：

其中，α1与γ1为负载成本系数，β为负载成本衰减因子，Rk为任务k的资源需求量，LDi为无人机i的载荷能力，tsj为任务j开始执行时间，etj(si)为任务j实际开始执行时间，具体计算公式为：

航路成本PCi(si)计算公式为[16]：

其中，α2为航路成本系数，MFLi为无人机i的最长飞行航路，TPLi为无人机i的总飞行航路长度，其具体计算公式为：

无人机i对任务组合si的任务执行成本为上述负载成本与航路成本之和，即：

在此无人机ui对任务组合si的任务执行成本函数基础上，给出了全局任务执行成本函数[17]：

1.1.2 任务分配模型

无人机集群任务分配目标就是找到全局任务执行成本最小的无冲突、全覆盖任务分配方案，可将该问题描述为不等式约束下的最小化问题.受现有模型启发[18-20]，无人机集群任务分配模型可以定义为：

每架无人机需要具备能够顺利完成已分配任务序列的载荷资源，即任务资源需求约束；在携带资源有限的条件下，每架无人机任务航路总长度不得大于其最大飞行距离，且需要平衡每架无人机剩余飞行长度距离，以确保整个无人机集群执行能力的持久性；每项任务的实际开始执行时间需满足其执行开始时间窗约束.

1.2 网络进化博弈模型

针对无人机集群任务分配问题，构建网络进化博弈模型G={U,{Si},{Ai}}，将每架无人机ui∈U定义为博弈参与者，对于无人机ui，其可执行任务序列si∈Si作为其行动策略[21].为实现集群整体任务效用Ai最大化，每个博弈参与者都会根据自身邻域Ψi中邻居策略与收益，在行动策略集中不断迭代更新自身策略.

对于可行任务组合si∈Si与未被分配任务集合为T0(s)，证明F(T)的最优解与最优任务分配方案之间的等效性：

定理1对与∀j∈M，公式（8）的最优解始终是无人机集群最优任务分配解.

证明：假设s*是公式（8）的一个最优解，但不是无人机集群最优任务分配解，则必定存在一个子任务tk没有被分配给任何一架无人机.由此，可得到一个将任务tk分配给无人机ui的新任务分配解≠s*，.根据公式（6）和公式（7），可得：

当s*不是最优任务分配解时，不可能是公式（8）的最优解，即如果s*是公式（8）的最优解，则必然是无人机集群最优任务分配解.

定义1 纳什均衡[22]：对于有限策略集博弈模型G={U,{Si},{Ai}}，当任何一个参与者在某策略组合下单方面改变自身策略（其他参与者策略不变）都不能提高自身效用时，此策略组合成为纳什均衡.

定义2 势博弈[22]：对于有限策略集博弈模型G={U,{Si},{Ai}}，如果存在一个势函数ξ满足下式，则该博弈模型可成为势博弈.

利用势博弈模型，势函数的最优解即为博弈模型的纳什均衡解，无人机集群分布式任务分配问题可以转化为求解网络进化博弈纳什均衡解，得到最优任务分配策略.

2 基于网络进化博弈与交替方向法的分布式任务分配算法

2.1 交替方向法

交替方向法是一种适用于解决分布式凸函数优化问题的简单且强大的算法，求解过程中对变量进行交替迭代处理[23].交替方向法可有效解决如下形式优化问题：

其中，h和C是凸函数.该优化问题可写为另一种形式：

其中，g是C的指标函数，z是单独变量，u是原始变量.

增广拉格朗日函数定义为[24]：

其中，ρ为惩罚参数，a为缩放后的对偶参数.交替方向法通过以下三个步骤将全局优化问题分解为两个可分离变量的子问题，并分别对u和z进行最小化处理：

除此之外，交替方向法还可以扩展到具有多个可分离变量、非凸函数优化问题或者具有不等式约束的优化问题[12].

考虑无人机集群任务分配优化问题，针对1.1.2节中提出的无人机集群任务分配模型（如公式（8）所示），对于无人机ui，当fi(si)取最小值时，无人机个体i达到自身策略最优点.

利用交替方向法求解公式（8）中的目标函数，引入协调变量φ，其增广拉格朗日函数定义为：

其中，λ为对偶因子（拉格朗日乘子），ρ＞0是惩罚参数，为协调变量在当前循环中的实际计算值，将si作为函数变量，对fi(si)进行优化求解，从而求得最小任务执行成本fi(si).交替方向法具体实施步骤如下.

Step 1输入原始数据及参数，包括无人机的最大飞行长度、巡航速度、负载能力，任务的位置、执行时间、开始执行时间窗和负载需求，拉格朗日乘子、惩罚因子等；

Step 2无人机i根据自身性能和任务属性挑选有能力执行的任务，生成初始可行任务组合，并根据公式（6）计算相应的任务执行代价，得到协调变量φ；

Step 3通过优化更新协调变量φ，φ[l]为第l次迭代计算待更新的协调变量，并据此得到更新后的拉格朗日乘子λ：

Step 4若第l次迭代结果满足下列约束条件，则认为此时得到无人机i的最优任务组合si_best，算法停止运行并输出结果，否则，进入下一次迭代计算，跳转至Step2.

其中，σpri与 σdual分别为原始残差和对偶残差.

2.2 无人机集群交替方向网络进化博弈任务分配实现流程

根据2.1节中给出的交替方向法，求得每架无人机ui的最优任务组合si_best，在整个无人机集群中，存在个体间交互与执行任务耦合，借助1.2节中给出的网络进化博弈模型，平衡各架无人机之间的任务冲突，实现全局任务收益最大化.基于交替方向网络进化博弈的无人机集群任务分配算法流程如图1所示.

图1 基于交替方向法网络进化博弈的无人机集群任务分配算法流程图Fig.1 Flowchart of the unmanned aerial vehicle swarm task allocation algorithm, based on the alternating direction method of multipliers (ADMM)network potential game theory

对于第p轮迭代中无人机i的任务组合，记为第p轮循环中所有无人机的任务组合记为假设对于任务集合T，通过广播机制，向所有无人机发送完整任务集信息，根据完整的任务集，每架无人机都可得到自己可单独执行的任务组合Sif.在算法初始化阶段，设置所有无人机属性与任务属性，随机在Sif中选择si1和Si1.完成初始化后，执行交替方向法所有算法步骤，得到每架无人机局部收益最大的任务组合，作为下一步算法初始输入量，再逐步实施算法中剩余步骤.每轮迭代中，无人机i仅与自己邻域内邻居交换信息，由此可给出博弈当前收益Aip、最佳响应Bip和后悔值Rip的计算[24]：

3 仿真实验分析

为验证本文所提出的无人机集群分布式任务分配算法的有效性，以4架无人机协同执行20个目标点的打击任务为例进行仿真验证，并与文献[25]中基于一致性拍卖包算法（Consensus-based bundle algorithm, CBBA）进行仿真实验对比.对每组仿真实验独立运行150次，给出平均数值统计结果，并采用基于Unity3D平台开发的无人机集群三维态势视景仿真综合验证平台对该无人机集群任务分配方法进行演示验证.

在800 m×800 m×800 m三维空间内，4架无人机对随机分布的20个目标点执行打击任务.无人机最大飞行航路MFLi为2000 m，巡航速度V=20 m·s-1，单个任务所需执行时间随机设定为3 s或5 s，对应载荷需求随机设定为2或3，单个任务收益随机设定为5或8，交替方向法中原始残差σpri与 对偶残差σdual均设定为0.01.理想条件下，无人机i可与邻域范围Ψi内所有邻居个体进行信息交互.

任务完成效能指标选取总任务收益、任务完成时间、资源消耗和无人机总飞行航路长度.其中，总任务收益为所有无人机局部收益总和，任务完成时间为无人机集群完成所有任务所需总时长，资源消耗则为完成所有任务所需飞行资源与载荷资源之和，无人机总飞行航路长度为所有无人机任务航路长度总和.

无人机集群在仿真的初始时刻、150、200和300 s的任务分配仿真结果如图2所示，图中红色星号代表任务目标点的当前位置，当某个目标点被成功打击后，将不再显示.由图2可知，在仿真实验最后时刻，无人机集群完成了对所有目标的打击任务.在单个无人机效用函数优化阶段，交替方向法中原始残差与对偶残差随迭代次数的变化曲线如图3所示.在98次迭代时原始残差与对偶残差均收敛至达到最大容错度，所得结果满足任务分配模型中的所有不等式约束条件且能够稳定收敛于最优解.

图2 任务分配结果.(a) 初始时刻; (b) 150 s; (c) 200 s; (d) 300 sFig.2 Task allocation results: (a) initial moment; (b) 150 s; (c) 200 s; (d) 300 s

图3 ADMM的残差收敛曲线Fig.3 Residual convergence curve of the ADMM

如表1所示，本文所提出的基于交替方向网络进化博弈无人机集群分布式任务分配算法(Distributed tasks allocation algorithm, DTAA)在四项指标中均不同程度优于基于一致性的拍卖包算法.在总任务收益方面，分布式任务分配算法较基于一致性的拍卖包算法增长了20.99%；在无人机集群完成所有任务总时间方面，分布式任务分配算法降低了16.50%；资源消耗方面，分布式任务分配算法降低了12.94%；航路总长度方面，分布式任务分配算法降低了12.69%.

表1 本文所提分布式任务分配算法与拍卖算法性能指标Table 1 Performance metrics of the distributed tasks allocation algorithm and CBBA algorithm

无人机集群在两种算法下任务完成度与任务完成个数随时间的变化趋势如图4和图5所示.

图4 任务完成度随时间变化Fig.4 Changes of the degree of completion of tasks over time

图5 任务完成个数随时间变化Fig.5 Changes of the number of completed tasks over time

在任务开始阶段，分布式任务分配算法较基于一致性的拍卖包算法效率优势还不明显，随着任务执行时间的增加，由于设计代价函数时考虑任务点位置与资源消耗等因素，分布式任务分配算法在任务执行中后期仍然能够保证快速针对任务特征分配到具有执行能力的适合执行者.

无人机集群任务分配三维态势视景仿真综合实时推演验证结果如图6所示.

图6 三维视景场景演示.(a) 任务分配场景1; (b) 任务分配场景2Fig.6 3D visual simulation platform snapshots: (a) task allocation scenario 1; (b) task allocation Scenario 2

图6中红色曲线表示无人机飞行轨迹，无人机先后飞抵所有任务目标点并无冲突、全覆盖执行完毕.基于此三维态势视景仿真综合验证平台，可实现无人机集群任务规划与执行情况的动态展示，使决策者便于观察任务执行过程，实时掌握集群整体态势.

4 结论

本文针对无人机集群任务分配问题中各类资源约束的异质性和无人机执行能力因素，将任务分配问题公式化描述为不等式约束下求解最小值问题.利用交替方向法求解单架无人机局部收益最大化任务组合，在网络进化博弈算法中，将每架无人机局部收益最大化任务组合作为初始任务分配方案，每架无人机作为博弈参与者与邻域内无人机个体交换任务策略与收益信息，将全局任务收益最大化作为求解目标进行二次优化.基于本文所建立的无人机集群任务分配网络进化博弈模型，分析了无人机集群最优任务分配策略与网络进化博弈的纳什均衡解的等效性.

通过仿真实验，验证了本文所提出的基于交替方向网络进化博弈的无人机集群任务分配算法可在有限迭代步骤内稳定收敛至最优解，且能够无冲突的分配所有任务目标点.与传统方法比较，在总任务收益、效率、资源消耗和航路总长度方面均有较强优势.最后，通过无人机集群三维态势视景仿真综合验证平台，以实时推演形式给出了无人机集群任务规划与执行的动态仿真过程.