中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2018 , Vol. 40 >Issue 5: 32 - 36

DOI: https://doi.org/10.3969/j.issn.1673-3819.2018.05.007

Theory & Research

Task Allocation of Multi-unmanned Aerial Vehicle Based on Improved Quantum Particle Swarm Optimization

  • DENG Ke 1 ,
  • LIAN Zhen-jiang 2 ,
  • ZHOU De-yun 2 ,
  • LI Xiao-yang 2
Expand
  • 1. Dalian Naval Academy, Dalian 116018
  • 2. Northwestern Polytechnical University, Xi’an 710072, China

Received date: 2018-04-13

  Revised date: 2018-04-27

  Online published: 2022-05-12

Fold

Abstract

Aiming at the problem that standard quantum particle swarm optimization (qpso) has poor adaptability to discrete and long solution space in multi UAV mission assignment, the adaptive inertia weight and quantum gate mutation operator based on the degree of particle convergence are proposed to improve the standard quantum particle swarm optimization (qpso) algorithm. The adaptive inertia weight accelerates the algorithm to approach the real Pareto solution, and coordinates the global and local search ability of the algorithm in discrete and long solution space, thus the algorithm has dynamic adaptability. While the quantum gate mutation operator can ensure diversity of solutions and optimization accuracy. The simulation results show that the improved quantum particle swarm optimization algorithm improves the accuracy and efficiency of task allocation and achieves the global optimum of task assignment in multi UAV task allocation problem.

Key words： Qpso; adaptive inertia weight; quantum gate mutation operator; task allocation

Cite this article

DENG Ke , LIAN Zhen-jiang , ZHOU De-yun , LI Xiao-yang . Task Allocation of Multi-unmanned Aerial Vehicle Based on Improved Quantum Particle Swarm Optimization[J]. Command Control and Simulation, 2018 , 40(5) : 32 -36 . DOI: 10.3969/j.issn.1673-3819.2018.05.007

随着计算机技术、人工智能的发展,无人机在军事领域取得了众多成功应用,在可预见的未来,多无人机协同执行作战任务是无人机技术的一个重要发展方向[1]。美军多所科研单位、军事机构都曾以全球鹰、捕食者、X-45、X-47为研究对象,进行了多无人机协同任务分配问题研究,探讨了多无人机协同任务分配在真实战场下的作战效能[2],并将多无人机协同作战融入一体化作战构想中[3]。多无人机协同作战是一个复杂化、多样化、智能化的作战过程,协同侦察攻击任务作为协同作战热点研究问题,指在作战区域中对目标实行协同侦察,对确定目标进行协同攻击与毁伤评估任务[4],多无人机任务分配是协同作战的基础与保障。
文献[5]将QPSO算法应用于复合结构的无人机编队分配问题,文献[6]提出了改进的MRS与MAS系统框架针对无人机对地任务分配,但是这些框架模型存在控制参数多且难以确定的缺点;文献[7]提出了一种基于MQABC算法求解无人机任务分配问题的方法,文献[8]利用Memetic算法求解协同分配模型,文献[9]设计了一种蝗虫仿生算法针对多无人机搜救任务。但是这些算法存在收敛时间不稳定的缺陷,在多无人机协同执行单一类型任务性能优异,面对多类型任务有所欠缺。
综上所述,研究一种适用于多无人机的多目标任务分配算法具有重要意义,为多无人机协同作战奠定基础并提供保障。本文综合考虑多无人机协同任务分配问题中的各类约束,结合多目标优化理论,构建了多无人机协同任务分配模型,在QPSO(Quantum-behaved Particle Swarm Optimization)算法基础上,借鉴变异的思想,设计了变异量子门克服了多无人机协同任务分配问题中解空间狭长导致求解算法陷入局部最优的缺点,且改进了QPSO算法下的惯性权重,自适应惯性权重使得该算法具有收敛速度快,搜索能力强的优点。

1 协同多任务分配模型

1.1 问题描述

近年来,许多学者对无人机协同任务分配模型进行了研究,但大多模型为单目标优化任务分配,面对多无人机多目标优化任务分配存在收敛慢、多目标函数优化性能差的不足,针对多无人机协同任务分配的特征,本文基于CMTAP[10]通用协同任务分配模型,结合多目标优化理论,融合多无人机协同作战环境下的多种任务协同约束,构建多无人机任务协同分配模型。
广域搜索空对地战场场景下,假定敌方目标位置与战场环境已经预先获得。U={U1,U2,…,Un}为执行任务的UCAV集合,n为参与任务的UCAV架次,T={T1,T2,…,Tm}为敌方m个目标;M={ M T 1, M T 2,…, M T m}为待执行的Mi×m个任务,对于每个目标Ti需要完成三种作战任务,分别为侦察(Classify)、攻击(Attack)和毁伤评估(Verify),因此任务集可写为
M = { M 1 , M 2 , … , M m } M i = T i , C l a s s i f y , A t t a c k , V e r i f y , T i ∈ T
为适当简化问题,无人机UCAVi在t时刻的位置由(xUi t,yUi(t))(i∈1,2,…,n)表示,目标位置Ti由(xTi t,yTi(t))(i∈1,2,…,m)表示。多无人机任务分配结果即为每一架无人机分配一条任务执行序列,即
D U A V i={ x T 0 , y T 0 , M T 0, x T 1 , y T 1 , M T 1,…,(xTk,yTk,MTk)}
其中,(xTi,yTi,MTij)为Ti目标下的任务合集中的第j类任务,每一架无人机须在执行完任务序列后返回出发基地。

1.2 任务约束

多无人机协同执行任务在实际战场环境中,首先无人机受限于自身的航程以及负载,其次对目标执行侦察、攻击、毁伤评估三类任务内在包含时序要求,最后需要充分考虑协同作战的效率性,因此多无人机协同任务分配问题的多类复杂约束条件可主要归为三种,分别是任务时序约束、任务协同约束以及无人机能力约束。
1)任务协同约束是指每一个作战任务只能被执行一次,即对于敌方目标i只执行一次侦察、攻击、毁伤评估任务。假定无人机i对于任务集合Mj的协同决策量为wij,若无人机i执行该任务则wij=1,否则wij=0,那么wij必须满足: ∑ i wij=1。
2)任务时序约束是指执行侦察、攻击、毁伤评估任务具有内在先后顺序要求。假定对于敌方目标i,执行侦察任务时刻为t1,执行攻击任务时刻为t2,执行毁伤评估任务时刻为t3,t1、t2、t3必须满足: t 1 < t 2 < t 3。
3)单架无人机任务载荷约束是指无人机执行作战任务所携带的挂载载荷有限。假定每架无人机任务载荷最大为Umax,那么约束条件为 ∑ i ui≤Umax。

1.3 问题描述

多UCAV总飞行航程指标能有效反映分配方案的作战耗损,即实际战场下多UCAV的耗油量、飞行时长等无人机自身属性约束,多UCAV的总飞行时间能直接反映分配方案的作战效率,即实际战场中多UCAV快速完成任务的能力,本文多无人机任务分配问题主要通过UCAV总飞行航程与UCAV总飞行时间这两项评价指标来评价不同任务分配方案的优劣。
假定每架无人机飞行速度恒定为V。本文的多无人机任务协同分配模型目标函数定义为:
minJ= J 1 , J 2
minJ1= ∑ i = 1 nLi= ∑ i = 1 n ∑ j = 1 k D U A V i j
minJ2=maxti=max L i V(i∈n)
式中J1为UCAV总飞行航程指标,其中Li为每一架UCAV的飞行航程, D U A V i j为第i架UCAV任务序列中相邻目标间距离;J2为UCAV总飞行时间指标。

2 改进的量子粒子群算法

2.1 QPSO算法描述

粒子群算法是由Kennedy和Eberhart在1995年提出的,该算法本质粒子在解空间追随最优的粒子进行搜索最优解,但是粒子群优化算法不是一个全局收敛算法,且全局搜索能力对速度上限过度依靠导致算法的鲁棒性较差。由于粒子群算法的劣势,Sun等根据量子力学中的粒子行为,假设粒子具有量子效应,提出了量子粒子群算法。在量子空间中,粒子状态X=[x1,x2,…,xn]由波函数ψ(x,t)来描述,波函数为粒子在量子空间的统计概率表述,实质上波函数模的平方即为粒子的概率密度函数,因此通过求解波函数可得到粒子在量子空间下出现位置的统计概率,以随机数模拟的方式类比波函数的观测坍缩即可得到粒子位置[11]。
QPSO算法的粒子进化方程为:
x t + 1=P±β|Pmbest-x(t)|ln 1 μ
其中:
P=αPi+(1-α)Pg
Pmbest= 1 M ∑ i = 1 MPi=( 1 M ∑ i = 1 MPi,1, 1 M ∑ i = 1 MPi,2,…, 1 M ∑ i = 1 MPi,N)
式中,α、μ为[0,1]上服从均匀分布的随机数;Pi为第t次迭代时粒子个体的最优位置,Pg为第t次迭代时粒子群体最优位置;P为第t次迭代时粒子个体最优位置与粒子群体最优位置之间一个随机位置;Pmbest为粒子群平均最好位置;M为粒子群中粒子的数目。
其中β为惯性权重,是影响QPSO算法收敛速度的一个重要参数,它可取为固定值,也可随着算法迭代动态变化,惯性权重一般采用线性递减策略。
β=βmax- β m a x - β m i n t m a x×t
通过设置惯性权重的上下边界βmax与βmin,根据式(7)按当前迭代次数t与设定迭代次数tmax的线性关系进行线性递减。通常情况下,β从1线性递减至0.5时能取得较好的结果。

2.2 变异量子门算子

QPSO算法在狭长且离散的解空间下进行全局搜索,在算法后期容易陷入局部最优解。为改进QPSO算法这一缺陷,提高对多无人机任务分配问题的适用性,本文借鉴遗传算法中的变异算子思想,设计了变异量子门算子。每次迭代后,根据粒子状态计算每个粒子的目标函数值,判断每个粒子是否处于支配状态,并将非支配解置入Pareto解集,维护并更新Pareto解集,使得Pareto解集中始终保持非支配Pareto最优解;若连续多次迭代过程中,Pareto解集未发生更新,则将粒子群按一定概率对密集程度高的部分粒子进行变异。
针对多无人机任务分配问题中解空间狭长的特点,采用通用量子门形式进行变异操作,以保证寻优过程中解的多样性。通用量子门包括量子旋转门与量子非门,其中量子旋转门使得粒子的原有量子编码进行旋转,获得新的角动量方向,量子非门则使得粒子编码位进行变异,若进行随机变异,粒子易出现飞离解空间边界的情况,将减弱算法寻优能力减缓收敛速度,因此本文根据解空间狭长的特点,以全局最优粒子位置与当前粒子最优位置取代量子非门下的随机变异操作,该种变异形式能提高算法的局部搜索能力,并且避免在狭长解空间下随机变异带来的退化现象,变异量子门算子如下所示:
x i d = 1 2 x i d + γ 1 P i + γ 2 P g γ 1 2 + γ 2 2 = 1
式中,γ1、γ2为[0,1]上服务均匀分布的随机数。通过把变异量子门算子的引入,实现了粒子群在局部最优解中的跳变,使得QPSO算法在多无人机任务分配问题下能保证广域的搜索空间,并保证后期的局部搜索能力。实验表明,变异概率随迭代次数线性递增,上界取0.2-0.3之间的值,可获得较好的效果。

2.3 自适应惯性权重

在QPSO算法中惯性权重的大小影响全局搜索能力与局部搜索能力。实验表明,惯性权重增大可加强全局搜索减弱局部搜索,惯性权重减小时反之。对于QPSO算法中粒子群而言,粒子群当前粒子位置与全局最优粒子位置间的距离表明了算法在解空间内搜索范围的覆盖尺度。为使得QPSO算法在搜索最优解过程中的自适应机制,对于离全局最佳位置点近的粒子,应适当增大β,以保证粒子群更大的覆盖范围;而对离全局最佳位置点远的粒子,应适当缩小β,防止粒子过度分散,减弱算法的局部搜索能力。此外,在算法早期,粒子搜索域需要保持较大的覆盖范围,若粒子群过度分散,则会导致算法收敛慢的问题,此时需要控制粒子群的分散程度,防止粒子群搜索发散;随着算法迭代的进行,算法后期需要更为精确的搜索,若粒子群过于集中时,容易陷入局部最优点,使得算法陷入局部最优解,因此需要根据迭代次数与粒子群集中程度调整惯性权重,适当放大粒子群的搜索范围。
基于以上讨论,本文采用当前粒子状态与全局最优粒子状态差值来衡量粒子群的集中程度,结合算法的迭代时期来动态调节惯性权重,即
β=0.9×( 1 e 1 + 7 t / t m a x)×( 1 e | P - P g |)
其中,t为当前迭代次数,tmax为最大迭代次数,P为当前粒子状态,Pg为全局最优粒子状态。

2.4 改进QPSO算法流程

本文提出的改进QPSO算法流程如下:
步骤1 没置迭代次数t=0,设置基本参数,如总迭代次数、粒子数量等。初始化每一个粒子的波函数,计算粒子的位置概率密度函数获得粒子位置,Xi中储存最优的粒子,Pi 0=Xi(0)。
步骤2 根据式(6)计算粒子群的平均最好位置。
步骤3 循环执行步骤4-9,直到粒子群所有粒子均完成更新。
步骤4 对粒子i的每一维,根据式(5)计算得到一个当前位置与全局最优位置间的一个随机点位置。
步骤5 计算粒子的新位置。
步骤6 根据多无人机任务分配模型指标,计算粒子i当前位置X(t)的适应度f(X t),并根据步骤5获得的粒子新位置X(t+1)计算适应度f(X t + 1),根据两适应度的支配关系更新最优个体值,若无支配关系则按设定概率判定是否更新。
步骤7 对于粒子i,将该粒子适应值与全局最好位置的适应值比较,若支配则更新。
步骤8 根据Pareto占优理论评价更新后的粒子群并维护Pareto最优解集。
步骤9 根据Pareto解集更新情况与变异概率,对粒子群进行量子门变异操作,产生新个体计算适应度后重组种群。
步骤10 直至满足循环条件,输出Pareto解集,否则返回步骤4。

3 仿真实验

为验证本文所提出的改进QPSO算法相比标准QPSO算法针对多无人机任务分配问题更具有有效性,本文在表1下的假定环境中,将QPSO算法与改进QPSO算法进行仿真实验对比,分析改进粒子群算法在求解多无人机任务分配问题上的可靠性与优越性。
表1 UCAV与目标属性
编号 坐标
1 (10,20)
2 (20,20)
UCAV属性 3 (30,50)
4 (45,60)
5 (80,95)
1 (80,90)
2 (55,20)
目标属性 3 (40,65)
4 (70,45)
5 (10,30)
假定作战环境为我方须对敌方5个目标区域执行作战任务,共出动5架无人机。5个目标区域所执行的任务集均为Classify、Attack、Verify三类任务,即总任务数M=15;我方无人机均具有侦察、打击、毁伤评估能力,且各个无人机出发基地位置不同,须在执行任务后返回出发基地,基地位置与目标位置见表1。
QPSO算法和改进QPSO算法均设置粒子数量为50,最大迭代次数为2000;改进QPSO算法主要参数设置如下:Pareto解集更新不变次数为30次,变异量子门概率设为0.25。两算法分别独立运行30次,各算法的分配方案如表2所示。
表2 分配方案
算法类型 指标 方案
1 2 3 4
QPSO J1 680.2145 698.0308 754.5010 866.4472
J2 27.2052 17.0725 22.2825 19.1604
改进QPSO J1 679.7740 694.3121 750.0912 856.4350
J2 22.1864 16.5379 19.3293 20.0260
图1与图2分别给出了改进QPSO算法迭代过程中,总飞行航程指标与任务完成时间指标每一代更新中最优值迭代图。由图可以看出,随着算法的迭代次数递增,目标函数均得到了优化,最后收敛至稳定值。并且从收敛曲线可以看出,改进后的惯性权重能根据算法的收敛程度,在粒子群聚集搜索空间小时,增大粒子的搜索范围,使得算法避免过早收敛,而在粒子群过于分散时,惯性权重自适应减小,防止算法收敛缓慢。
图1 航程代价变化曲线
图2 任务执行时间变化曲线
由表2可以看出,改进QPSO算法在Pareto解的前沿上搜索能力总体优于基本QPSO算法。其中改进QPSO算法下的方案1、2、3均支配QPSO算法下的方案1、2、3解集;此外,改进QPSO算法的方案1对QPSO算法下的方案1与3是支配的,并且改进QPSO算法下方案2解也对QPSO下方案2、3、4支配。由此可以看出,在两种算法获得的Pareto解集上,改进的QPSO算法能更有效地进行局部搜索,使得算法跳出局部最优解,且能保证解集的多样性。因此改进QPSO算法相比基本QPSO算法在多无人机任务分配问题上更有效。将改进QPSO算法任务分配方案2转换为UCAV任务对应表与任务执行序列,如表3与表4所示。
表3 UCAV对应任务
目标编号 UCAV编号
1 2 3 4 5
1 Classify 0 0 0 0 1
Attack 0 0 1 0 0
Verify 0 0 0 0 1
2 Classify 0 0 0 1 0
Attack 1 0 0 0 0
Verify 0 0 0 0 1
3 Classify 0 0 1 0 0
Attack 0 1 0 0 0
Verify 0 0 1 0 0
4 Classify 0 0 1 0 0
Attack 0 0 0 1 0
Verify 1 0 0 0 0
5 Classify 1 0 0 0 0
Attack 0 1 0 0 0
Verify 0 1 0 0 0
表4 任务执行序列
UCAV编号 执行目标与执行任务类型
1 T5(Classify)→T2(Attack)→T4(Verify)
2 T5(Attack)→T3(Attack)→T5(Verify)
3 T3(Classify)→T4(Classify)→T1(Attack)→T3(Verify)
4 T2(Classify)→T4(Attack)
5 T1(Classify)→T2(Verify)→T1(Verify)

4 结束语

本文通过综合考虑多无人机任务分配约束条件,以多UCAV总飞行航程和多UCAV总飞行时间两个关键指标作为任务分配方案的评价标准,构建多无人机任务分配模型,采用改进的QPSO算法进行优化求解多无人机任务分配问题。通过仿真得到的多无人机协同任务分配方案显示,改进的QPSO算法能更好地搜索Pareto前沿,更为有效地解决多无人机任务分配问题。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
王鹏飞. 多机协同作战效能评估及其不确定问题研究[D]. 郑州: 郑州大学, 2014.

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

[3]
US AIR FORCE. Small-Sized Unmanned Aerial System(SUAS) Flight Planning in 2016-2036[R]. USDOD: US Air Force, 2016.

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

[5]
Omkar S N, Khandelwal R, Ananth T V S, et al. Quantum behaved Particle Swarm Optimization (QPSO) for multi-objective design optimization of composite structures[J]. Expert Systems with Applications An International Journal, 2009, 36(8):11312-11322.

DOI

[6]
Venugopalan T K, Subramanian K, Sundaram S. Multi-UAV Task Allocation: A Team-Based Approach[C]// Computational Intelligence, 2015 IEEE Symposium. IEEE, 2015:45-50.

[7]
赵辉, 李牧东, 韩统, 等. 基于多目标MQABC算法的无人机协同任务分配[J]. 华中科技大学学报: 自然科学版, 2016, 44(3):121-126.

[8]
温攀, 王社伟, 徐明仁. 基于Memetic算法的多无人机任务分配研究[J]. 计算机仿真, 2013, 30(5):82-85.

[9]
Kurdi H, How J, Bautista G. Bio-Inspired Algorithm for Task Allocation in Multi-UAV Search and Rescue Missions[C]// AIAA Guidance, Navigation and Control Conference, 2016.

[10]
Shima T, Rasmussen S J, Sparks A G, et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33(11):3252-3269.

DOI

[11]
Kennedy J, Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks, 1995.

[12]
Sun J, Feng B, Xu W. Particle swarm optimization with particles having quantum behavior[C]// Evolutionary Computation, 2004.

Options
Outlines

/

〈 〉