多无人机协同探测时间最小化问题的研究

谢 军，耿家利，张 萍，裘哲勇

(1.杭州电子科技大学生命信息与仪器工程学院，浙江 杭州 310018； 2.杭州电子科技大学计算机学院，浙江 杭州 310018；3.杭州电子科技大学理学院，浙江 杭州 310018)

多无人机协同探测时间最小化问题的研究

谢 军1，耿家利2，张 萍2，裘哲勇3

(1.杭州电子科技大学生命信息与仪器工程学院，浙江 杭州 310018； 2.杭州电子科技大学计算机学院，浙江 杭州 310018；3.杭州电子科技大学理学院，浙江 杭州 310018)

对无人机协同任务规划中的航线规划与轨迹优化问题进行了研究.以攻击方无人机在雷达探测区域的总滞留时间为优化目标，建立了数学模型，提出了基于多旅行商问题MTSP的分层混合遗传算法，通过该算法产生初始航迹.在初始航迹的基础上，进一步做航线平滑和轨迹优化处理.最后通过实例，比较了初始解和最终解，验证了算法的有效性.

无人机；航线规划；轨迹优化；多旅行商问题；混合遗传算法

0 引 言

人工智能时代，多无人机协同任务已经从军事领域扩展到民生领域，逐渐成为科技创新的热点.多无人机协同任务规划从功能上可大致划分为系统资源分配、任务分配、航行规划、轨迹优化、武器投放规划等[1].目前，国内外对多无人机协同展开了广泛研究.文献[2]提出了一种基于PSO的DCAA算法，对任务规划问题中的任务分配问题和航迹规划问题进行研究.文献[3]将敌方雷达区作为约束条件，建立了多架无人机对多个目标执行侦察任务的规划模型.文献[4]提出了几何增强学习的方法，用于解决无人机的路径规划问题.

本文研究无人机在侦察防御方的目标群的过程中，如何规划无人机航线使得无人机被防御方雷达探测的总时间最小.此问题和多旅行商问题(Multiple Travelling salesman problem, MTSP)[5]相关，但目标函数不同.旅行商问题一般优化目标是总代价最小，而此问题是求解总路程中被雷达探测的路程最小.在实际战场中，无人机在执行侦察任务时被防御方的雷达探测之后，防御方的目标群就会对空警戒并发射导弹炸毁无人机，滞留时间越长其被摧毁的可能性越大，具有一定的实际意义.

1 防御方雷达探测无人机时间最小化问题建模

1.1 背景介绍与问题描述

假设攻击方无人机基地集合为O，无人机可通过装载成像传感器对防御方的目标进行侦察.防御方目标群为集合V，每个目标群均配有雷达站且包含数量不等的地面目标，雷达站对攻击方无人机的有效探测区域是半径为R的圆.假设已知所有目标点、无人机基地、雷达的坐标，攻击方要派遣无人机侦察防御方所有目标点，如何设计无人机的飞行航线可使无人机被防御方雷达探测范围之内的时间最小？

为了方便模型的阐述与研究，首先对战场的地形进行阐述和简化，战场简化的示意图如图1所示.其中O1～O4为攻击方基地，V01～V10为防御方目标群，十字箭头表示雷达位置，其外围的圆圈为雷达探测范围，坐标轴单位为km.

图1 战场简化示意图

1.2 最小化问题建模

由前文背景介绍和问题描述知，无人机要从基地出发，选择尽可能短的路径完成侦察任务，完成任务后回到出发点，而且在侦察过程中还要尽可能的避开敌方的雷达.此时无人机的航迹规划问题就是确定一条通过所有航路点，使得敌方雷达侦测时间和最短的几条闭合路线，每一条闭合路线上的目标点集合都是一架无人机所需要完成的侦测任务，这与多旅行商问题的描述是一致的，因此无人机航迹规划问题可以转化为MTSP[6].无人机航迹线路总规划如图2所示.

图2 航迹线路总规划

无人机侦察滞留防御方的时间最小化问题是一个目标分配问题，可以转化为一个整数规划问题.假设整个飞行航迹网络构成一张有向图：G(O∪V,w),其中O={O1,O2,O3,O4}表示攻击方4个无人机的出发基地，V={V1,V2…,V10}表示防御方10个目标群，ωij表示从第i点到第j点的距离.引入决策变量

(1)

可以建立基于多旅行商问题的数学规划模型：

(2)

(3)

(4)

(5)

(6)

(7)

式(1)为决策变量；式(2)为目标函数，即求得最小化的总航行路程；式(3)为无人机飞行约束，即表示所有的无人机从基地出发完成侦察任务后回到出发基地，因有4个攻击方无人机基地，故最后形成的子图数量为4；式(4)表示无人机从目标群i出发下一次只侦察一个目标群j；式(5)表示侦察当前目标群j的无人机只来自目标群i中的一个；式(4)和式(5)结合表明每个目标群只被侦察一次；式(6)保证单个目标点不形成子图；式(7)中的i和j分别为攻击方无人机基地集合O中不同的基地，该式表示攻击方无人机不可从攻击方基地i飞到基地j.

进一步将研究的航迹规划问题转化2个子问题：1)如何划分子图；2)如何确定每个子图中的无人机的飞行路径使得总的路程最小。

图3 混合遗传算法分组示意图

为了求解多无人机航程规划问题，下面设计一种分层混合遗传算法，该混合遗传算法的结构示意图如图3所示.第一层：利用启发式遗传算法将这个MTSP问题分解为m个顶点不相交的TSP问题，在该层主要依据模型约束条件将有向图中所有的目标点分成m个子图.第二层：采用遗传算法对m个TSP问题进行求解，分别求得每个子图的最小路径.

2 混合遗传算法初步求解与航迹优化

无人机滞留防御方雷达探测范围之内的时间最小化问题和多旅行商问题相关，但目标函数不同.通过混合遗传算法[7]得到初始航迹，然后分析初始航迹进而对初始航迹进行调整和优化.

2.1 混合遗传算法的程序流程图

遗传算法以自然选择和遗传理论为基础，本模型中将无人机侦察滞留防御方雷达探测时间最小化问题模拟成一个生物进化的过程.本文采用的混合遗传算法的流程图如图4所示.设计的算法终止的条件是：种群的平均估计值不小于1.2并且平均适应值增量不大于0.04并持续20次，变异概率提高一倍，再次在种群平均估计值不小于1.2并且平均适应值不大于0.04并持续20次.

图4 混合遗传算法的程序流程图

2.2 航迹优化与结果分析

具体坐标信息详见2016年全国研究生数学建模竞赛A题中附件1和附件4，通过matlab编程实现基于MTSP的混合遗传算法，混合遗传算法迭代的次数和雷达探测的无人机飞行总路程关系如图5所示.图5中，x轴表示算法的迭代次数，y轴表示雷达探测的无人机飞行的总路程，算法迭代的总次数在1 700次左右趋于收敛，探测的总路径为1 788.8 km.

最终实现4架无人机对10个目标集群的64个目标进行侦察，应用基于多旅行商的混合遗传算法求得初始航迹图如图6所示，其中4条闭合折线是无人机的初始航迹.分析初始航迹可知，无人机在完成最后侦察之后以直线飞回出发基地，返程中可能多次重新进入雷达探测范围，为了求解无人机被雷达探测路程最小，因此需要对初始航迹进行调整来实现返程中躲避雷达的目的.

图5 算法迭代次数和雷达探测无人机飞行路程关系图

图6 混合遗传算法求得的初始航迹图

本文在混合遗传算法的基础上，为保证侦察无人机滞留防御方雷达有效探测范围内的时间最短，采用以下约束条件来对初始航迹进行优化和调整：

1)所有无人机完成侦察任务后返回基地的总路径L尽可能小：

(8)

其中，pi为第i架无人机，Li为第i架无人机的路程.

2)所有无人机完成侦察任务后再次进入另一防御方雷达探测范围的次数总和C为0：

(9)

其中，pi为第i架无人机，Ci为第i架无人机再次进入另一防御方雷达探测范围的次数.

图7 平滑和优化后的航迹图

通过上面2个约束条件，对无人机的侦察路径的航迹进行优化调整，优化后的无人机的航迹图如图7所示，无人机在最后一次完成侦察任务后不是直线飞回对应的出发基地，而是在返程中躲避了雷达，避免二次进入雷达探测范围之内.初始航迹得到的初始解和调整航迹后的最终解的对比结果如表1所示，从表1得知，经过航迹优化调整后雷达探测无人机的飞行总路程由1 788.8 km变为1 463.2 km，雷达探测无人机的飞行总时间由8.94 h变为7.33 h.可知航迹调整后，雷达探测无人机飞行的路程和时间都相应减小，说明航迹优化的有效性.

表1 初始解和最终解的对比结果

3 结束语

本文针对雷达探测攻击方无人机时间最小化问题，提出了一种基于多旅行商问题的分层混合遗传算法，通过遗传算法获得初始航迹后，又通过两个约束条件对初始航迹进行了二次优化和调整处理，从计算结果可知，该算法可以显著降低无人机被雷达探测的时间.相比于传统的无人机协同问题，本模型针对雷达探测范围进行了航迹优化处理.研究结果对于实际战场中降低无人机被摧毁的概率具有很强参考意义.后续还可以继续分析如何有效地提高算法的效率，以增强规划的时效性.

[1] 毛红保，田松，晁爱农.无人机任务规划[M]．北京:国防工业出版社，2015:89-103.

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

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

[4] ZHANG B， MAO Z，LIU W，et al. Geometric reinforcement learning for path planning of UAVs[J].Journal of Intelligent & Robotic Systems,2015，77(2):391-409.

[5] 旷东林.混合遗传算法在mTSP中的应用[D].长沙:中南大学，2009.

[6] GU X, CAO X, XIE Y, et al. Cooperative trajectory planning for multi-UCAV using multiple traveling salesman problem[C]//Chinese Control Conference,2016:2722-2727.

[7] AGARWAL A, LIM M H, ER M J, et al. ACO for a new TSP in region coverage[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE Xplore,2005:1717-1722.

StudyontheProblemofMinimizingtheCooperativeDetectionTimeofMulti-UAVs

XIE Jun1, GENG Jiali2, ZHANG Ping2, QIU Zheyong3

(1.CollegeofLifeInformationScienceandInstrumentEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang310018,China;3.SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

The problem of route planning and trajectory optimization in UAV cooperative task planning is studied. Based on the multi-traveling salesman problem(MTSP), a hierarchical hybrid genetic algorithm is proposed to generate the initial flight trajectory by using the total residence time of the attacking unmanned aerial vehicle(UAV) in radar detection area as the optimization goal. The initial trajectory is generated by this algorithm, and the route smoothing and trajectory optimization are further done considering the UAV survival rate and trajectory rationality. Finally, the effectiveness of the algorithm is verified by comparing the initial solution and the final solution.

unmanned aerial vehicle; path planning; trajectory optimization; multi-traveling salesman problem; hybrid genetic algorithm

10.13954/j.cnki.hdu.2017.06.018

2016-12-02

谢军(1993-)，男，山东临沂人，硕士研究生，算法设计.通信作者：裘哲勇教授，E-mail:qzy@hdu.edu.cn.

V279

A

1001-9146(2017)06-0095-05