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

赵慧武; 王鹏; 郭江宇

doi:10.15892/j.cnki.djzdxb.2022.05.021

PDF(579 KB)

弹箭与制导学报 ›› 2022, Vol. 42 ›› Issue (5) : 113-116. DOI: 10.15892/j.cnki.djzdxb.2022.05.021

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

作者信息 +

Particle Swarm Optimization Algorithm for Cooperative Task Allocation of Multi-vehicles

Author information +

文章历史 +

摘要

提出了一种多飞行器协同任务分配粒子群算法。首先,考虑飞行器载弹能力约束以及航程约束,建立多飞行器协同任务分配问题的数学模型。其次,分析粒子的连续性位置属性,为每个粒子构造了一个任务分配向量,从中可提取出相应的多飞行器协同任务分配解,实现了粒子群算法连续性解的离散化。最后,基于粒子群算法原理建立一种多飞行器协同任务分配算法,进行数字仿真实验,验证了所提算法的有效性。

Abstract

This paper proposes a particle swarm optimization (PSO) algorithm for co-allocating tasks among multi-vehicles. Firstly, by taking consideration of the vehicle carrying-capacity and range constraints, the mathematical model for the problem of multi-vehicle task assignment is presented. Secondly, the continuous position attribute of a particle is analyzed and a task assignment vector for each particle is developed. The corresponding task assignment solution can be extracted from the task assignment vector, achieving the objective of discretizing the continuous solution of PSO algorithm. Finally, based on PSO, a multi-vehicle collaborative task allocation algorithm is developed, and its effectiveness is verified by a digital simulation experiment.

导出引用

赵慧武, 王鹏, 郭江宇. 多飞行器协同任务分配粒子群算法研究[J]. 弹箭与制导学报, 2022, 42(5): 113-116 https://doi.org/10.15892/j.cnki.djzdxb.2022.05.021

ZHAO Huiwu, WANG Peng, GUO Jiangyu. Particle Swarm Optimization Algorithm for Cooperative Task Allocation of Multi-vehicles[J]. Journal of Projectiles, Rockets, Missiles and Guidance, 2022, 42(5): 113-116 https://doi.org/10.15892/j.cnki.djzdxb.2022.05.021

中图分类号： V279 TP18 (人工智能理论)

0 引言

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

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

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

1 数学模型

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

假定系统包含N_u架飞行器U={U₁,U₂,…,

U_{N_{u}}

}和N_t个目标T={T₁,T₂,…,

T_{N_{t}}

},N_u<N_t。目标的编号越小,优先级越高。飞行器优先攻击优先级高的目标。任务分配目标是为每架飞行器U_i分配一个攻击目标顺序集合Θ_i:

Θ_i=<T_w₁,T_w₂,…,T_wk>

(1)

飞行器U_i执行任务Θ_i时,先从初始位置B_i出发,依次攻击Θ_i中的目标,即先攻击T_w₁, 然后攻击T_w₂,以此类推,攻击完最后一个目标T_wk后返回初始位置,总航程表示为d(Θ_i) =d(B_i,T_w₁)+

\sum_{s \in {1,2, \dots, k - 1}}

d(T_ws,T_ws₊₁)+d(T_wk,B_i),其中函数d(·)表示两个目标之间或初始位置与目标之间的距离。

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

x_ij=

\{\begin{array}{l} 1 & 如 果 U_{i} 攻 击 了 目 标 T_{j} \\ 0 & 其 他 \end{array}

(2)

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

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

\sum_{j \in {1,2, \dots, N_{t}}}

x_ij≤Q_i_,max,∀i∈{1,2,…,N_u}

(3)

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

d(Θ_i)≤L_i_,_max,∀i∈{1,2,…,N_u}

(4)

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

\sum_{i \in {1,2, \dots, N_{u}}}

x_ij=1,∀j∈{1,2,…,N_t}

(5)

威胁代价:飞行器在执行任务时也可能受到敌方反击,可能被击中甚至击落。通过将威胁代价最小化,尽可能的减少飞行器损毁。假设飞行器U_i被目标T_j击中的概率为p_ij_,_U。可知U_i执行任务Θ_i后,没有被击中的概率是

\prod_{j \in {1,2, \dots, N_{t}}}

x_ij(1-p_ij_,_U),被击中的概率是1-

\prod_{j \in {1,2, \dots, N_{t}}}

x_ij(1-p_ij_,_U)。假设U_i的价值为V_i_,_U,相应的威胁代价函数为:

min C_i=V_i_,_U(1-

\prod_{j \in {1,2, \dots, N_{t}}}

x_ij(1-p_ij_,_U))

(6)

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

min L_i=d(Θ_i)

(7)

攻击收益:飞行器攻击目标将会获得一定的收益,其大小由目标本身价值和飞行器对目标的杀伤概率决定。通过将收益指标最大化,能尽可能的提高作战性能。假设p_ij_,_T是飞行器U_i对目标T_j的杀伤概率,V_j_,_T是目标T_j的价值。飞行器U_i执行Θ_i任务后收益函数为:

max H_i=

\sum_{j \in {1,2, \dots, N_{t}}}

(V_j_,_Tp_ij_,_Tx_ij)

(8)

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

min J=

\sum_{i \in {1,2, \dots, N_{u}}}

s₁C_i+s₂L_i -s₃H_i

(9)

s.t. 式(3)~式(5)

x_ij∈{0,1},∀i∈{1,2,…,N_u},∀j∈{1,2,…,N_t}

其中,s₁,s₂和s₃分别是威胁代价、航程代价以及攻击收益对应的权重。

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

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

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

在多维目标搜索空间中,假设粒子P_k在t时刻的位置向量和速度向量分别是Y_k(t)和Z_k(t),它们按照式(10)~式(11)演化:

Z_k(t+1)=wZ_k(t)+c₁Rand₁()(p_b(t)-Y_k(t))+c₂Rand₂()(g_b(t)-Y_k(t))

(10)

Y_k(t+1)=Y_k(t)+Z_k(t)

(11)

其中:Rand₁()和Rand₂()是分布在[0,1]之间的随机自然数;c₁和c₂通常情况下都取值为2;p_b(·)是粒子P_k的个体极值;g_b(·)是种群当前找到的全局极值;惯性权重w取(0.5, 0.9)之间的随机数。

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

令函数K(z)表示不大于z的最大整数,比如K(2.3)=2。为了从粒子P_k的位置向量Y_k提炼出相应的任务分配解,定义个一个N_t维分配向量A_k=(A_k₁, A_k₂,…,

A_{k N_{t}}

),其中分量A_kj由式(12)计算:

A_kj=

\{\begin{array}{l} K (\frac{Y_{k j} + N_{u}}{2}) + 1 & Y_{k j} < N_{u} \\ N_{u} & Y_{k j} \leq N_{u} \end{array}

(12)

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

x_ij=

\{\begin{array}{l} 1 & A_{k j} = i \\ 0 & 其 他 \end{array}

(13)

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

文中无人机任务分配的目标是:尽可能减少任务分配的威胁代价和航程代价,提高攻击收益。因此,对于由粒子P_k得到的任务分配解,我们将

\sum_{i \in {1,2, \dots, N_{u}}}

s₁C_i+s₂L_i-s₃H_i作为适应度函数F。设定F(P_k)越小,由粒子P_k得到多飞行器协同任务分配解的性能就越好。

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

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

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

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

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

3 算法仿真

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

表1 目标情况

编号	位置	价值	威胁概率
T₁	(67,23)	20	0.1
T₂	(65,70)	30	0.2
T₃	(25,55)	25	0.3
T₄	(8,32)	40	0.2
T₅	(35,30)	50	0.1
T₆	(40,44)	30	0.2
T₇	(42,90)	25	0.15
T₈	(19,40)	40	0.2
T₉	(60,35)	25	0.3
T₁₀	(66,55)	30	0.2
T₁₁	(80,98)	50	0.12
T₁₂	(94,89)	50	0.25
T₁₃	(32,65)	40	0.2
T₁₄	(87,30)	30	0.1

表2 飞行器情况

编号	位置	价值	杀伤概率	任务上限
U₁	(45,3)	130	0.9	6
U₂	(34,5)	100	0.8	7
U₃	(23,3)	80	0.7	5

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

图1给出算法迭代过程中,每一代更新中全局最优粒子的适应度函数指标。由图1可以看出,随着迭代次数增加,适应度函数得到了优化,最后收敛至稳定值。迭代过程完成后,可得一个方案:Θ₁=(T₉, T₁₀, T₁₁, T₁₂, T₁₃, T₁₄),Θ₂=(T₁, T₂, T₃, T₄, T₇, T₈),Θ₃=(T₅, T₆),其中的各个飞行器的代价与收益情况如表3所示。

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

Full size|PPT slide

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

编号	威胁代价	航程代价	攻击收益
U₁	73.39	480.32	202.5
U₂	58.06	462.34	172
U₃	16.8	88.27	56

4 结论

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

参考文献

列表( 原文顺序 | 文献年度倒序 | 文中引用次数倒序 ) 可视化分析

[1]	胡超芳, 杨娜, 王娜. 多无人机模糊多目标分布式地面目标协同追踪[J]. 控制理论与应用, 2018, 35(8):1101-1110. 本文引用 [1]

[2]	尹高扬, 周绍磊, 贺鹏程, 等. 国外多无人机协同任务分配研究现状及发展趋势[J]. 飞航导弹, 2016(5):54-58. 本文引用 [1]

[3]	牛轶峰, 肖湘江, 柯冠岩. 无人机集群作战概念及关键技术分析[J]. 国防科技, 2013, 34(5):37-43. 本文引用 [1]

[4]	赵明, 李涛, 苏小红, 等. 三维多无人机系统协同任务规划关键问题综述[J]. 智能计算与应用, 2016, 6(1):31-35. 本文引用 [1]

[5]	尹高扬, 周绍磊, 祁亚辉. 多无人机协同多任务分配研究[J]. 电光与控制, 2017, 24(1):46-50. 本文引用 [1]

[6]	廖沫, 陈宗基. 基于多Agent分布协同拍卖的动态目标分配算法[J]. 北京航空航天大学学报, 2007, 33(2):180-183. 本文引用 [1]

[7]	韩健. 基于多Agent的无人机协作控制[D]. 哈尔滨: 哈尔滨工业大学, 2012. 本文引用 [1]

[8]	王庆贺, 万刚, 柴峥. 基于改进遗传算法的多机协同多目标分配方法[J]. 计算机应用研究, 2018, 35(9):2597-2601. 本文引用 [1]

[9]	苏菲, 陈岩, 沈林成. 基于蚁群算法的无人机协同多任务分配[J]. 航空学报, 2008, 29(5):184-191. 本文引用 [1]

[10]

叶文, 朱爱红, 欧阳中辉, 等. 基于混合离散粒子群算法的多无人作战飞机协同目标分配[J]. 兵工学报, 2010, 31(3):331-336.

本文引用 [1] 摘要

针对多无人作战飞机(UCAV)协同目标分配问题，提出了一种基于混合离散粒子群算法的多UC针对多无人作战飞机(UCAV)协同目标分配问题，提出了一种基于混合离散粒子群算法的多UCAV协同目标分配方法。混合离散粒子群算法根据多UCAV协同目标分配问题的特点，设计了新的粒子群位置和速度更新公式，并且充分利用粒子群优化算法的全局搜索能力，同时利用禁忌搜索的局部搜索能力，使2种算法的优势得到互补，较为显著地提升了原算法的性能。仿真结果表明：混合离散粒子群算法能够有效地解决多约束条件下多UCAV 协同目标分配问题，并且算法简单、灵活，易于实现和扩展。

[11]	李炜, 张伟. 基于粒子群算法的多无人机任务分配方法[J]. 控制与决策, 2010, 25(9):1359-1363. 本文引用 [1]

[12]	韩庆田. 基于改进PSO的多UAV协同任务分配研究[J]. 兵器装备工程学报, 2019(11):74-78. 本文引用 [1]

PDF(579 KB)

Accesses

Citation

Detail

段落导航

摘要
Abstract
关键词
Key words
引用本文
0 引言
1 数学模型
2 多飞行器粒子群协同任务分配算法
3 算法仿真
表1 目标情况
表2 飞行器情况
图1 任务分配适应度指标变化图
表3 飞行器代价、收益指标
4 结论
参考文献

收稿日期	出版日期
2022-07-12	2022-10-20
发布日期
2025-01-16

选择文件类型/文献管理软件名称

选择包含的内容