基于粒子群算法的多无人机任务分配方法概要.docx
- 文档编号:18528844
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:14
- 大小:34.58KB
基于粒子群算法的多无人机任务分配方法概要.docx
《基于粒子群算法的多无人机任务分配方法概要.docx》由会员分享,可在线阅读,更多相关《基于粒子群算法的多无人机任务分配方法概要.docx(14页珍藏版)》请在冰点文库上搜索。
基于粒子群算法的多无人机任务分配方法概要
第25卷第9期Vol.25No.9
控制与决策
ControlandDecision
2010年9月
Sep.2010基于粒子群算法的多无人机任务分配方法
文章编号:
1001-0920(201009-1359-05
李炜,张伟
(电子科技大学电子科学技术研究院,成都610054
摘要:
作为多无人机系统应用的一项关键技术,任务分配是一个多维互异离散变量的优化问题.采用混合整数线性规划方法构造优化函数,并利用群智算法中的粒子群算法来求最优解,这样可以解决多无人机的任务分配问题.针对互异性要求进行必要的算法改进.数值仿真实验表明,该粒子群算法可以迅速找到优化函数的最优解,从而高效地实现多无人机的任务分配.
关键词:
多无人机;任务分配;粒子群算法;多维互异变量;代价函数
中图分类号:
V249.122文献标识码:
A
Methodoftasksallocationofmulti-UAVsbasedonparticlesswarmoptimization
LIWei,ZHANGWei
(ResearchInstituteofElectronicScienceandTechnology,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China.Correspondent:
LIWei,E-mail:
aegeanwei@
Abstract:
Taskallocationisakindofkeytechnologyintheapplicationofmulti-UAVssystems,anditisamutuallyexclusivemulti-dimensionsoptimalproblem.Mixedintegerlinearprogramisappliedtobuildtheoptimalfunction,andparticleswarmoptimization(PSOalgorithmisutilizedforsearchingthebestsolutioninordertorealizethetaskallocationofmulti-UAVssystem.InthePSOalgorithm,itisnecessarytomakesomemodificationtosuitfortheacquirementofmutuallyexclusive.Thenumericalsimulationshowsthatthepresentedalgorithmcanfindtheoptimalsolutionrapidlyandaccomplishthetaskallocationofmulti-UAVsefficiently.
Keywords:
Multi-UAVs;Tasksallocation;PSO;Mutuallyexclusive;Costfunction
1引言
由多个简单无人机通过协同、协作组成集群系统来完成单个无人机无法完成或难以完成的工作[1],已经成为各国研究者的普遍共识.因此,对于多无人机系统的研究受到了广泛关注.多无人机可实现多种作战任务,而基本的工作状态包括4种:
1搜索目标状态:
遵照事先规划的搜索路径飞行,寻找地面目标;
2识别目标状态:
利用目标识别算法判断目标为真目标、被击中的目标还是暂时无法确切判断类型的目标;3攻击目标状态:
对于已经被识别为真的目标,无人机进入交会阶段,对其实施攻击;4毁伤评估状态:
判断被攻击的目标是否还具备战斗力[2-4].
针对无人机在某一时刻发现的目标,如何能够合理地将无人机以最佳的任务状态分配给最适合的目标是能否发挥多无人机协同工作效能的关键.国内外对该问题的研究已经成为热点.其中有代表性的研究成果包括:
1采用网络最优模型进行任务分配的方法,它是模拟货物的供应需求的转换和变化,从而实现无人机和目标之间的任务分配[5,6];2利用多智能体的方法,将每个无人机都作为一个智能体,通过相互之间的交互实现任务的分配[7,8];3利用禁忌搜索的方法,依次对无人机分配任务,反复迭代,直至找到最优解[9];4采用混合整数线性规划方法,该方法可以找到一个最优解,但计算量较大[10,11].因此,在此基础上,有很多研究者结合蚁群算法、退火算法、遗传算法等最优化方法找到最优解.目前,通过模拟生物群体的行为来解决计算问题已经成为了新的研究热点.其中粒子群算法作为一种具有较强寻优能力、简
收稿日期:
2009-08-27;修回日期:
2009-10-23.
基金项目:
国防预研项目(402030203;电子科技大学中青年学术带头人培养计划项目.
作者简介:
李炜(1980−,男,内蒙古包头人,助理研究员,博士,从事多机协同、智能控制等研究;张伟(1974−,男,四川达州人,副研究员,博士,从事智能系统、仿真技术等研究.
1360控制与决策第25卷
单通用,且鲁棒性强的方法被广泛应用于科学研究和工程实践中.本文的目标就是采用整形线性规划方法构造最优函数,利用群智算法中的粒子群算法求出最优解,从而实现多无人机的目标分配.
2构造任务分配函数
无人机根据识别目标的类型所需执行的任务包括3种:
1对于真目标,执行攻击任务;2对于被攻击过的目标,执行毁伤评估任务;3对于无法判断类型的目标,执行再识别的任务.无人机根据自身与目标所处的位置和角度对目标进行分类识别,并且确定分类识别的置信度.如果识别结果低于预置的置信域,则报告为暂时无法识别类型的目标,这样选择无人机执行再识别的任务;一旦目标被确认为真目标,则无人机可以选择该目标进行交会;一旦无人机和目标满足了交会条件,无人机即可对目标进行攻击;目标被攻击后,其他无人机可对其进行毁伤评估,判断其状态,完全被摧毁或是仍然可以工作.
从上述的描述可以看出,无人机对目标识别分类的准确程度是影响任务分配的首要因素.没有对目标正确的识别也就不会有合理的任务分配.为了简化目的,本文在建模时,认为无人机可以正确地对目标进行识别分类,而不会出现识别类型错误的情况.此外,值得注意的是,本文研究的对象是微小型无人机,其对目标的攻击是通过自身的战斗部起爆来实现的,即无人机实施攻击也意味着本身生命周期的结束.无人机的任务分配过程中需要考虑的因素包括:
任务的优先级、时间约束以及任务路径的可飞性.任务的优先级是指对于每个被发现的目标根据其识别类型顺次执行相应的任务,例如经识别认为是真目标时,则应该先执行攻击任务,然后才能执行毁伤评估.时间约束是指给定的任务需要在一个特定的时间域内完成,超过了这个时间域,就可能意味着任务的失败,特别是在打击时间敏感目标的过程中,如果完成任务所需的时间过长,则很可能会丢失目标,从而使任务失败.如果假设所有无人机的飞行速度相同,那么任务路径越短,所对应的任务完成时间也就越短.任务路径的可飞性是指无人机在执行任务时所需飞过的路径满足运动学和动力学约束条件.
2.1距离因素
如果假设无人机飞行速度相同,则时间约束条件就转化为无人机与目标之间的距离因素.无人机与目标的距离越近,则完成任务的时间就越短,因此将该无人机分配给此目标的机率也就越大.用数学表达式表示如下:
设距离因素对任务分配的影响为α1,则
a1=w1dij/dmax.(1其中:
dij表示第j个无人机到第i个目标直接的距离;
dmax表示所有无人机中相对第i个目标的最大距离;w1为(0−1之间的一个数,表示距离因素对于任务分配影响程度的权重值,数值越大表明距离因素对任务分配的结果影响越大,反之则越小.
2.2角度因素
任务路径的可飞性要求飞行路径的最大曲率要满足无人机飞行性能的要求.在任务分配时,无人机所产生的路径受到多种不确定因素的影响,很难精确地对可飞路径加以量化描述.本文主要根据无人机当前的飞行方向与目标视线之间的夹角来描述产生任务路径的可飞性.如图1所示,θ表示无人机当前飞行方向与目标视线之间的夹角,虚线表示任务路径.由图1可以看出,目标1与无人机1生成的夹角θ11要小于目标2与无人机1生成的夹角θ21,相应的任务路径的曲率也较小,可飞性也就相应的越好;而对目标2而言,与无人机1生成的夹角θ21要大于与无人机2生成的夹角θ22,相应的任务路径曲率也较大,所以可飞性也就越差.因此,利用无人机当前的飞行方向与目标视线之间的夹角可大致地定量描述产生任务路径的可飞性.
1
2
θ
11
θ
22
θ
21
v
2
v
1
21
图1无人机可飞性示意图
设无人机当前的飞行方向与目标视线之间的夹角对任务分配的影响为
a2=w2θij/θmax.(2其中:
θij为第j个无人机的飞行方向与第i个目标视线的夹角;θmax为无人机飞行方向与目标视线的最大夹角,根据夹角的定义,θmax=180;w2为飞行方向与目标实现夹角对于任务分配结果的影响程度,数值越大,表明对结果的影响越显著,反之则越微弱.
2.3时间因素
无人机剩余飞行时间主要用来评价执行任务的代价.例如在执行攻击任务时,选择一架刚出发的无人机要比选择一架燃油即将耗尽的无人机付出的代价大得多.因此,在进行任务分配时,尽可能将作战任务分配给剩余飞行时间少的无人机.对任务分配的影
第9期
李炜等:
基于粒子群算法的多无人机任务分配方法
a3=w3
j
tmax
.
其中:
tj为无人机j的剩余飞行时间;tmax为无人机最
大的飞行时间;w3为无人机剩余飞行时间对任务分配结果的影响程度,数值越大,表明剩余飞行时间对结果的影响越大,反之越小.
综上所述,可构造无人机任务分配的代价函数为
C(xij=Pi(α1+α2+α3=
Pi(w1
dij
dmax+w2θijθmax+w3tjtmax
.(4其中:
xij为j无人机作用于i目标;Pi为目标的识别
概率,当Pi落入不同的识别置信区域时,分别判定为无法识别类型的目标、真目标、被攻击的目标;相对应地,将C(xij的定义域写为{Rcost,Acost,Bcost},分别为再识别任务代价、攻击任务代价和毁伤评估任务代价.对应不同的目标类型,式中的权重取值不同.2.4优化问题
由此可将任务规划问题转化为寻找下列优化问题的最优解:
Cost=min
n∑i=0
C(xijxij.(5s.t.C(xij∈{Rcost,Acost,Bcost};
(6n∑i
xij=1,j=1,2,⋅⋅⋅;(7m∑j
xij=1or0,i=1,2,⋅⋅⋅;
(8xij∈{0,1},i=1,2,⋅⋅⋅,j=1,2,⋅⋅⋅.
(9
其中:
n为目标的数量,m为无人机的数量,i为目标编号,j为无人机编号,C(xij为i无人机与j目标之间的代价系数.约束条件(6表示代价系数只能是3种代价系数之一;约束条件(7表示对于任意一个目标,当前时刻只能有一个无人机对其发生作用;约束条件(8表示在任意时刻,任意一个无人机至多对一个目标发生作用,并假设无人机的数量大于等于各类目标的总数量,对于未与目标配对的无人机则继续执行搜索任务;约束条件(9表示xij=0为(0-1变量,当j无人机作用于i目标时,xij=1,否则xij=0,表示如下:
x=
{
1,子弹药j作用于目标i;0,否则.
3粒子群算法求解
粒子群优化算法是由美国的Kennedy和Elberhart受到鸟群觅食行为的启发,于1995年提出的.最初的设想是仿真简单的社会系统,研究解释复杂的社会行
维搜索空间“流动”的,粒子在搜索空间内的位置变化是以一个个体成功地超过其他个体的社会心理意向为基础的.因此,群中粒子的变化受到其邻近粒子经验或知识的影响,一个粒子的搜索行为受到群中其他粒子的搜索行为的影响.
粒子群算法具有计算的快速性和算法本身的易实现性,由于粒子群迁移过程是有方向性的,搜索过程中运用反馈原理并采用并行计算技术,具有较高的搜索效率,这是其他算法所不具备的优势.
无人机的任务分配问题是离散变量问题,因此利用粒子群算法来进行优化问题求解时,需要将更新的速度离散化,粒子的位置也随之被离散化.具体方法是利用Miranda和Fonscca提出的概率舍入的方法[12],按速度更新后的数值到取值空间内每个整数的距离的概率比例进行舍入.3.1
基本优化算法
将n∑i=0
xij记为微粒Xk,其位置变化表现为编号
为i的目标和编号为j的无人机之间的任务配对情况.它经历过的最好位置记为pbest,在群体所有微粒经历过的最好位置的索引号记为gbest.
微粒k的速度用Vk=(vk1,vk2,⋅⋅⋅,vkn表示,对于每一代,vki根据如下方程迭代:
vki(t+1=wpvki(t+c1r1(pki(t−Xki(t+
c2r2(pgi(t−Xgi(t,
(10Xki(t+1=Xki(t+vki(t+1.
(11
其中:
wp为线性递减权重[13];c1,c2为学习常数,r1,r2为介于0到1的随机数;pki(t为每个微粒到目前为止,所出现的最优位置;pgi(t为所有微粒到目前位置,所出现的最优位置.
在搜索时,微粒的位置被最大位置和最小位置限制,如果某微粒在某维的位置超出该维的最大位置或者最小位置(弹目的任务分配超过了目标数或无人机数范围,则该微粒的位置被限制为该维的最大位置或最小位置.同样,微粒的速度也被限制于最大速度和最小速度之间[14],具体公式如下:
vki=
{
vmax,vki>vmax;
−vmax,vki<−vmax.
其中:
vmax为设定的最大速度向量.当粒子速度过大时,将可导正回适当速度向量,如粒子往负向速度过大时,则会限定最大负向速度.3.2
粒子群改进算法流程
在任务分配的求解问题中,变量的取值是离散
1362控制与决策第25卷
的,所以为非连续的优化问题.在利用PSO算法进行优化时,必须进行变量的离散化:
一方面需要将粒子的位置离散化,另一方面也要将更新速度离散化.同时更为重要的是,在利用PSO算法时,必须要满足约束条件(7和(8的要求.因此粒子在选择新位置的时候,并不是在全定义域内进行选择.粒子移动的位置表示该粒子对于任务分配的结果,目标的数目也是微粒的维数,粒子的更新速度为无人机和目标之间的任务配对的变化情况.根据约束条件要求,任意目标只能有一个无人机对其发生作用,任一无人机至多也只能对一个目标执行任务.因此在PSO算法的寻优过程中,微粒各维的最终位置应该是互异的,在本文中采用多次迭代的方法,直到各维变量的位置都不同时,才继续往下执行,具体的算法流程如图2所示.
图2粒子群算法流程图
Step1:
初始化设置微粒群的规模,惯性权值,加速系数,最大允许迭代次数.
Step2:
针对每个微粒,生成随机的初始无人机和目标的任务配对,并计算目标评价函数.
Step2.1:
依次对每个目标分配一个无人机来执行作战任务,如果无人机和目标的任务分配出现同一个无人机对两个不同的目标执行任务时,则再重新分配,直到此类情况不再出现(不重复原则.
Step2.2:
当每个微粒的初始弹目任务分配满足要求时,按目标评价函数评价各微粒的初始适应值.
Step3:
根据公式计算各微粒新的速度,并对各微粒新的速度进行限幅处理.
Step4:
根据公式计算各微粒新的位置,并对各微粒新的位置进行限幅处理.
Step5:
当微粒处于新位置时,同时存在微粒对于无人机和目标的任务分配出现Step2.1的情况时,重新执行Step3和Step4,直到满足要求.
Step6:
按目标评价函数重新评价各微粒适应值.
Step7:
对每个微粒,比较其当前适应值和其个体经历过的最好适应值,若当前适应值更优,则令当前适应值为其个体历史最好的适应值,并保存当前位置为其个体历史最好位置(个体最优弹目任务分配.
Step8:
比较群体所有微粒的当前适应值和全局历史最好的适应值,若某微粒的当前适应值更优,则令该微粒的当前适应值为全局历史最好适应值,并保存该微粒的当前位置为全局历史最好位置(全局历史最优弹目任务分配.
Step9:
若满足停止条件,则搜索停止,输出搜索结果;否则,返回Step3继续搜索.
Step10:
gbest为搜索到的最优值.
粒子群改进算法伪码如下:
初始化
粒子数量、最大迭代次数、结束标志阈值、目标数量、无人机数量;
Fori=1粒子数
计算每个粒子的初始位置(为每个目标分配无人机;
计算粒子初始移动速度;
End;
Do
Fori=1粒子数
根据目标代价函数计算粒子pi的个体适应值;
If此适应值优于此前该粒子最好位置pbest的适应值
更新pbest值;
End;
End;
从所有粒子中找出个体适应值最大的位置pbest赋给gbest,并记录该粒子的任务分配结果;
Fori=1粒子数
根据公式更新pi的速度,速度被限制在[−vmax,vmax]之间;
根据公式更新pi的位置,位置被限制在可行域上(可行的任务分配;
End;
While(当最优适应值大于结束标志域且迭代次数小于最大迭代数
输出最优结果.
4数值仿真
为了验证本文提出的任务分配算法的性能,设定静止目标数量为5个,分别处于(300,10,(350,10,(400,10,(450,10和(500,10.其中:
目标3为无法识别的目标,目标4为被攻击过的目标,其他目标都为
第9期
李炜等:
基于粒子群算法的多无人机任务分配方法
1363
真目标.无人机的数量为50个,其x坐标50开始,依次增大10;y坐标都为500,速度方向都是指向y轴的负半轴.分别设粒子数量为1000,2000,5000,最大迭代次数为100,惯性权值设为0.5.经过多次计算得出的最终结果为:
第25号无人机对第1个目标执行攻击任务,第30号无人机对第2个目标执行攻击任务,第35号无人机对第3个目标执行再识别任务,第40号无人机对第4个目标执行毁伤评估的任务,第45号无人机对第5个目标执行攻击任务,最终的代价函数适应值为0.78.
在粒子数设为1000时,经过100次的迭代会出现结果不最优的情况.而当粒子数设为5000时,每次计算都可以获得最优解.由此可以看出,粒子数的规模对寻找最优解有直接的影响,如图3所示.
20
406080100
0.8
0.911.1
Na=5000Na=2000Na=1000
图3适应函数值收敛曲线
由图3可知,在粒子数较多时,经过较少的迭代次数(30代就可以收敛到最优值,而当粒子较少时,一般需要经过更多次的迭代才可以收敛到最优值.
将无人机的飞行方向改为从与,x轴正向呈−65˚开始,以一度的差值依次递减.经过多次计算得到的结果为:
第25号无人机对第1个目标执行攻击任务,第32号无人机对第2个目标执行攻击任务,第35号无人机对第3个目标执行再识别任务,第38号无人机对第4个目标执行毁伤评估的任务,第40号无人机对第5个目标执行攻击任务,最终的代价函数适应值为1.187.此外,在此条件下,将权重值w2从1.5调整到0.5时,最优结果又变为:
第23号无人机对第1个目标执行攻击任务,第25号无人机对第2个目标执行攻击任务,第28号无人机对第3个目标执行再识别任务,第30号无人机对第4个目标执行毁伤评估的任务,第32号无人机对第5个目标执行攻击任务,最终的代价函数适应值为0.862.
5结论
多无人机的任务分配是多维互异离散变量寻优问题,对其求解是一项非常耗费计算的工作.利用概念清晰、搜索速度快、易于实现的粒子群算法来进行求解是一项非常好的选择.本文通过对速度更新和位置更新的多次迭代来适应多维变量互异性的要求,获得了比较好的寻优效果.从文中的数值仿真结果可以
看出,在1000∼2000个粒子群规模的条件下,经过几十次迭代就可以找到最优解,耗费计算资源小,可满足机载计算机甚至是单片机的运算要求.因此,利用粒子群算法可以高效快速地解决多人机的任务分配问题.
参考文献(References
[1]
DavidFrelinger,JoelKvitky,WilliamStanley.Proliferatedautonomousweapons[R].
Santa
Monica:
Rand
Corporation.[2]
CoreySchumacher,PhillipRChandler,StevenRasmussen.Taskallocationforwideareasearchmunitinos[D].Anchorage:
Wright-PattersonAirForceBase,2002.[3]
RobertDunkelⅢ.Investigationofcooperativebehaviorinautonomouswideareasearchmunitions[D].Ohio:
AirForceInstituteofTechnology,2002.[4]
OrhanGozaydin.Analysisofcooperativebehaviorforautonomouswideareasearchmunitions[R].Ohio:
AirForceInstituteofTechnology,2002.[5]
KendallNygard,PhillipChandler,MeirPachter.Dynamicnetworkflowoptimizationmodelsforairvehicleresourceallocation[C].AmericanControlConf.Arlington,2001:
25-27.[6]
SchumacherCJ,ChandlerPR,RasmussenSJ.Taskallocationforwideareasearchmunitionsviaiterativenetworkflowoptimization[C].ProcoftheAIAAGuidance,Navigation,andControlConf.Monterey,2002:
3472-3477.[7]
姚宗信,李明,陈宗基.多机协同作战任务决策方法多智能体结构框架[J].电光与控制,2008,15(3:
1-4.(YaoZX,LiM,ChenZJ.Multi-agentframeworkofmissiondecision-makingmethodformulti-aircraftcooperativecombat[J].EletronicsOpticsandControl,2008,15(3:
1-4.[8]
曹菊红,高晓光.多架无人机协同作战智能指挥控制系统[J].火力与指挥控制,2003,28(5:
22-24.
(CaoJH,GaoXG.Agent-baseddesignformulti-ucavintelligentco
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 粒子 算法 无人机 任务 分配 方法 概要