基于资源约束的多无人机联盟的任务分配

王 辉， 刘 爽

（华东理工大学机械与动力工程学院，上海 200237）

近些年，多无人机（Multi Unmanned Aerial Vehicles, 简称Multi-UAV）任务分配问题受到人们的广泛关注，旨在将无人机分组，组成联盟，从而更高效快捷地完成任务。资源分配是为了完成目标任务，确定无人机拥有的资源数量。随着控制技术、通讯技术、传感器技术和智能调度技术的快速发展[1-3]，任务分配问题已广泛应用于生产规划、货物运输和工作安排等，而多无人机任务分配更是广泛应用于军事、农业、服务业等领域。由于单个无人机资源有限，很难完成现实中复杂多变的任务，因此为了更有效地解决军事上的复杂问题，应采用多无人机联盟。

国内外的学者对任务分配问题已进行了大量的研究。Chopra 等[4]提出了匈牙利方法的分布式来解决任务分配问题。在多无人机应用的情况下，所有无人机协同计算共同分配，在对等网络进行有限局部计算。Lee[5]提出了一种基于市场机制的拍卖算法，在执行任务期间，无人机会不断消耗其资源，这些资源必须在运行期间重新填充。在该算法中，考虑了无人机的资源，从而也产生相应的成本。Jiao 等[6]提出了基于拍卖的市场模型，有效地最大化区块链网络的社会福利，并为云/雾计算服务供应商提供有效的策略。Kurd 等[7]提出了一种新的自主生物启发方法，在执行任务期间，利用该方法对多个无人机进行高效分配。每个无人机根据与各个无人机运行状态和任务参数有关的标准动态调整任务分配，而不参与任务的无人机之间可以进行直接通信。Fang 等[8]提出了一种基于情绪传染（PTA-EC）的任务分配算法，建立了人格和情感模型，将人格映射到行为并设计了情感互动。文献[9]提出了一种自组织的多机器人任务分配算法，研究了集中通信策略下的性能。这些结果表明本地策略可以在集中任务策略方面提高系统性能，降低总体通信吞吐量，并降低通信成本，从而扩展了对通信效果的理解。所采用的框架是从对蚂蚁、人类和机器人社会系统的观察中得出的自组织分工的通用模型。Gulpinar 等[10]提出了一种构造启发式算法，该算法基于估计的边际效用，将代理和资源按顺序分配给任务。基于这种启发式算法，还提出了各种近似动态规划方法和一种进化算法。Jin 等[11]提出了一种分布式协调模型，针对竞争性有限的通信，以竞争性方式为多个非完整机器人开发了一种新的协调控制。在这种建议的控制方法中，只有比赛的获胜者才会得到任务并被激活以朝着目标前进。

在现有的研究中，假定无人机具有自动执行任务的能力，并且任务分配框架只专注于最大限度地减少总成本。但在任务分配中，尚未广泛考虑任务的难度、成功率以及任务的个数。现实情况是无人机没有足够的资源和能力来执行每一项任务，任务也是多变的。在完成特定任务中，如果无人机数量不足，联盟可能无法成功完成任务；或者该联盟能够完成任务，倘若再加入几架无人机，任务的成功率和效率可能更高。

本文提出了一种基于资源的建模方法和多无人机任务分配算法，旨在为每个任务分配最佳的联盟组合，同时考虑了任务执行的成功率和效能。

1 问题描述

1.1 资源模型

将Rn表示为任务所需的资源，其中n是资源索引，n=1,2,··· ；R是资源类型。

6 种资源模型及相关参数详见表1。

表1 无人机的资源Table 1 Resources of UAV

1.2 基于资源约束的无人机模型和任务约束

此外，定义资源约束任务Ti为施加的无人机联盟C的约束，联盟级别约束通过任务Ti反映了高级资源需求，即促进联盟中的多个无人机拥有分组完成任务Ti的能力。强调多个无人机的协作技能，例如一个无人机视觉系统引导其他多个无人机执行攻击任务。定义Niu为执行任务Ti时联盟必须拥有的资源数量，如下所示：

此外，每个联盟可能要执行多个任务，任务的难度有所不同，因此将任务的难度定义为DT。DT与任务所需资源、时间有关，需要的资源越多，花费的时间越多，表示该任务难度越大，因此可以将DT定义为:

并且DT的函数表示为[10]：

2 问题求解

2.1 算法描述

Leader-follower 联盟算法主要是通过启发的方式来形成多无人机联盟，而任务分配算法（Task Allocation Algorithm，简称TA 算法）是通过计算的方式来实现多无人机的分组，计算每个分组方式执行任务的效能值(Utility)、奖励值(Reward)、代价函数值(Cost) 和成功率STCtr，将任务分配给成功率和效能值最大的组合，从而可以更高效地完成任务。算法核心如下：

2.2 成功率

每架无人机具有相同的能力和技能，并且是同类型的无人机，在给定的时间t内，根据资源来定义决策变量，将资源Rn分配给无人机Ui来执行任务T，用RTru表示该资源的数量。X是一个二维变量，表示无人机联盟C在时间t使用资源Rn完成任务T产生的影响，当任务Ti在时间t分配给无人机联盟C时，XTCtr为1，否则为0。

因此，可以在t时刻将任务T分配给联盟C，来定义任务执行的成功率[12]STCtr，

2.3 代价函数

代价函数是衡量多无人机联盟在执行任务的过程中所产生不理想结果的函数。首先，在执行任务的过程中，飞机会不断消耗机油和弹药，这会产生很大的成本；其次，飞机在飞行的过程可能会发生其他系统损坏，导致飞机坠毁；然后，任务初期，可能还有一些飞机不执行任务，在空中悬停，这也会产生一定的成本，这些都会影响无人机联盟执行任务的成功率。因此，飞机的成本函数可以描述为[10]

式中：r表示无人机的总数；ns（T）表示在任务区域，执行T任务的无人机数量；ncrash（T）表示执行任务T时，发生坠毁的无人机数量；nb（T）和nf（T）表示执行任务T时，分别消耗的弹药和机油数量；Cloc、Ccrash、Cb和Cf分别表示无人机不执行任务、发生坠毁、消耗弹药和机油所产生的成本。

此外，在许多无人机任务分配的应用中，为了确定无人机联盟是否执行任务以及任务执行情况，增加了通信中继的应用程序，确保无人机之间、基地和无人机之间可以相互交流通信[12-15]。人工操作人员或基于地面的操作系统可以使用此程序向无人机发送命令，或收集和分析来自无人机的实时传感器数据。例如，在配备摄像头的无人机进行搜索和攻击的任务中，操作人员可能需要观察来自每个无人机的实时视频来确定敌方的可能位置。此外，在许多情况下每个无人机的通信范围可能会受到限制，特别是可能小于基地和监视区域之间的距离。因此，在这种情况下，有必要形成通信“链”，由空间分隔的一串无人飞行器组成，用于中继消息在基地和任务执行区之间来回传递。

为了建立通信链的需求，代价函数C（T，U）按以下方式修改为[10]

其中：逻辑函数m(T)取值0 或1，当无人机之间存在通信联系时，m(T)取1；否则取0。

2.4 奖励函数

尽管执行任务会产生一定的成本，但是任务执行成功也会获取相应的奖励，每成功地执行完一个任务，无人机都会获取相应的奖励[10]

其中：ait表示任务分配参数，若已分配任务，则取1，否则取0；Rit表示单个无人机所获取的奖励，Rit=1-e-au；a表示弹药的性质；u表示弹药的数量。

2.5 效能函数

在执行任务的过程中，每当这个联盟执行完一个任务就更新这个效能函数值，效能函数由奖励函数（Reward）和代价函数（Cost）两部分组成，奖励函数值减去代价函数值即为效能值，效能函数U[10-12]如下：

3 结果及分析

3.1 实验结果

为了验证该算法的有效性，在Matlab 环境下进行仿真实验，该实验将3 组任务，共15 个任务分配给40 架无人机，每架无人机拥有的资源是相同的，因此，经过计算，3 组任务的实验数据分别见表2、表3和表4。

表2 第1 组任务分配实验数据Table 2 The first set of experimental data on task allocation

表3 第2 组任务分配实验数据Table 3 The second set of experimental data on task allocation

表4 第3 组任务分配实验数据Table 4 The third set of experimental data on task allocation

此外，在Matlab 环境下做了仿真动画来进一步验证该算法的有效性。动画中，五角星表示无人机，虚线代表飞行的路线，圆形表示无人机飞行的范围，三角形表示任务点位置，三角形面积大小表示任务难度，颜色变化反映了任务的执行进展，分别是深红、橙色、黄色、绿色和蓝色，其中深红表示任务还未执行，蓝色表示任务执行完毕。另外，在动画的中央设定了一个飞机场，无人机从飞机场出发，如图1（a）所示。首先，第1 组任务共有6 个任务，由于任务相对简单，故只由25 架飞机来执行这些任务，其他飞机在飞机场内待命。这6 个任务中如果有任务提前完成，该任务点就消失，同时飞机在原地盘旋，等待被分配第2 批任务，如图1（b）所示。第2 组任务共有5 个任务，且难度较高，40 架飞机全部执行任务，如图2（a）所示，同样的，当某项任务先执行完毕后，任务点就会消失，如图2（b）所示。当执行完第2 批任务后，有15 架飞机发现油量和弹药不足，不能继续执行接下来的任务，故这15 架无人机先返回飞基地，由剩余25 架无人机执行第3 组任务，如图3 所示。

图1 第1 组多无人机任务分配Fig. 1 The first group of multi-UAV task allocation

图2 第2 组多无人机任务分配Fig. 2 The second group of multi-UAV task allocation

图3 第3 组多无人机任务分配Fig. 3 The third group of multi-UAV task allocation

3.2 实验对比

在利用Matlab 得到理想的效果和数据后，也不能确定所采用的TA 算法具有优越性，于是，将该算法与遗传算法[16-17]、匈牙利算法[4]和拍卖算法[6]进行了对比，结果见表5、表6 和表7，对比分析了在这些算法的框架下，飞机执行任务的成功率、奖赏值、代价值和效能值。由于仿真实验的任务众多，故只对比分析每一轮任务的第1 个任务，结果表明，通过上述数据对比分析可以得出TA 算法具有一定的优越性，在该算法框架下，任务执行的成功率最高且效能值最大。

表5 不同算法下第1 组第1 个任务实验数据对比Table 5 Comparison of experimental data of the first round of the first task under different algorithms

表6 不同算法下第2 组第1 个任务实验数据对比Table 6 Comparison of experimental data of the second round of the first task under different algorithms

表7 不同算法下第3 组第1 个任务实验数据对比Table 7 Comparison of experimental data of the third round of the first task under different algorithms

4 结束语

研究了基于资源的多无人机任务分配，提出了一种任务分配算法，重点介绍了在该算法的有效性，同时考虑了任务的成功率、奖励值、代价值和效能值，将任务分配给最佳的无人机组合，从而提升了任务分配的准确性以及任务的成功率。为了验证该算法的有效性，在Matlab 中进行了仿真实验,做了仿真动画，并且对比了该算法与遗传算法、匈牙利算法和拍卖算法的成功率、奖赏值、代价值和效能值，证明该算法可以大大提升任务的成功率和效能值。