基于离散鸽群算法的无人机任务分配

2021-01-15勾青超李庆奎

北京信息科技大学学报(自然科学版) 2020年6期

勾青超，李庆奎

(北京信息科技大学自动化学院，北京 100192)

0 引言

多无人机协同[1]在军事领域和民用领域都具有广泛的应用前景。任务规划是多无人机协同任务的关键技术，是实现多无人机协同完成任务的指挥系统，主要包括任务分配和航迹规划。任务分配是在考虑多种约束下，对同类型的无人机或者是异构无人机进行任务指派，是实现协同任务的核心。

多无人机任务分配已经成为目前的研究热点，国内外学者开展了相关的研究工作。文献[2]用遗传算法求解异构无人机的多机协同任务分配问题；文献[3]介绍了合同网方法的提出及发展；文献[4]对一致性包算法(CBBA)进行了扩展，提出了基于改进冲突消解原则的一致性联盟算法(CBCA)，以实现异构多智能体协同无冲突任务分配。智能算法对于求解任务分配具有先天的优势，主要包括基于蚁群算法的任务分配[5]、基于粒子群算法的任务分配[6-10]、基于遗传算法的任务分配[11]等。

目前，任务分配的算法模型多是基于多目标单任务进行的。而实际上在真实环境中无人机需要通过协同同时执行多个任务。为研究多目标多任务的任务分配问题，本文将鸽群算法进行改进，并将其离散化，应用改进后的算法对多无人机的协同任务分配问题进行了求解。鸽群算法[12]具有全局优化的特点，对于多约束多目标问题具有较大的求解优势。

1 任务分配模型

1.1 问题描述

假定多无人机在执行广域搜索攻击任务中，任务区域已被其他无人机或者侦察平台搜索到Nt个疑似目标，需要任务区域内的多无人机对疑似目标依次进行侦察、攻击。令发现的目标集合为T={T1,T2,…,TNt}，任务区域的无人机有Nv个，其集合为V={V1,V2,…,VNv}。对每个目标需要执行的任务集合为M={M1,M2,…,MNm}。无人机的任务集合为K={K1,K2,…,KNc}，Nc为无人机需要执行的任务总数量，Nc=Nv×Nm。作战示意图如图1所示。

在示例中，三架无人机UAV1、UAV2、UAV3执行对target1-target6的攻击任务，目的是在满足约束条件的前提下，找到最优的任务分配方法。示例中的求解结果为UAV1攻击target1与target2、UAV2攻击target3与target4、UAV3攻击target5与target6的路径代价最小，即为最优的方案。

1.2 约束条件

在任务分配问题中存在以下约束：

1)任务时序约束。多无人机对同一目标进行侦察和攻击任务时具有时序约束。对该目标的攻击任务必须在对该目标的侦察任务完成之后，即：

TM1

(1)

2)多机协同约束。任务集合中的任何一个任务只能被完成一次，即所有无人机对同一个目标只能依次进行一次侦察和攻击任务，即：

(2)

3)弹药数量约束。设对多无人机进行任务分配时，无人机1当前剩余未使用弹药数量为M，则无人机 1执行攻击任务的次数必须小于或者等于M。即：

(3)

4)任务时间约束。定义同一个目标的不同任务执行时存在时间间隔，即前一个任务完成后需经过一个最小时间间隔之后才允许执行下一个任务，而且时间间隔不允许超出最大时间间隔，即

tM(nt)+Δtmin≤tM(nt+1)≤tM(nt)+Δtmax

(4)

1.3 目标函数

该类问题通常选取航程或者航行时间作为方案决策的重要标准。本文选取所有目标被完成后无人机航行总距离以及时间作为衡量指标，认为总航程最短的任务分配方案最优。假设Di为第i架无人机与目标的区间信息，j为被执行任务的目标，即第i架无人机对所有目标的航程代价为

(5)

最优方案为

(6)

2 数学模型

2.1 基本鸽群算法

鸽群算法是根据鸽子所特有的导航能力而提出的。将鸽子归巢行为看作依靠磁场与地标的两阶段寻径。在离巢较远距离依赖地磁场确定归巢大致方向，在靠近鸽巢时，根据附近熟悉的地标建筑锁定鸽巢位置。基本鸽群算法如下。

2.1.1 第一阶段：依靠磁场寻径

鸽群在多维搜索空间中，鸽子的位置和速度在每一次迭代中都会得到更新，更新过程如下：

V(t)=V(t-1)×e-Rt+d×(Xgbest-X(t-1))

(7)

X(t)=X(t-1)+V(t)

(8)

式中：R为磁场因子，R∈{0,1}；d为取值范围在(0,1)的随机数；Nc为目前迭代次数；经过Nc-1次迭代循环后，通过比较所有鸽子的位置得到全局最优位置Xgbest。当该循环次数达到所要求的迭代次数后，即停止磁场因子阶段的迭代，进入地标算子中继续工作。

2.1.2 第二阶段：依靠地标寻径

更新地标函数为

(9)

X(t)=X(t-1)+d×(X(t)-X(t-1))

(10)

式中f(X(t))为当前鸽子的适度值函数，即设定的目标函数。

舍弃函数为

(11)

在依靠地标寻径的过程中，每一次迭代后鸽子的数量都会减少一半。那些远离目的地的鸽子对地标不熟悉,它们将不再有分辨路径的能力,因而被舍去。Xc是剩余鸽子的中心位置，将被当作地标，即作为飞行的参考方向。

基本鸽群算法流程如图2所示。

2.2 鸽群算法的离散化与改进

2.2.1 鸽群算法离散化

鸽群算法是针对连续函数提出的智能算法。本文在对任务分配问题进行求解时，首先对鸽群算法进行离散化处理。具体方式是将鸽群的速度和位置坐标离散化，通常用0或1来表示(离散二进制)，或者自定义整数数组来表示。

针对多无人机多目标任务的分配问题，本文将目标的序列与无人机的序列进行编码。考虑到多机协同约束，即每个目标任务均只需要一架无人机完成，所以可拟定确定的目标序列，通过随机排列无人机编码序列，来形成不同的任务分配方案，分配结果实例如图3所示。

图3描述的是5个无人机针对8个目标执行两种任务的一种随机编码序列，图中数字即代表第几个无人机去执行对应行目标的对应列类型任务。

2.2.2 鸽群算法的改进

任务分配问题难以拟合成一个连续函数，而基本鸽群算法针对离散问题难以处理，本文对鸽群算法进行改进，改进后的模型如下。

1)第一阶段,迭代次数l≤N1时：

X=e-R×l×X(l-1)+d×(Xgbest-X(l-1))

(12)

式中Xgbest为当前全局最优解。

2)第二阶段，迭代次数N1≤l≤(N1+N2)时：

X=e-R×l×X(l-1)+rand(Xc-X(l-1))

(13)

(14)

标准鸽群算法通过每次剩余鸽群中的中心位置向目标靠近来寻优，容易过早收敛。在进行寻优搜索时，前期希望算法拥有较强的全局搜索能力，局部搜索能力影响小，后期更希望算法能够进行精确的局部搜索，因此希望局部更新对算法的影响更大。因此本文对式中磁场因子R进行了重新设计，使其在迭代过程中呈现非线性衰减的趋势，避免过早收敛：

(15)

式中：

(16)

2.2.3 约束处理

为了更好地处理约束，同时为了规避在生成任务分配方案时出现生成不可能方案(如负数或者超出无人机数量的数值)的情况，本文对任务分配方案序列进行了处理，将单列无人机编码数组转化为目标与无人机对应关系的连接矩阵，行数等于目标数目，列数等于无人机数目，用0或1表示，方案的对应关系转化示例如图4所示。

对于连接矩阵L，其取值仅有{0，1}，因此，可以生成二进制的速度矩阵，利用“与或”逻辑关系，完成迭代中的迭代结果离散化。在连接矩阵中，对以下约束进行处理：

1)多机协同约束。在连接矩阵中对应每行和为1，即：

∑(A(i),2)=1

(17)

2)弹药约束。当任务类型为攻击约束时(定义任务类型变量nt，当nt=2时)：

∑(A(i),1)≤2

(18)

3)任务时序约束。通过定义任务类型变量nt，取值{1,2},分别对应目标的侦察与攻击任务。程序通过扩展矩阵维数来解决目标的多任务类型，并依次对任务类型进行迭代。

4)任务间隔约束。定义时间序列组，分别记录目标任务的完成时刻Tt与无人机完成任务时刻Tu(前者需要通过后者数值来计算)，判断同一目标的不同任务类型完成时间是否满足约束条件。

① 若任务间隔时间Δt小于最小间隔时间Δtmin，则认为无人机通过盘旋来延长飞行时间，即此段距离认为是：

D=v×Δtmin

(19)

② 若任务间隔时间Δt大于最大间隔时间Δtmax，则通过罚函数进行处罚，定义罚函数因子PT：

F=D+M×PT

(20)

式中M是较大值，当满足约束时，PT=0；当不满足约束时，PT=1。

2.2.4 适应度函数

适应度函数的选取直接影响到算法的收敛速度以及能否找到最优解。本文通过计算鸽群中各粒子的适应度函数来判断个体适应程度。即通过计算多无人机完成多目标任务的总航程，来判断个体的优秀程度，选取航程最短的作为最优方案：

1)对于单任务类型问题，不需要考虑复杂的多任务条件约束，不利用外部信息，仅以适应度函数为依据，利用鸽群中每个粒子的适应度来进行搜索，最优适应度即为任务分配结果中粒子的总航程累加结果。

2)对于多任务类型问题，需要考虑到任务间隔约束。最优适应度需要比较多种任务阶段适应度值的累加结果得出，并对不满足约束的某段航程进行处理，即延长或者惩罚。

3 离散鸽群算法流程

程序运行流程框架如图5所示。

其中constraints_solve函数对迭代后得到的速度矩阵进行处理，处理多机协同约束和弹药约束。其思路是：

第一步：对多于目标任务数量的坐标进行随机去除(初步满足多机协同约束，总无人机执行任务数等于目标需要执行任务数)。

第二步：进一步处理多机协同约束，将和不为1的行中多余的点进行转移。首先要搜索行和大于1的行，利用random_choose函数随机选取多余的点(增加了种群多样性)，然后搜索同列中可转移的位置(行和为0的位置)，在搜索结果中随机选取转移位置进行转移，转移只改变行数，不改变列数。

第三步：处理弹药约束。首先搜索列和大于2的列，随机选取多余的点，然后随机选取其他列可转移的位置进行转移，转移只改变列数，不改变行数。

calFitness函数通过累加各无人机完成任务的路程获得个体适应度值。对于弹药数量大于1的模型，存在单无人机对多个目标进行攻击的情况，在此情况下计算适应度时，需要选择该无人机攻击的先后顺序，即需要通过比较不同情况的适应度高低，选择较低的方案。

4 仿真分析

仿真环境为CPU2.50GHz四核，内存8 GB，Matlab R2018b。假设目标数量8个；执行任务的无人机数量为5架；弹药约束为2发；迭代粒子数为100；迭代次数N1=350，N2=150；最小时间间隔Δtmin=0.25 s，最大时间间隔Δtmax=1 s。

针对多目标执行攻击任务，随机生成目标及无人机位置,相同位置下，将离散鸽群算法与遍历算法及基于Sigmoid函数惯性权重自适应调整的粒子群优化算法[13-14]对比。在目标数量较少的情况下，3种算法的分配结果一致。遍历算法的运行时间为27.30 s,粒子群算法的运行时间为7.13 s，离散鸽群算法的运行时间为6.87 s。任务分配结果如图6所示。

目标数量增加到16个，执行任务的无人机数量增加到10架，其他条件无变化时，采用粒子群算法与离散鸽群算法的任务分配结果如图7所示。

在目标较多的情况下，粒子群算法求解的总路程最小距离为80.75 km，运行时间为13.74 s；离散鸽群算法求解的总路程最小距离为75.01 km，运行时间为11.58 s。可以看出，随着目标数量增多，离散鸽群算法在寻优能力及收敛速度方面有了一定程度的提高。

针对多目标多任务的情况，初始最优分配与离散鸽群算法分配结果如图8所示。

多目标多任务的最优分配方案如图9所示。

在多目标多任务的情况下，初始最优分配方案的总路程最小距离为352.58 km，运行时间为47.56 s；离散鸽群算法求解的总路程最小距离为162.97 km米，运行时间为23.34 s。从图8及图9可以看出，针对复杂度很高的多目标多任务问题模型，离散鸽群算法可以快速求出一个较优解。不同任务类型的无人机方案分配序列大致相同，这符合实际情况的判断(不考虑最小时间约束和弹药约束差异的情况下，同一个目标的两个任务必然由同一个无人机执行完成)。