基于多Agent无人机协同侦察任务规划模型

褚　政，郭分林,粘松雷

(1.海军航空工程学院,山东烟台　264001;2.南昌陆军学院,江西南昌　330103)



基于多Agent无人机协同侦察任务规划模型

褚政1，郭分林2,粘松雷1

(1.海军航空工程学院,山东烟台264001;2.南昌陆军学院,江西南昌330103)

建立了多无人机协同侦察任务规划模型,在考虑侦察时间间隔约束和目标载荷需求基础上,给出了位于不同基地的无人机优化部署和调度策略,并提出了基于多Agent的优化搜索仿真算法,利用Matlab实现了无人机优化配置和任务规划模型,得出了无人机优化配置和任务规划方案,最后分析了模型算法存在的某些不足,提出了模型改进的方向。

无人机;多Agent;协同侦察;任务规划;优化搜索

无人机(Unmanned Aerial Vehicle,UAV)是一种具备自主飞行和独立执行任务能力的新型作战平台[1]。利用多无人机进行协同侦察,实时获取侦察目标的动态信息,通过信息融合处理技术,能够及时获得准确的战场态势,为部队实施精确打击和战场评估等提供辅助决策支持。多无人机协同侦察可以分解为侦察目标分配、侦察路径规划、渐近轨迹跟踪等多个子问题[2]。

多无人机协同路径规划是指通过选择无人机的数量、配置任务载荷、确定侦察目标、规划航迹,使得多无人机协同侦察的整体效能最大,且代价最小。多无人机协同侦察任务规划属于非确定性多项式(Nondeter Ministic Polynomial,NP)问题,若无人机数量较多时,使用穷举法或最优控制法求解将耗费大量的计算代价,甚至难以实现[3]。从近几年该领域的研究情况看,求解问题的方法主要以现代智能算法为主,如:神经网络、遗传算法、模拟退火、进化算法与粒子群优化算法等[4]。这些算法有一定的优势,但是需进行大量与实际不符的情况假设,因此,本文提出使用“基于多Agent搜索优化算法”,求取一个较优解,然后不断应用阶梯式逐步逼近最优解。

1　协同侦察规划问题案构建

为了使得问题研究更具有针对性,本文首先以一个具体的实例为例,归纳总结成一个一般性问题。现设定一个具体问题:某部队现有3个可供无人机起降的停靠基地,分别为基地S、基地T、基地P,每个基地均配备有一定数量的无人机,每架无人机可携带一种任务载荷去执行侦察任务。已知基地S配有载荷Ⅰ和Ⅱ,基地T配有载荷Ⅲ和Ⅳ,基地P配有载荷Ⅰ、Ⅱ和Ⅲ。该部队承担着某区域内30个点目标的侦察任务,其中包括6个A类目标、13个B类目标、11个C类目标。根据侦察目标的特点和实际需要,要求对A类目标每天用不同的载荷侦察三次,并且间隔时间4至8小时。对B类目标每天至少用不同的载荷侦察两次,间隔时间至少6小时。对C类目标每天至少用某种载荷侦察一次。该型无人机平均航速200km/h,最大续航时间为10小时。无人机根据续航能力可以选择最近的基地降落进行能量补充和必要的维护保养(每次需要时间5小时),之后可以连续执行侦察任务,但在24小时内执行完最后一次任务要返回原停靠基地。

通过分析,该问题是一个复杂的多目标规划,目标函数的维度较高,未知变量较多,用一般的数学方法较难得到最优解。如果加上对问题的约束条件以后,问题可转化为多目标优化的决策问题。

此问题要解决的是,在24小时内使用最少的无人机数量完成指定的侦察任务,并给出无人机最优调度策略。通过分析,应该建立两个目标函数:第一级目标为无人机数量最少,第二级目标为总路径最短。另外,在本次模型当中,可以不考虑敌情、天候、故障等影响因素。由于有多个因素影响目标函数的最优,因此,在求解过程中,可以考虑首先搜索出一个可行解,然后对这个可行解进行调整,使其逐步逼近最优解。通过问题分析,现做以下假设:

1)假定无人机不进行任务载荷更换;

2)假定无人机从源基地出发,经过多个目标点(包括到其他基地补给)为飞行一个架次;

3)假定无人机飞行过程中不考虑敌情、故障、天候、地形等影响因素;

4)忽略对目标侦察的持续时间;

5)忽略无人机的转角问题,无人机以平均速度飞行;

6)假定基地可以同时起飞多架无人机。

2　模型建立与求解

2.1模型建立

定义1:设Xτ,Yτ均为记录元素出现的时间序列集合,则两集合的“代数和”,记为Sτ=Xτ⨁Yτ,且|Sτ|=|Xτ|+|Yτ|。

从问题分析的情况看,所得到的模型解必须满足以下几个条件:

a)对于所有的目标点必须至少侦察一次以上;

b)对于A类目标点要侦察3次,对于B类目标点至少要侦察2次;

c)对于A类目标点连续侦察的间隔时间在4小时至8小时之内,对于B类目标点连续侦察的间隔时间在6小时以上;

d)所有的侦察任务必须在24小时之内完成。

1)建立目标函数

根据问题分析来看,本问题是一个多目标规划问题,在保证任务完成的情况下,第一级目标函数为使用的无人机数量最少[5],即要满足条件a),则:

(1)

其中,Nij为第i类基地的第j种任务载荷的无人机序号集合,i∈J,J={1,2,3},j∈Pi,Pi⊆P,P={1,2,3,4};J中,1表示基地S,2为基地T,3为基地P;P中,1表示任务载荷为Ⅰ型,2为Ⅲ型,3为Ⅳ型,4为Ⅱ型[2]。

根据实际情况和给定条件分析,一架无人机从基地i1直接飞到基地i2(i1≠i2),此次任务为无效,即两基地间的距离为∞,距离矩阵D具体值为[6]

STPA01A02…A06B01…B13C01…C11

其中,di,i=0,dij=dji。

从条件b),可知第二级目标为一天内所有无人机飞行的总路程最短,即

(2)

其中,i∈J,j∈Pi,l∈Nij。

2)目标函数的约束条件

①对于条件a),可作如下约束:

|M|=|V|

②对于条件b),有以下约束:

(3)

通过问题分析,可知C类侦察目标只须侦察一次即可,可以由式(3)满足,可不用计算。

③根据条件c),有如下约束:

(4)

(5)

④根据条件d),如下约束:

问题当中,有一个要满足条件c),要求24小时之内完成侦察任务,则必须满足下式条件,即

综上可见,问题比较复杂,很难用一个具体的方法去求解,因此,必须使用降维的方式进行简化。

2.2模型求解

通过模型的建立和分析,可以看出这是一个复杂的多目标规划问题,为了对这类复杂问题的求解,主要利用于阶梯式反推方式进行求解[7],首先仿真求出一组无人机飞行策略,利用这个飞行策略(初始可行解)推理出目标函数模型所需的计算支撑数据(如:时间间隔数据、经过侦察目标的不同任务载荷的种类数量等),再从模型目标出发,在不影响任务完成与满足模型约束条件下,利用优化搜索仿真算法不断逼近最优解[8]。

1)推算目标函数模型所需的计算支撑数据

(6)

(7)

(8)

根据定义1可以得出[10]:

(9)

其中,⨁VτA为记录时间t的所有无人机一天内经过A类侦察目标点的集合;⨁VτB为记录时间t的所有无人机一天内经过B类侦察目标点的集合;⨁VτC为记录时间t的所有无人机一天内经过C类侦察目标点的集合。

有了以上的条件,可以通过下式来判断第j种任务载荷是否有无人机经过第i序号的A类侦察目标:

(10)

同理可以得出:

(11)

2)模型算法流程

针对这一问题,本文采用基于多Agent优化算法[4,11]进行仿真求解。首先构造初始可行方案,通过逐步逼近最优解的方式得出最终方案。

算法主要思路可以分为以下两过程:

◆Process1:根据约束条件,利用无人机Agent遍历目标点的方法,通过逐步增加无人机Agent数量,判断是否完成任务,得出目标函数的初始可行解,其中目标点分为侦察目标点和基地目标点两类,通过首先遍历侦察目标点、其次遍历基地目标点的方法,优化搜索算法。具体流程(流程图如图1)如下:

Step3:选择目标点,判断本基地出发的无人机能否到达目标Ti,若成立,转入步骤Step4,否则不侦察此目标点,继续执行Step3;

Step4:判别目标的类型,若属于A类目标,转入步骤Step5,否则转入步骤Step8;

Step5:针对A类目标,判断侦察目标i的不同载荷无人机数量,若li<3,转入Step6,否则转入Step3;

Step6:判定是否有同种载荷的无人机侦察目标点,若是,转入Step7,否则转入Step2;

Step7:判定是否符合前后两次不同载荷的无人机经过目标i的时间间隔,若4≤Vtj≤8,转入Step11,否则转入Step3;

Step8:判别是否属于B类目标,如果是,转入Step9,否则转入Step11;

Step9:判定是否有相同类型载荷的无人机侦察目标i,若是,转入Step10,否则记录无人机侦察目标i的时刻;

Step10:判定前后不同载荷的无人机到达目标i的时间间隔,若Vtj≤6时,记录无人机载荷种类数量,li=li+1,记录到达目标i的时刻,否则转入Step3;

Step11:侦察目标点Mi,记录经过目标点i的无人机载荷种类数量li=li+1,记录到达目标i的时刻;

Step12:判定无人机能否继续飞行,若能够继续飞行,转入Step3,否则飞往基地目标点,记录无人机降落的时刻和起飞的时刻tij=tij+5,hij=tij,同时记录无人机维护的次数nj=nj+1;

Step13:判断在基地的无人机是否继续飞往目标点,若成立,转入Step3,否则此架无人机不再飞行,同时判断是否完成任务,若成立,不再增加无人机,得出模型一个初始可行解,否则,转入Step2,继续增加一架无人机。

◆Process2:在初始可行解的基础,通过逐步减少无人机数量,同样利用无人机Agent遍历目标点方法得出目标函数的一个较优解。同时通过依次调整每架无人机的飞行路径上的每个节点,达到重新规划所有无人机路径的目的,从而在较优解基础上逐步逼近最优解,得出的这个结果就可以认为是较好的结果。算法流程(如流程图2)具体如下:

图1　多Agent优化算法流程1

Step1:初始化变量:N;

Step2:从初始可行解中,返回基地时间最晚的第N架无人机开始,减去第N架无人机,N=N-1,判断N>0?如果是,转入Step3,否则转入Step4;

Step3:以最早执行完任务返回基地时间最早的无人机为第一架无人机,根据Process1流程,根据约束条件,遍历搜索所有侦察目标点,判断能否完成任务,如若能,得出一个无人机数量N′和调度策略,同时将N′作为初始可行解,N=N′,继续执行Step2,否则,直接转入Step4;

Step4:加入调整策略,本文的调整策略是依次限制每架无人机上一次飞行路径上的点序列,根据Process1流程,重新遍历搜索侦察目标点,判断能否完成任务,能完成,得出一个无人机数量N′调度策略,同时将N′作为初始可行解,N=N′,继续执行Step2,否则,跳出循环,结束算法,此时,最后一次完成任务得到的无人机数量N和调度策略,就是一个比较优的解。

图2　多Agent优化算法流程2

2.3模型结果及分析

通过仿真计算,得出了多个方案,这里仅选取了其中两个方案。方案表明最少需要6架无人机可以完成侦察任务,具体结果如表1、表2所示,每架飞机的路径如图3、图4所示。通过两个方案的对比,最少无人机数量都是6架,但是方案一总飞行时间小于方案二,表明其飞行路径最短,所以方案一的无人机调度策略优于方案二。

表1　飞行调度策略1

表2　飞行调度策略2

图3　无人机侦察策略1路径

图4　无人机侦察策略2路径

3　结束语

通过对上述问题的分析、建模和求解,本文建立了多无人机协同侦察的优化配置和任务规划模型,通过对多Agent优化搜索仿真算法得到的数据分析,可以看出建立的无人机优化配置和任务规划方案,能够满足问题研究的要求,并且具有一定的实用性和推广性。该模型可扩展性强,可以满足多基地多目标多任务的复杂多目标规划问题的数学描述,基于启发式搜索算法的模型求解与人的思维类似,便于理解实现。

[1]陈济舟.卫星任务规划算法综合评价技术研究[D].长沙：国防科学技术大学,2008.

[2]袁利平,夏洁,陈宗基.多无人机协同路径规划研究综述[J].飞行力学,2009,27(5):1-5.

[3]孙小雷,齐乃明,董程,等.无人机任务分配与航迹规划协同控制方法[J].系统工程与电子技术,2015,27(12):2772-2776.

[4]田菁.多无人机协同侦察任务规划问题建模与优化技术研究[D].长沙:国防科学技术大学,2007:163.

[5]谢涛,陈火旺,康立山.多目标优化的演化算法[J].计算机学报,2003,26(8):997-1003.

[6]安伟刚.多目标优化方法研究及其工程应用[D].西安:西北工业大学,2005:52.

[7]周昊,覃征,邢剑宽.基于多Agent的多无人机协同决策算法仿真平台设计[J].系统仿真学报,2012,24(3):587-593.

[8]夏爽.C4ISR系统下的无人机情报分发策略研究[J].中国科学信息,2012(11):104-106.

[9]柳长安.无人机航路规划方法研究[D].西安:西北工业大学,2003:67.

[10]赵先章,常红星,曾隽芳,等.一种基于粒子群算法的移动机器人路径规划方法[J].计算机应用研究,2007,24 (3):181-186.

[11]杨遵,雷虎民.一种多无人机协同侦察航路规划算法仿真[J].系统仿真学报,2007,19(2):433-436.

Programming Model of UAV Cooperative Reconnaissance Mission Based on Multi-Agent

CHU Zheng1， GUO Fen-lin2， NIAN Song-lei1

(1.Naval Aeronautical Engineering Institue,Yantai 264001；2.China Nanchang Military College,Nanchang 330103， China)

This paper views programming model of UAV cooperative reconnaissance mission.In the conside of reconnaissance time interval and target load requirement,the paper decipts optimization deployment and attemper tactic of the different base’s UAV,and decipts multi-agent based simulation arithmetic of optimization search.The paper realizes deployment and mission programming model of UAV,and figures out the model’s outcome.The paper analyses some shortages of the model and arithmetic,and puts forward the betterment’s directions of the model lastly.

UAV； Multi-Agent； cooperative reconnaissance； mission programming； optimization search

1673-3819(2016)05-0021-07

2016-06-21

2016-08-01

褚政(1978-),男,山东烟台人,硕士,讲师,研究方向为装备管理工程。

郭分林(1979-),男,硕士,副教授。

粘松雷(1982-),男,博士,讲师。

E917;TP18

ADOI:10.3969/j.issn.1673-3819.2016.05.004