基于任务拆分的多无人机任务分配多目标优化*

张 曼，王 桢

（解放军92728 部队，上海 200436）

0 引言

在现代战场上，无人机因其灵活机动、隐蔽性佳等特点而被广泛用于侦察、攻击等作战任务。随着现代战争模式的发展，无人机单机的机动性、敏捷性已不能满足复杂的任务需求，要求无人机具备多机协同作战的能力［1］。美国多所军事院校、科研单位、军火公司都曾以全球鹰、捕食者、X-45、X-47为对象，研究多无人机协同任务分配及协同控制问题［2］。多无人机系统是由多架同构或异构无人机组成，相比于单架无人机具有明显的优势，多无人机的任务规划问题是其进行高效协同作战的关键［3］。如何实现多个任务目标的最优分配一直是当前研究的重点。

现有对于多无人机任务分配的研究主要集中在多无人机任务分配问题建模和求解方法两方面。大多数学者［4-9］考虑任务成本最小或效用最大，研究单目标多无人机任务分配优化问题。也有学者兼顾无人机任务成本和收益，研究多无人机分配双目标优化问题，综合考虑无人机任务航程和任务完成时间，见文献［10-13］。

上述研究均假定一项任务可以被单架无人机执行，未考虑多架无人机共同执行某项任务的情形，实际作战环境下，一个目标被摧毁经常需要多个无人机的资源，需要多架无人机对目标进行攻击。文献［14-16］考虑了目标资源需求和无人机资源约束，使多无人机联盟同时攻击目标，但只考虑无人机任务时间最短，未考虑无人机任务成本，造成无人机数量较多，我方无人机群代价增加。

本文针对同一构型攻击无人机群对战区任务目标攻击任务分配问题进行研究，考虑无人机资源约束和任务目标点资源需求，在有效任务时间窗的前提下，考虑目标点任务需求可拆分，放宽无人机群同时攻击约束，以无人机群执行任务成本最小和攻击目标收益最大为目标，建立基于任务拆分的多无人机任务分配多目标优化模型，并设计多目标禁忌搜索算法获得Pareto 最优解集，为多无人机协同作战任务分配网络优化理论提供参考。

1 模型构建

1.1 问题描述与假设

某个发射/回收站有多架攻击型无人机，要出发执行战区的目标攻击任务，战区内存在多个任务目标，任务目标的初始位置已知，根据攻击任务目标的资源需求以及无人机群携带的资源量，指派合适的无人机对任务目标进行攻击。

针对多无人机任务分配问题具体情境，作出如下假设：

1）发射/回收站和可用无人机数量以及具体位置已知；

2）攻击目标所需资源数量已知；

3）假定无人机以固定的高度和速度巡航，不考虑无人机的飞行高度和俯仰角等限制，模型简化在二维平面。

1.2 符号定义与说明

V：V＝｛i|i=0，1，…，n｝，所有节点的集合，0 代表发射/回收站，｛1，2，…，n｝代表n 个任务目标点；

K：表示可用无人机数目的集合，K＝｛k|k=1，2，…，m｝；

Q：无人机携带的最大资源数量，同一类型无人机携带的资源数量相同；

qi：攻击任务目标点i 的需要的资源数量，其中i=1，2，…，n；

dij：任意两个任务目标点i 和j 之间的距离，其中i，j=0，1，…，n；

D：从发射/回收站出发的无人机在每一次执行任务中的最大航程；

d0n：从发射/回收站到任务目标点n 的距离，可通过任务目标点距离数据累加得到；

tki：无人机k 到达任务目标点i 的时间；

tij：无人机从目标点i 飞到目标点j 所用的时间；

yki：无人机k 攻击目标点i 的资源数量；

uki：无人机k 执行攻击目标点i 所耗费的时间；

wki：无人机k 在目标点i 的盘旋等待时间，wki；

［ETi，LTi］：攻击目标点i 的有效时间窗，在此时间窗内，攻击目标点所得收益不为0；

c0：单架无人机执行任务时航程单位距离成本；

c1：无人机早于目标时间窗到达，盘旋等待的单位时间成本；

vi：任务目标价值；

xijk=1 第k 架无人机攻击目标i 后攻击目标j

0 否则 ；

yki：无人机攻击任务目标点i 消耗的资源数量。

1.3 无人机执行任务收益水平测度

多无人机协同任务分配网络中，无人机任务收益与目标价值以及无人机开始攻击目标的时间有关。当无人机k 到达目标点i 的时间ti≤ETi，无人机执行任务收益水平最大，等于任务目标价值；当无人机攻击目标点的时间ETi＜ti＜LTi，收益随时间递增衰减；当无人机攻击目标点的时间ti≥LTi，此时任务收益水平为0。

式（1）为无人机执行任务收益水平函数。

1.4 基于任务拆分的多无人机任务分配多目标优化模型

引入攻击目标收益水平函数，建立基于任务拆分的无人机任务分配多目标优化模型。

1.4.1 目标函数

1.4.2 约束条件

式（2）和式（3）为目标函数，表示最小化任务总成本和最大化攻击任务目标总收益；式（4）和式（5）表示每个任务目标点至少被分配给1 架无人机；式（6）和式（7）表示攻击任务目标点的资源需求约束；式（8）和式（9）表示无人机携带任务资源能力约束和最大航程约束；式（10）表示无人机到达下一个任务目标点的时间；式（11）和式（12）表示无人机从发送/回收站出发，最终回到发射/回收站。

2 求解算法

研究表明［17-19］，禁忌搜索算法可有效求解多无人机任务分配问题。禁忌搜索算法［20］是GLOVER于1977 年提出，通过引入的存储结构和相应的禁忌准则以避免迂回搜索，由藐视准则赦免一些被禁忌的优良状态，以达到全局优化。基于此，本文结合多无人机任务分配模型特性，设计三阶段禁忌搜索算法，采用新的任务目标分配策略，针对本文提出的问题进行求解。算法操作规则如下。

2.1 初始解生成

采用新的任务分配策略，设计三阶段法构造初始解。具体步骤如下：

Step 1 采用最近距离插入法，从离发射/回收站最近的任务目标点i 开始，搜索距i 最近的目标点j 作为下一个目标点，如此根据输入目标点数量生成一组任务目标序列Ii：

Step 2 根据无人机最大资源约束将Step 1 所得Ii转换成多无人机任务分配序列Kk；

Step 2.1 根据Ii，设无人机已经消耗的资源量expend-Q=0，已攻击的目标数indextas=0，令i=1，j=i+1 从任务目标序列中第一个任务目标点开始判断；

Step 2.2 依次读取所得任务目标序列中攻击第i 个至第j 个点的资源需求量，更新无人机已消耗的任务资源expend-Q，已攻击的任务目标数indextas；

Step 2.3 判断任务目标序列中第i 个目标点至第j 个目标点所需的资源量，即无人机已经消耗的资源量expend-Q 是否超出最大资源约束Q，若否，进入Step 2.4，若是，则进入Step 3；

Step 2.4 令j=j+1，继续任务目标序列选择下一个目标点，判断j 是否超过i 的总个数，若是进入步骤Step 4；若否，返回Step 2.2；

Step 3 将目标点j 的资源需求量进行拆分，更新expend-Q=k，输出任务目标序列第i 个对应目标点的序号到第j 个对应目标点的序号，更新expend-Q（j+1）=expend-Q（i）+ expend-Q（j）-k，赋值i=j+1，j=j+2，返回Step 2.2；

Step 4 判断输出序列个数是否大于可用无人机总数，若是，返回Step 1 重新生成任务目标初始序列，若否，根据路径优化各无人机攻击任务序列，最后输出多无人机任务分配初始解。

2.2 初始解评价

计算初始解的任务总成本f1及总收益f2，G 为一个较大的数，若不满足无人机资源约束或航程约束，f1=f1+G；若不满足目标有效时间窗约束，f2=f2-G。

2.3 生成候选集

候选集生成取决于邻域操作方法，常通过reverse、insert、swap 变换产生。对目标序列Ii 随机采用上述操作方法生成邻域结构，再将其转化成无人机任务分配序列，生成候选集。

2.4 候选解评价

计算候选解的各目标函数值，并对不满足约束的解进行相应的惩罚。

2.5 禁忌规则

选择固定值15 作为禁忌长度，构造n×3 的矩阵作为禁忌表，将邻域操作的禁忌对象存放在禁忌表中，其中，n 表示禁忌长度，第1 列代表对应的变异类型，第2、3 列表示相应邻域操作变化的任务目标点。

2.6 更新局部非劣解、全局非劣解、禁忌表

比较各候选解的f1、f2，筛选候选非劣解集；比较候选非劣解和全局非劣解，得到新的候选非劣解集。判断候选非劣解是否满足藐视准则，更新当前解和禁忌表。

2.7 终止准则

达到事先指定最大循环迭代次数或者在事先给定的某一步数之内当前最好解未改进，则停止搜索，输出全局非劣解集，结束算法。

多目标无人机任务分配禁忌搜索算法具体流程如图2 所示。

图2 禁忌搜索算法流程图Fig.2 Flowchart of tabu search algorithm

3 仿真验证

3.1 任务场景

设计采用攻击无人机执行任务，已知任务区域内有25 个任务目标，每个任务目标点详细数据如下页表1 所示，无人机发射/回收站坐标为（35，35），无人机发射/回收中心拥有的无人机总数为10，无人机最大任务能力（即携带攻击资源数量）为8，最大航程约束为100，单位距离能耗成本为10，单位时间等待成本为5，任务目标初始价值均为1。

表1 任务目标点信息Table 1 Task target point information

3.2 结果分析

基于以上任务场景，利用禁忌搜索算法对是否考虑任务拆分的任务分配方案进行求解，算法参数设置如下：最大迭代次数Max_Iter=500，邻域解数量为300，禁忌长度为15。Pareto 解集分布如图3 所示。

图3 多无人机任务分配Pareto 解集分布对比图Fig.3 Distribution comparison diagram of Pareto solution set for multi-UAV task assignment

仿真结果表明，任务不拆分情况下，双目标Pareto 解集中任务总成本最低为6 294.74，总收益最大为0.860 6；当考虑任务拆分时，双目标Pareto 解集中任务总成本最低为6 266.68，总收益最大为0.895 4。因此，基于目标任务拆分的分配方案，无人机执行任务成本及效益更优。此外，随着无人机执行任务的成本增加，任务收益逐渐增加，收益水平的提高往往以增加任务成本为代价。

为分析目标任务拆分时，任务成本和收益间的影响，对总成本最低和收益最大的单目标最优实验结果进行下一步分析。相应的多无人机任务分配结果如表2 所示。

表2 多无人机任务分配结果Table 2 Task assignment results of multi-UAV

从各指标最优的方案可以看出：

1）成本最低分配方案与任务收益最大分配方案相比，任务需求拆分较少，仅拆分了目标点14、15、2，收益最大方案任务需求拆分较多，拆分了目标点16、1、15、9、2。

2）相比总成本最优分配方案，收益最优分配方案无人机航程成本有所增加，说明多个目标点任务拆分导致航程增加；时间窗等待成本增加则是为了满足目标任务时间窗约束，以提高无人机任务收益。

4 结论

在多无人机任务分配优化过程中，基于任务拆分，采用多无人机对同一目标进行攻击，有效提高任务收益。本文考虑任务目标资源需求及任务有效时间窗，以无人机执行任务总成本最小、攻击目标收益最大为优化目标，建立多目标优化模型；针对模型特点，采用三阶段禁忌搜索算法进行求解，寻求最优任务分配方案。得出以下结论：

1）在多无人机任务分配优化网络中，目标任务需求拆分可有效提高无人机执行任务效率，无人机任务成本及任务收益均可得到优化。

2）作战过程中，决策者往往需要同时考虑多个作战目标，但这些目标往往具有冲突性，无法同时达到最优。因此，需要决策者依据自身战略以及战场环境变化，合理分配无人机作战资源。

3）决策者在制定决策时应考虑实际情况，对于难度大、攻击资源需求量高的目标点可优先考虑目标任务拆分；对于任务资源需求小的任务目标，则仅考虑单无人机攻击，避免过度拆分，增加无人机航程成本。

在作战过程中，无人机任务分配网络规划更为复杂，未来将研究无人机动态任务分配优化问题；在实际应用时，战场信息数据更加庞大，算法性能有待进一步优化。