刘广瑞， 王庆海， 姚冬艳

(郑州大学 机械工程学院，河南 郑州 450001)

0 引言

多无人机协同任务规划是根据无人机所处的地形和环境因素，为多无人机执行多目标任务制定最佳作战任务规划方案和各无人机作战航迹[1].近年来，国内外学者对多无人机协同任务规划做了大量研究.文献[2]考虑环境威胁、战斗毁伤概率等因素提出了并行GAPSO算法对协同任务规划模型进行了求解，但模型建立未能考虑无人机任务时间，所规划任务序列实用性差.文献[3]和文献[4]在求解无人机任务调度问题上未能考虑环境威胁因素，仅仅是对目标点之间进行任务规划，致使算法所规划序列对无人机生存率很难保证.文献[5]建立了多无人机多目标多任务模型，模型未能考虑无人机燃油限制和任务时间约束，致使执行任务效率较低或根本完成不了任务.文献[6]引入逆向算子改进人工蜂群算法对多无人机单任务进行了任务规划，提高了任务规划效率，但未考虑无人机执行任务前后时间约束，不能够做到各无人机协同执行任务.

考虑到多无人机任务规划的协同性、安全性和任务时效性，针对无人机信息共享、多任务能力等特点提高了任务规划难度，考虑战场威胁分布、目标任务时序、无人机续航时间等因素[7]，建立了多无人机协同执行多目标的多任务规划数学模型.首先采用文献[8]所提算法对各目标点间和各无人机与目标点间最优航迹进行规划.之后考虑战场威胁分布、无人机续航时间等约束，引入时间窗对无人机执行任务起始时间进行约束建立多无人机任务规划模型，提出一种基于改进人工蜂群算法的多无人机协同任务规划方法.仿真实验结果表明，所设计多无人机协同任务规划模型的正确性和有效性得到了很好的验证.

1 多无人机协同任务规划模型

1.1 问题描述

以多无人机执行多目标任务为背景，如图1，无人机执行任务的环境信息已知，由n架无人机执行m个目标的任务，对每个目标依次执行侦查、攻击和评估3项任务，每项任务耗时都为tc.每架无人机对每个目标只能执行一项任务.各目标位置、无人机出发位置和执行每项任务耗时已知.其中U1，U2，…，Un分别表示1#，2#，…，n#无人机；T1，T2，…，Tm分别表示1#，2#，…，m#目标；其中第i个目标被执行完侦查任务、攻击任务和评估任务的结束时间分别为tiS、tiA和tiE.

图1 多无人机协同执行任务示意图Fig.1 A sketch map of multi-UAV cooperative execute tasks

假设无人机在二维空间完成规定任务，通过6m维向量表示n架无人机执行m个目标的任务.无人机根据任务时间约束按照时间先后依次执行3项任务.为规划多无人机任务分配序列，首先需要根据文献[8]所提航迹规划算法规划出各目标点和各无人机与目标点间最优航迹，再根据所提算法规划出最优或较优任务序列.

1.2 约束条件

式(1)约束所有目标的所需任务必须按照任务顺利要求执行；式(2)约束每架无人机只能执行每个目标其中一项任务；式(3)约束所有目标的任务必须全部被执行完毕；无人机由一个位置移动到另一个位置需躲避所有威胁且航迹较优，最大航程须小于一上限；式(4)和(5)分别表示无人机i开始任务时间和结束任务时间.

tiS≤tiA-tc≤tiE-tc;

(1)

(2)

(3)

tsjk=tlj(k-1)+tc+twjk;

(4)

tljk=tsjk+tc,

(5)

式中,xij为第i个目标被第j个无人机执行任务则为1，否则为0；tsjk和tljk分别为第j个目标第k项任务开始和结束时间;twjk为执行第j个目标第k项任务的等待时间[8].

1.3 目标函数建立

假设无人机飞行速度为v，在已知无人机和目标位置的前提下，无人机以最优或较优时间完成所有任务的任务分配计划.目标函数为：

F=max(S/v),

(6)

其中S=[S1,S2,…,Si,…,Sn]，Si为第i个无人机完成分配的任务飞行航迹长度.

2 人工蜂群算法的改进

2.1 初始化蜜源

将一个任务序列集合X=(x1,x2, …,x6m)视作一个蜜源，初始化蜜源需满足约束条件，其中奇数位为无人机序号，偶数位为前一位奇数位对应的无人机所执行任务的目标序号.如图2，表示的是3架无人机执行2个目标任务的任务序列编码.图中表示的任务分配计划为：3架无人机同时出发，U1对T2执行侦察任务；U2对T1执行侦察任务；等待无人机执行完T2的侦察任务后，U3对T2执行攻击任务；等待U2对T1执行完侦察任务后，U1对T1执行攻击任务；等待U3对T2执行完攻击任务后，U2对T2执行评估任务；等待U1对T1执行完攻击任务后，U3对T1执行评估任务[9].

图2 任务序列编码方式
Fig.2 Encoding of a sequence of tasks

2.2 选择机制

传统ABC算法是通过目标函数值决定的蜜源适应度比例来判定所要跟随的采蜜蜂，该方法虽然提高了算法收敛速度，但是容易导致蜂群向适应度值较高的蜜源聚拢，使算法极易陷入局部最优.采用动态评价选择策略[10]取代传统选择机制，通过采蜜蜂动态变化状况决定被跟随的概率，极大地提高了蜂群多样性，避免了算法陷入局部最优.

动态评价指标为w1(i)和w2(i),蜜源i被优化时w2(i)按式(8)计算，w1(i)为0；蜜源i未被优化时w1(i)按式(7)计算，w2(i)为0.动态评价函数F(i)为式(9).

(7)

(8)

(9)

式中：w1(i) 为蜜源i被优化连续不变的次数;w2(i)为蜜源i被优化连续变化次数;Limit为算法的限制参数.

通过动态评价函数计算单个蜜源得分，采蜜蜂被选择概率Pi的计算公式为(10)，通过Pi计算累计第i个采蜜蜂被选择概率，将生成的0～1的随机数与各累计选择概率匹配，决定观察蜂选择哪个采蜜蜂.

(10)

2.3 邻域搜索

由于所优化问题为离散问题，对任务序列X=(x1,x2, …,x6m)进行邻域搜索时，由于任务序列奇数位置和偶数位置表示不同的含义，需进行不同的邻域搜索策略.设邻域搜索位为I，若I为奇数，随机选取没有在I位对应的目标执行过任务的无人机替代I位对应的无人机；若I为偶数，随机选取I位对应的无人机未执行过的其他偶数位对应的目标位进行位置交换.之后采取文献[6]的方法引入逆向算子的方式对任务序列进行变异.邻域搜索完成后对任务序列进行可行性判定，该方式提高了邻域搜索解的可行性，提高了算法收敛速度.

2.4 判定准则

在航迹寻优过程中，由于寻优域较宽，传统ABC算法全局寻优性能劣化，寻优收敛速度前快后慢.为提高算法收敛速度和精度，引入Metropolis准则[11]对新旧蜜源进行进一步判定.当前航迹向新航迹转化概率表达如式(11).通过改进，算法寻优初期对较差航迹具有较高接受概率，使算法不易陷入局部最优；算法寻优后期对较差航迹具有较小接受概率，蜜蜂可在较优航迹附近进行细致搜索.

(11)

式中:o代表旧航迹；n代表新航迹；下降函数T(t)=T(t-1)·σ，退火系数σ一般取0.8.

2.5 算法流程图

基于改进人工蜂群算法(IABC)的多无人机协同任务规划算法流程图如图3所示，其中q为当前迭代次数，Lmax为最大迭代次数.

图3 IABC算法流程图Fig.3 The flow diagram of IABC algorithm

3 算例分析

在Inter(R) Core(TM) i3-2130 CPU，3.4 Ghz，Matlab R2014a环境下进行仿真分析，假设在1 000 km×1 000 km的战场环境内，5架无人机对10个目标执行任务，无人机参数和威胁参数设置如表1和表2所示.目标T1，T2，…，T10位置分别为(100,300)，(310,240)，(210,700)，(620,610)，(250,500)，(620,350)，(450,470)，(600,150)，(820,350)，(420,750).人工蜂群算法参数：蜜蜂总数为NP=60，采蜜蜂总数为NP/2，Limit=10，Lmax=300.

表1 无人机参数设置

表2 威胁参数设置

采用ABC和IABC算法分别进行了20次仿真实验，通过IABC算法仿真得出的最优任务分配计划对应的其中一架无人机的航迹见图4.通过20次试验仿真数据分析得出两种算法的目标函数最优值收敛曲线对比图见图5，目标函数均值收敛曲线对比图见图6.其中ABC、ROABC和IABC分别代表基本人工蜂群算法、逆向算子人工蜂群算法和改进人工蜂群算法多无人机多任务规划仿真实验目标函数值.图7为通过IABC算法仿真得出的最优任务分配计划的无人机任务执行时间表.表3为对应的无人机任务分配表，其中C、A和E分别对应无人机执行的侦查、攻击和评估任务，例如，1C对应无人机对目标1执行侦察任务.

图4 无人机航迹图Fig.4 Flight path of UAV

图5 目标函数最优值收敛曲线对比图Fig.5 Comparison convergent curve of target function′s optimal value

图6 目标函数均值收敛曲线对比图Fig.6 Comparison convergent curve of target function′s mean value

图7 UAV任务执行时刻表Fig.7 UAV’s assignment schedule

UAV编号航迹长度/km任务耗时/h任务分配计划U115791510903C→10C→4A→2A→1A→5EU215541611271C→5C→7A→4E→6A→8E→9EU315681310844C→7C→2C→8A→9A→6EU417417211273A→10A→5A→1E→2EU514809310408C→9C→6C→7E→3E→10E

通过20次仿真实验数据分析，随着进化代数的增加，目标函数值不断降低，种群不断向更优的方向进化，两种改进算法较传统算法不但收敛的快，而且收敛精度也高很多.IABC算法、ROABC算法和ABC算法耗时均值分别为24.75 s、25.04 s和24.03 s，最优收敛值分别为11.72 h、12.16 h和14.33 h.在耗时相当的情况下，IABC算法最优收敛值比ABC算法低16.5%，比ROABC算法收敛值低3.6%，种群均值更是优于ABC算法.根据图5，随着进化代数增加，所提算法优化种群目标函数均值较另两种算法更低，可知，所提算法比另外两种算法种群更优.表3给出的无人机任务分配表就是所提IABC算法优化的全局最优解.

4 结论

针对无人机信息共享、多任务能力等特点提高了任务规划难度，考虑战场威胁分布、目标任务时序、无人机续航时间等因素，建立了多无人机协同执行多目标的多任务规划数学模型.采用改进人工蜂群算法对该模型求解通过仿真结果表明：

(1) 引入时间窗对无人机执行任务起始时间进行约束建立多无人机任务规划模型，增强了多无人机任务规划模型实用性；

(2) 通过引入动态评价选择策略、Metropolis 准则等方式提出改进人工蜂群算法对该模型求解，仿真结果表明了该方法的有效性；

(3) 算法优化过程中很难取得一个全局最优解，只能优化得到一个相对较优的解，每次优化结果很难保证完全一致，算法稳定性还有待进一步提高.

参考文献：

[1] 沈林成,陈璟,王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35(3): 593-606.

[2] 邓道靖,马云红,龚洁,等. 基于并行GAPSO算法的多无人机协同任务规划[J]. 电光与控制, 2014, 23(11): 1-6.

[3] 杜继永,张凤鸣,杨骥,等. 多UCAV协同任务分配模型及粒子群算法求解[J]. 控制与决策, 2012, 27(11): 1751-1755.

[4] LIN L, SUN Q B, WANG S G, et al. Research on PSO based multiple UAVs real-time task assignment[C]//2013 25th Chinese Control and Decision Conference (CCDC). Guiyang, China:IEEE, 2013: 1530-1536.

[5] GENG L, ZHANG Y, WANG J J, et al. Cooperative task planning for multiple autonomous UAVs with graph representation and genetic algorithm[C]//2013 10th IEEE International Conference on Control and Automation (ICCA). Hangzhou, China:IEEE, 2013: 394-399.

[6] WANG Z T, ZHENG M F, GUO J S,et al.Uncertain UAV ISR mission planning problem with multiple correlated objectives[J]. Journal of intelligent & fuzzy systems, 2017,32(1):321-335.

[7] 张晓敏,马培蓓,纪军,等. 具有时间约束的多无人机协同航迹控制研究[J]. 电光与控制, 2015,22(9): 42-45.

[8] LI B, GONG L G, YANG W L. An improved artificial bee colony algorithm based on balance-evolution strategy for unmanned combat aerial vehicle path planning[J]. Scientific world journal, 2014, 2014(1): 95-104.

[9] 马纯超,尹栋,朱华勇. 网络化战场环境下多无人机调度问题[J]. 火力与指挥控制,2015,40(10):31-36.

[10] 徐向平,鲁海燕,程毕芸. 基于动态评价选择策略的改进人工蜂群算法[J]. 计算机应用, 2015, 35(7): 1969-1974.

[11] MIAO H, TIAN Y C. Dynamic robot path planning using an enhanced simulated annealing approach[J]. Applied mathematics and computation, 2013, 222: 420-437.