多飞行器协同任务分配粒子群算法研究

赵慧武，王 鹏，郭江宇

(1 北方自动控制技术研究所，太原 030006；2 32381部队，北京 100071)

0 引言

现如今，飞行器在目标搜索、对地攻击、空中搜救、交通巡查以及快递运输等军用和民用领域发挥着重要作用[1]。单架飞行器往往无法高效率的完成复杂多变的任务。因此，需要使用多个同构或异构飞行器协同完成任务。如何使得多飞行器控制系统更好的适应复杂的任务环境和灵活多变的任务要求，是近年来国内外科研人员研究重点[2]，特别是多飞行器协同任务分配问题，已成为飞行器自主导航领域亟需解决的关键问题[3]。

多飞行器协同任务分配问题可定义为：给定飞行器种类及数量，根据一定的物理环境信息和任务要求，将一个或多个任务分配给一个飞行器，所有飞行器完成所分配的任务的同时，使得整个飞行器编队的整体效能达到最优[4]。在给飞行器分配任务的过程中，还需考虑飞行器的载弹有限性、多任务时序约束以及实时规划有效性等要求。从理论上讲，多飞行器协同任务分配问题属于NP-hard的排列组合问题，难以完全避免组合爆炸，对于规模较大的飞行器编队很难得到最佳任务分配方案[5]。目前，很多学者提出了多种计算可行的协同任务分配算法，比如基于合同网“招标-投标-中标”的市场拍卖机制，提出了多Agent分布式任务分配算法[6-7]；智能优化算法因为具有灵活、易实现和计算复杂度低的特点，被广泛的用于多飞行器协同任务分配的研究，常用的算法包括遗传算法[8]、蚁群算法[9]和粒子群算法[10-12]等。

文中主要研究了多飞行器协同攻击多个地面目标的任务分配问题，提出了任务分配粒子群算法。首先，建立飞行器任务分配时必须满足的攻击上限约束以及航程约束，构造任务分配需付出的代价函数和收益函数，进而建立多飞行器协同任务分配问题的数学模型。然后，为每个粒子定义了相应的任务分配向量，建立粒子的连续化的位置属性与任务分配解的“一一对应”的关系，即实现了粒子连续性解的离散化。最后，建立多飞行器协同任务分配的粒子群算法，并进行了数字仿真实验，验证了所提算法的有效性。

1 数学模型

以二维战场环境多架飞行器多对地面目标开展协同攻击为研究背景。假设任务背景中不存在禁飞区、地形障碍等威胁，任务环境已知，同时考虑目标对飞行器的防空威胁。

假定系统包含Nu架飞行器U={U1,U2,…,UNu}和Nt个目标T={T1,T2,…,TNt}，Nu

Θi=

(1)

为了更好的描述上述过程，利用xij表示第i架飞行器Ui执行任务Θi时是否攻击了第j个目标。

(2)

本质上，飞行器的协同任务分配是个排列组合问题。通过为飞行器合理分配攻击目标，保证飞行器编队整体作战性能最好。在飞行器任务分配中，通常需要考虑以下的约束、代价与收益。

约束条件：飞行器的载弹能力有限，单次执行任务时只能攻击有限个数目标，令飞行器Ui的能力上限是Qi,max。此约束表示为：

(3)

受机载燃油限制，飞行器只能在有限距离内连续飞行，因此飞行器Ui的飞行路程不能超过最大航程Li,max。此约束表示为：

d(Θi)≤Li,max,∀i∈{1,2,…,Nu}

(4)

每个目标只能分配给一个飞行器，不能重复分配。此约束表示为：

(5)

(6)

航程代价：飞行器需要飞行一定航程完成攻击任务。航程越长，消耗机载燃油越多。通过将航程代价指标最小化，尽可能的减少资源消耗。飞行器Ui执行Θi的航程代价函数为：

minLi=d(Θi)

(7)

攻击收益：飞行器攻击目标将会获得一定的收益，其大小由目标本身价值和飞行器对目标的杀伤概率决定。通过将收益指标最大化，能尽可能的提高作战性能。假设pij,T是飞行器Ui对目标Tj的杀伤概率，Vj,T是目标Tj的价值。飞行器Ui执行Θi任务后收益函数为：

(8)

通过上述分析，可得飞行器任务分配问题的数学模型为：

(9)

s.t. 式(3)～式(5)
xij∈{0,1},∀i∈{1,2,…,Nu},∀j∈{1,2,…,Nt}

其中，s1，s2和s3分别是威胁代价、航程代价以及攻击收益对应的权重。

2 多飞行器粒子群协同任务分配算法

粒子群算法(PSO)是20世纪90年代出现的智能进化算法。一定数目的粒子组成种群，每个粒子代表问题的一个潜在解，利用适应度函数评估粒子的优劣，追随当前粒子种群中的最优解和粒子历史最优解，持续迭代更新粒子种群以追寻到全局最优解。

算法初始化时随机选择一群粒子。每个粒子有两个连续性特征属性：位置和速度。在迭代过程中，粒子需要追踪两个极值：第一个是粒子自身历史的最优解，称为个体极值；另一个是整个种群当前的最优解，称为全局极值。所有粒子基于这两个极值更新位置和速度，从而尽快向最优解靠拢。

在多维目标搜索空间中，假设粒子Pk在t时刻的位置向量和速度向量分别是Yk(t)和Zk(t)，它们按照式(10)～式(11)演化：

Zk(t+1)=wZk(t)+c1Rand1()(pb(t)-Yk(t))+
c2Rand2()(gb(t)-Yk(t))

(10)

Yk(t+1)=Yk(t)+Zk(t)

(11)

其中：Rand1()和Rand2()是分布在[0, 1]之间的随机自然数；c1和c2通常情况下都取值为2；pb(·)是粒子Pk的个体极值；gb(·)是种群当前找到的全局极值；惯性权重w取(0.5, 0.9)之间的随机数。

设粒子的位置和速度都是Nt维向量，即它们的维度等于目标个数，这样任务分配问题的解空间是Nt维的。我们将粒子Pk的位置分量Ykj限制在[-Nu,Nu]之间。即当Ykj≥Nu时，令Ykj=Nu;当Ykj<-Nu时，令Ykj=-Nu。

令函数K(z)表示不大于z的最大整数，比如K(2.3)=2。为了从粒子Pk的位置向量Yk提炼出相应的任务分配解，定义个一个Nt维分配向量Ak=(Ak1,Ak2,…,AkNt)，其中分量Akj由式(12)计算:

(12)

分配向量Ak对应的任务分配方案表示：第Akj架飞行器被分配给了第j个目标。相应的xij可由式(13)计算:

(13)

数字i在Ak中出现时的下标的顺序集合组成了第i架飞行器任务的Θi。所有飞行器的任务{Θi，i∈{1,2,…,Nu}}组成了粒子Pk对应的任务分配解。值得注意的是，Ak的每个分量只对应一个飞行器编号，因此给每个目标只分配一个无人机，满足式(5)。但是基于Ak得到的任务分配解可能不满足式(3)与式(4)，因此并不一定是可行的。在更新粒子时，检验相应的任务分配解是否可行，如果不可行，则舍弃重新更新，直至得到满足式(3)和式(4)的解。

综上所述，多飞行器协同任务分配问题的粒子群算法为：

步骤1: 设定粒子种群规模大小、最大迭代次数。初始化粒子位置和速度，为每个粒子建立分配向量，使得对应的解满足式(3)～式(5)，并计算个体极值和全局极值。

步骤2: 计算每个粒子适应度指标，如果优于该粒子当前个体极值，则更新该个体极值；如果某个体极值好于当前的全局极值，则更新全局极值。

步骤3: 按照式(10)和式(11)更新每个粒子Pk的位置向量和速度向量，计算相应的任务分配向量Ak以及任务分配解Θi，i∈{1,2,…,Nu}。如果所得解是可行的，则接受Pk的更新；否则，不接受，重新更新粒子Pk直至得到可行任务分配方案。

步骤4: 如果迭代次数达到最大迭代次数，则停止迭代并输出全局极值为当前最优解，否则，转入步骤2。

3 算法仿真

已知任务区域内有14个目标T1～T14，有3个飞行器U1～U3。每个目标的位置、价值、威胁等属性如表1所示。飞行器的位置、价值等属性如表2所示。每架飞行器最大航程为500 km。假设一个目标对于不同的飞行器具有相同的威胁概率，一个飞行器对不同的目标具有相同的杀伤概率。

表1 目标情况

表2 飞行器情况

假设粒子群算法有20个粒子，迭代2 000次，威胁代价、航程代价以及攻击收益对应的权重s1=2,s2=1,s3=3。

图1给出算法迭代过程中，每一代更新中全局最优粒子的适应度函数指标。由图1可以看出，随着迭代次数增加，适应度函数得到了优化，最后收敛至稳定值。迭代过程完成后，可得一个方案：Θ1=(T9,T10,T11,T12,T13,T14)，Θ2=(T1,T2,T3,T4,T7,T8)，Θ3=(T5,T6)，其中的各个飞行器的代价与收益情况如表3所示。

图1 任务分配适应度指标变化图

表3 飞行器代价、收益指标

4 结论

利用粒子群算法求解多飞行器协同任务分配问题。首先，建立考虑飞行器载弹能力以及航程约束的数学模型，通过分析多飞行器可能遭受的威胁、付出的航程代价以及打击目标后获得的收益，构造出粒子群算法的适应度函数。然后，基于每个粒子的位置向量建立了对应的任务分配向量，从中提取出每个粒子对应的任务分配解，实现了粒子群算法连续性解的离散化。最后，利用粒子群算法进化原理，建立了一种

多飞行器协同任务分配方法，该方法的可行性可由仿真实验证明。提出的模型法和分配算法也可应用到其他多无人集群协同任务分配中。