时间约束下的多无人机任务分配方法研究

2022-06-04赵佳宜赵文栋刘存涛李艾静刘泽原

兵器装备工程学报 2022年5期

赵佳宜,赵文栋,刘存涛，李艾静，刘泽原

(陆军工程大学通信工程学院，南京 210000)

1 引言

无人机因其成本可控、机动性强、控制灵活、环境适应性好及人员伤亡风险低等优点，在民用和军事领域均得到了广泛的应用，尤其是执行高危环境下的污染监测、紧急搜救、灾后通信恢复及数据采集等任务时，与传统手段相比表现出更显著的优势。

在时延容忍网络(delay tolerant networks,DTN)中，节点之间的数据传递具有一定的时间容忍度，在截止时间内实现数据的最终交付对于用户来说即是可接受的。当电磁环境复杂、基础通信设施受损或通信条件较差时，基于多跳的数据转发会出现高误码率及高丢包率等问题，影响数据转发的可靠性和有效性。此时，采用无人机充当渡轮(ferry)实现节点间的数据摆渡能够确保数据的可靠交付。与传统的数据传输不同，数据摆渡可以采取装载-携带-交付(load-carry-and-deliver,LCAD)的方式，即无人机从源地面节点装载数据，在飞向目的地时携带数据，最后将数据交付给目的节点，这一方式在源和目的节点没有直接通信链路的情况下得到了广泛的应用。此外，当多架无人机同时执行多个具有不同截止时间约束(时延容忍区间)的数据摆渡任务时，受限于单无人机自身的任务执行能力，采用“一一对应”的任务分配方式很可能导致部分任务无法得到有效完成，即无法在任务截止时间内将源节点的数据传递至目的节点，从而直接影响任务的完成质量。在这种情况下，采用“交叉执行”的协同任务分配方式通常具有更好地适用性。

目前，已有许多文献围绕多无人机协同任务分配问题展开了研究。文献[5-8]研究了无人机任务分配中的成本最小化问题。文献[9-10]研究了无人机任务分配中的公平性问题。文献[11-13]研究了无人机任务分配中的效用最大化问题。然而，上述研究很少考虑不同任务的差异化时间约束,仅从无人机能耗或系统收益的角度出发对任务进行分配仍可能导致部分任务完成效果不佳。

在考虑时间约束的情况下，可以将多任务分配问题建模为带有时间窗约束的组合优化问题，该问题已被证明是NP-hard问题，通常可以通过状态压缩动态规划(状压DP)、(混合)整数规划、启发式算法、博弈论以及强化学习等方法进行求解。

本文考虑了DTN中基于多无人机摆渡的数据转发场景，研究了差异化时间约束下的多任务分配问题，采用任务拆解与重组的思想，将其建模为具有右时间窗的车辆路径问题，并以无人机总能耗最小化为目标对其进行优化。通过引入大规模邻域搜索(large-scale neighborhood search，LNS)中的“破坏和修复”思想，有效提高了遗传算法的全局寻优能力，能够在满足多任务时间约束的前提下，降低多无人机系统的总能耗。

2 系统模型及问题形式化

2.1 系统模型

如图1所示，本文考虑了DTN中基于多无人机的数据摆渡场景，包括一个信息中心，个目标点和架可用摆渡无人机。信息中心接收到多个用户的数据获取需求后，为无人机分配数据摆渡任务；无人机根据分配到的数据摆渡任务，飞往任务目标点处，采用悬停的方式采集任务目标点的信息，而后将其携带回信息中心；信息中心接收到无人机获取的信息后，根据用户的需求向用户分发信息。假设用户与信息中心之间通信条件良好，且不考虑两者之间的通信时延问题，信息中心获取到无人机所采集信息的时间即为用户获取到所需信息的时间。

初始数据摆渡任务是根据用户的不同信息获取需求来区分的，记={,,…,}表示个任务的集合，其中，=<,>表示第个任务，是完成任务需要访问的目标点集合，是任务的截止时间。

如图1(a)所示，采用“一一对应”的任务分配方式时，由于不同用户的信息获取需求不同，可能导致不同无人机访问目标点的数量存在较大差异(如UAV2和UAV3)，这一方面影响了无人机之间的能耗公平性，另一方面也造成无人机资源的浪费；同时，由于单个无人机飞行能力有限，当其需要访问的目标点数量过多时，任务完成时间通常会比较长，会导致对应的数据摆渡任务无法有效完成。

图1 系统模型示意图

为此，主要考虑如图1(b)所示的“交叉执行”任务分配方式，即一架无人机可以执行多个数据摆渡任务，每个数据摆渡任务可以由多架无人机执行。具体过程如下：首先将初始数据摆渡任务进行分解，把每个目标点看作一个任务碎片，并根据其所属的初始摆渡任务，使用作为时间戳对其进行标记；而后对任务碎片进行重组，并将重组后的数据摆渡任务分配给不同的无人机。碎片重组的有效性会直接影响任务的完成质量，为此，需要对碎片重组策略进行优化。这种基于碎片重组的任务分配问题可以归属于组合优化问题，下面对具体的约束和优化目标进行详细描述。

2.2 能耗约束

在考虑能耗约束的情况下，无人机任务分配与路径规划之间具有高度耦合性，因为无人机的能耗很大程度上取决于其在任务执行过程中的飞行路径。为此，通常会将任务分配与路径规划一同进行考虑：在确定了任务分配策略之后，无人机的飞行路径可以建模为完全无向图(,)，其中，是节点集合，表示无人机需要访问的所有目标点的集合；是节点之间边的集合，当2个节点之间有边时表示这两个节点由同一架无人机进行访问，即属于同一架无人机的任务目标点集合。此外，无人机在整个数据摆渡任务中的能耗包含采集目标点信息时的悬停能耗和飞行消耗两部分，将无人机的悬停能耗和飞行能耗分别表示为节点和边的权重：对于节点∈，点权重记为()，对于边(,+1)∈，边权重记为(,+1)。下面对无人机的飞行能耗和悬停能耗进行详细描述。

2.2.1 飞行能耗

无人机的飞行能耗主要取决于的飞行路径长度。本文只考虑二维平面的无人机，记无人机的飞行速度为，则可以表述为

=·

(1)

(2)

2.2.2 悬停能耗

(3)

其中，表示单位时间内的悬停能耗。

基于上述分析，如式(4)所示，的总能耗可以表示为

(4)

(5)

2.3 时间约束

主要与的飞行时间和悬停时间有关，可表示为

(6)

综上所述，时间约束可以表示为

(7)

2.4 目标函数

以无人机总能耗最小化为目标对多无人机协同任务分配问题进行优化，优化目标表示为

(8)

其中:表示任务分配策略集，表示策略集中的一个可行解。由于目标函数的非凸性，问题是一个非凸优化问题，很难通过直接求解得到问题的最优解。为此，我们提出了一种基于大规模邻域搜索算法改进的遗传算法对该问题进行求解。

3 算法描述

3.1 遗传算法概述

遗传算法是借鉴生物进化过程而提出的一种启发式搜索算法，通过选择、交叉和变异等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解，从而通过进化演变，逐步逼近问题的最优解。该算法具有简单通用，鲁棒性强，适于并行处理等优势。但是，遗传算法的局部搜索能力较差，且对初始种群的选择具有一定依赖性。

3.2 基于改进遗传算法的协同任务分配算法

本算法以遗传算法为基础，在进化算子中引入了大规模邻域搜索中的“破坏和修复”思想，有效弥补了遗传算法容易陷入局部最优解的缺陷，提高了解的质量，算法的具体描述如下。

3.2.1 染色体结构

如图2所示，采用整数编码的形式将一个染色体描述为(1,2,3,…,,+1,+2,…,+-1)，其中，数字1～表示对应序号的目标点，数字(+1)～(+-1)表示1～号无人机。如果无人机序号第一次出现在数字1-之间时，则表明第一条路径生成，以此类推。

图2 染色体结构示意图

3.2.2 适应度函数

考虑可能出现违反任务时间窗约束的情况，设计了如式(9)所示的惩罚函数()，表示为

()=·()

(9)

其中，表示单位惩罚成本，本实验中设置为10；()表示在采用任务分配策略时，违反任务时间窗约束的目标点信息的累积超时时间，表示为

(10)

其中，()表示目标点的时间戳，若标点的信息到达信息中心的时间尚未超过其时间戳，则()为0；否则，将()记为该信息的超时时间。

记()为所有无人机的总能耗，则适应度函数表示为

()=1(()+())

(11)

3.2.3 种群初始化

采用启发式方法构造初始种群，其中，单个初始解的构造方法如算法1所示。

1基于贪婪思想的初始解生成算法

无人机数目，个目标点的坐标，截止时间集合{}

初始可行解

1.路径序号：_←1；

2.从个目标点中随机选择一个点；

3.以为初始点，生成一个目标点遍历序列：←[,+1,…,,1,…,-1]；

4.按依次遍历目标点，如果将添加到当前路径中，不会导致路径中的节点(含)出现违背能耗约束的情况，则添加到路径中，并将从剔除；否则更新路_=_+1；

5.重复步骤4，直至为空，根据生成路径的数量_。

6.如果_小于，则选择1～_号无人机作为任务无人机，将+1,+2,…,+_依次插入到各个路径的起始点，并将各路径合并得到初始解；否则，当前解为不可行解，从步骤1开始重新构造初始解。

3.2.4 进化算子

选择算子：采用轮盘赌算法作为选择算子，基于个体的适应度选择若干个个体参与后续的交叉、变异以及局部搜索操作。

交叉算子：采用顺序交叉的方式实现，如图3所示，系统随机生成2个交叉位置，用以选择父代交叉的片段，如图3中标黄部分为例。随后将父代2的交叉片段移动到父代1的前面，将父代1的交叉片段移动到父代2的前面。接着从前到后把第2个重复的基因位删除，形成2个子代个体。

变异算子：采用了2种变异算子，一是基于two-element swap算子实现染色体变异，即随机生成2个位置，将父代染色体相应位置上的基因进行交换，形成子代染色体。二是引入LNS中的局部搜索算法，通过破坏算子和修复算子实现染色体变异，具体步骤如算法2所示。

图3 交叉算子示意图

2LNS算法

当前的解

进化后的解

1.初始化需要移出的目标点数量为=5；

2.从原有目标点集合中随机选出一个目标点；

3.根据相关性计算公式(,)=1(+)，由高到低依次移出中的个目标点，放入集合；

4.分别找出中的目标点在中的可行插入点集合，并记录此时的最小的能耗增量；

5.按照从大到小的顺序，将中的目标点在不违反约束的情况下依次插入当前解中，并计算此时的最小能耗；

6.重复该操作直至中的个目标点都被重新插回解集合。

基于上述分析，得到基于改进遗传算法的协同任务分配算法，具体步骤入算法3所示。

3基于改进遗传算法的协同任务分配算法

无人机数目，个目标点的坐标，截止时间集合{}

最优解

1.初始化种群，种群规模=100，最大迭代次数max=100；

2.根据算法1构造初始解，输出随机初始解的路线，即产生路径点集合，并计算初始解中的UAV使用数目，UAV飞行总能耗以及违反约束目标点数目；

3.计算(,+1),和()，和矩阵；

5.当≤max时，执行步骤6，否则，执行步骤10；

6.计算适应度函数=()；

7.进行选择，交叉和变异操作；

8.利用破坏和修复算子，根据算法2对染色体进行局部搜索操作；

9=+1；

10.输出当前最优解。

4 仿真结果及分析

为了评价算法的性能，除了本文提出的协同任务分配算法(cooperation task redistribution algorithm,CTRA)之外，同时对“一一对应”任务分配方式下的性能和传统的遗传算法性能进行了仿真。仿真结果均为在Matlab 2019a环境下进行了10次实验后，求取的平均值。

4.1 仿真参数设置

仿真过程中，目标点分布于大小为3 000 m*3 000 m的二维平面，信息中心位置固定，且为(0，0)，可用无人机数量为25，目标点的默认数量为100。图4显示了目标点的分布情况和任务需求。此外，任务截止时间如表4所示，其他主要仿真参数如表5所示。

图4 目标点分布及任务需求示意图

表4 任务截止时间

表5 参数设置

4.2 仿真结果

4.2.1 算法收敛性

图5显示了CTRA的收敛性。从仿真结果可以看出，该算法经过约86次迭代后，已经基本收敛。

图5 算法CTRA的收敛性曲线

4.2.2 算法性能比较分析

1) 能耗效率。如图6所示，采用“一一对应”的任务分配方式时，由于任务8和任务9的信息需求量差异较大，导致无人机8和无人机9消耗的能量差异也较大。而经过“交叉执行”的任务碎片化重组之后，如图7所示，需要的无人机总数量减少为7架，且无人机的能耗效率和公平性均得到明显改善。

图6 “一一对应”任务分配方式的分能耗直方图

图7 “交叉执行”任务分配方式的分能耗直方图

2) 任务完成时间。图8显示了“一一对应”任务分配方式下的任务完成时间，对于信息需求较大的任务8而言，任务完成时间超过了其截止时间，导致对应的数据摆渡任务8无法有效完成，任务2，4，7亦是如此。而在“交叉执行”任务分配方式下，如图9所示，所有任务均可在任务截止时间前完成，有效改善了任务完成质量。

图8 “一一对应”任务分配方式的分时间直方图

图9 “交叉执行”任务分配方式的分时间直方图

4.2.3 算法适应性

1) 截止时间分布对算法性能的影响。默认的截止时间分布是随机分布，因此图10研究了截止时间服从泊松分布时变化对目标函数的影响。当值较小时，由于违法约束的目标点数目较多，惩罚函数值较大，因此得到的最优解随之增大。随着的不断增大，截止时间均得到满足，最优解趋于稳定。

图10 最优值随截止时间分布变化直方图

2) 目标区域大小对算法性能的影响。图11和图12的仿真结果比较了目标区域大小对算法性能的影响。仿真中将侦察区域设置为正方形，图中的横坐标代表侦察区域的边长。随着侦察区域的增大，无人机的飞行距离变大，从而增加了无人机的飞行能耗和飞行时间，因此，需要的无人机数量随侦察区域范围的扩大产生了变化。另外，如图12所示，与“一一对应”任务分配方式相比，“交叉执行”任务分配方式在满足所有任务截止时间的情况下，系统总能耗可以降低约17.7%～41.9%。

图11 无人机数量随目标区域大小变化直方图(CTRA)

图12 总能耗随目标区域大小变化曲线

3) 目标点数量对算法性能的影响。图13和图14对比了CTRA和遗传算法GA的性能。其中，图13展示了无人机数量随着目标点数量的变化情况，从仿真结果可以看出，随着目标点数量的增加，为满足任务的截止时间，使用的无人机数目均随之增加，但是基于CTRA的任务分配算法能够在一定程度上获得更优的解，即可以采用更少数量的无人机来满足任务需求。此外，如图14所示，和遗传算法GA相比，CTRA平均降低了约12%的系统能耗。