基于进化算法的多无人机协同航路规划

李子杰，刘湘伟

（电子工程学院，合肥230037）

基于进化算法的多无人机协同航路规划

李子杰，刘湘伟

（电子工程学院，合肥230037）

以突防航路时域协同指数、空域协同指数、突防时长指数和受威胁指数为规划目标，以最小直线航路段长度、可飞空域、续航能力和进入任务航路方向为约束，构建了多无人机协同突防航路规划模型。结合模型特点，利用合作型协同进化遗传算法对该模型进行求解。

无人机，协同航路规划，合作型协同进化遗传算法

0 引言

多无人机协同是未来无人机运用的主要样式，多无人机协同航路规划在很大程度上决定了多无人机协同效能的发挥，是当下无人机航路规划研究的重点。多无人机协同航路规划主要是时间和空间上的协同［1］。现有关于多无人机协同航路规划的研究，侧重于首先对多架无人机单独进行航路规划，在较优种群中以编队预计到达目标时间ETA（Estimated Team Arrival Time）作为协同变量对多架无人机飞行航路组合评价［2-4］，寻求满足协同条件的飞行航路组合。本文通过引入突防航路时域协同指数、突防航路空域协同指数，对遂行干扰任务的多无人机协同突防航路正面建模，并根据模型特点，利用合作型协同进化遗传算法对模型进行求解。

1 协同航路分析

遂行干扰任务的无人机飞行航路主要包括突防航路和任务航路，如下页图1所示。发射阵地YFront1，j发射两组无人机，沿突防航路AssRoute1，j，1和Ass-Route1，j，2，进入任务航路MisRoute1和MisRoute2；发射阵地YFronti，j发射两组无人机，分别沿突防航路Ass-Route1，j，2和AssRoutei，j，r，进入任务航路MisRoute2和MisRouter；发射阵地YFrontNumFR，j发射两组无人机，沿突防航路AssRouteNumFR，j，r和AssRouteNumFR，j，NumR，进入任务航路MisRouter和MisRouteNumR。

图1 无人机协同航路示意图

突防航路规划同时受发射阵地中无人机的发射时间长度限制和到达任务航路时间区间限制。多架无人机应该在确定的时间区间内到达任务航路；由同一发射阵地起飞的多架无人机发射持续时间应控制在一定时间长度内，以避免来自敌方火力的报复性打击。

本文在已知无人机任务航路基础上开展无人机协同突防航路规划研究，多无人机协同突防航路可表示为：

2 协同突防航路规划建模

2.1 协同突防航路规划目标函数

多无人机协同突防航路规划主要考虑4个规划目标函数：突防航路时域协同指数、突防航路空域协同指数、受威胁指数、突防时长指数。

2.1.1 突防航路时域协同指数

在同一条任务航路上遂行压制干扰任务的无人机可由同一发射阵地发射升空，也可由不同发射阵地发射升空，这些来自不同发射阵地的无人机最终需要在任务航路上等间距飞行。为了防止不必要的冲突，有必要对来自不同发射阵地的不同无人机到达任务航路时间窗进行明确。在确定各无人机到达任务航路时间窗之前，首先应该确定不同无人机到达任务航路的先后顺序。这一顺序可由指挥员根据任务分配方案予以指定。来自不同发射阵地的无人机相继到达任务航路，调整无人机间距，以满足对雷达干扰要求。

图2 无人机到达任务航路时间窗分解示意图

如图2所示，无人机任务航路长度为Length（MisRoute），对应的任务航路周期为Tstd，无人机分别来自NFr个发射阵地，每个发射阵地NumUn架无人机。来自发射阵地YFrontn的无人机到达任务航路的时间窗宽度为：

如图1所示，设发射阵地YFront1，j起飞的两批无人机到达任务航路的时间区间分别为和，突防航路耗时分别为△t1，j，1和△t2，j，2，与之对应的发射时间窗为：

如图3所示，一个发射阵地发射两个批次无人机至任务航路MisRoute1和MisRoute2。假设航路相同的多架无人机被连续发射，只需计算第1架无人机提前到达的时间或最后一架无人机推迟到达的时间即可。本文以无人机编队推迟时间（提前时间）之和的最小值△tmin来评价是否协同。

图3 无人机发射时长计算示意图

将起始于发射阵地Fronti的突防航路时域协同指数表述为：

将所有发射阵地对应突防航路时域协同指数累加，即可得到多无人机的时域协同指数：

2.1.2 突防航路空域协同指数

航路如果存在交叉，则有可能发生碰撞，交叉部分越多，无人机发生碰撞的概率就越大。突防航路空域协同指数是对飞行航路在空间发生交叉情况的度量。对于突防航路AssRoutei，j，r，其空域协同指数就是其航程点数，减去与其他突防航路交叉点后的数量，占自己航程点总数的比值：

其中，NumNi，j，r为突防航路AssRoutei，j，r航程点数；NumJCi，j，r为AssRoutei，j，r与其他航路发生交叉的航程点数。

多无人机协同突防航路空域协同指数可表述为：

2.1.3 突防时长指数

突防航路是无人机飞行航路的一部分，为了减少燃料消耗，将更多的滞空时间用于遂行干扰任务，引入突防时长指数，用于引导无人机选择耗时较短的突防航路。突防时长指数最短指标可表述为：

其中，length（AssRoutei，j，r）为突防航路AssRoutei，j，r长度；vi，j，r为航路AssRoutei，j，r上相应无人机飞行速度最小值（m/s）。

2.1.4 受威胁指数

受威胁指数与无人机自身性能相关，在突防航路AssRoutei，j，r上的无人机受威胁程度thi，j，r为被发现概率和被毁伤概率之和。无人机受威胁指数可表述为：

2.2 协同突防航路规划约束

协同支援侦察突防航路规划约束包括最小直线航路段长度约束、可飞空域约束、续航能力约束和进入任务航路方向约束。其中，最小直线航路段长度约束与一般无人机相同；进入任务航路方向约束是为了保证无人机突防航路末端时，无需调整，直接进入任务航路直线段而提出的。在具体操作中，在任务航路直线段延长线上取一点作为突防航路航程点。下面主要介绍可飞空域约束和续航能力约束。

2.2.1 可飞空域约束

无人机飞行空域内包括不可穿越威胁、雷达探测威胁和火力毁伤威胁。不可穿越威胁包括两类：第1类是地形障碍、禁飞区、气象威胁、电子干扰威胁区等；第2类是其他飞行器已经占据且不可共用的空域，如空中进攻编队所占据空域等。在本文的讨论中，将第1类不可穿越威胁区等效为一定半径的圆形区域，将第2类不可穿越威胁区等效为该区域的最小外接多边形区域。

突防航路以保证无人机按时、安全到达任务区域为目标，其可飞空域应尽量避免防空威胁。但是，在某些特殊情况下，仍然可以一定被毁伤概率进入防空火力威胁区，防空火力威胁区一般等效为一定半径的圆形区域。设可飞空域为JoiAss Deploy，可飞空域约束可表述为：

2.2.2 续航能力约束

已知无人机任务航路和干扰任务持续时间要求，无人机续航能力约束可表述为：

2.3 协同突防航路规划模型

前述规划目标中存在取大和取小两种类型，为表述方便，本文统一对4个规划目标分量取小，首先对规划目标1和规划目标2做如下处理：

综合前述关于无人机协同突防航路规划目标函数和约束的分析，建立其协同突防航路规划模型如下所示：

3 基于合作型协同进化遗传算法的协同航路规划模型求解

3.1 算法结构

如图4所示为求解无人机协同航路规划模型的合作型协同进化遗传算法结构。随机生成多条飞行航路，构成无人机飞行航路子种群，即图4中的“无人机子种群1”、“无人机子种群2”……。无人机子种群个数取决于遂行任务的无人机组数，当仅有一组无人机时，合作型协同进化遗传算法退化为普通遗传算法。

图4 合作型协同进化遗传算法结构

合作型协同进化遗传算法不同于普通遗传算法，主要体现在种群构成和适应度计算。合作型协同进化遗传算法将长的染色体编码分组为多个短的染色体编码，即将决策变量分组，每一个短编码各自形成一个子种群，子种群独立进化。在个体评价时，由于一个子种群的基因只代表航路规划决策变量的一部分，需要将一个子种群的基因与其他子种群的基因结合，形成一个完整的航路规划解。如图4所示，在对无人机子种群1内的个体进行评价时，首先分别从无人机子种群2、无人机子种群3和无人机子种群4中选择一部分个体作为代表个体，与子种群1中个体结合，根据目标函数，对结合后的个体进行评价，评价结果作为子种群1内个体的适应度值；尔后依次计算无人机子种群2、3、 4内个体适应度值，并据此作为子种群遗传操作的依据［5］。由于存在多个目标函数，在求解个体适应度值时要综合考虑个体的多个目标函数。构建效用函数，将多目标函数转化为单目标函数，进而求出个体适应度值。

3.2 算法流程

求解多无人机协同航路规划模型合作型协同进化遗传算法流程如图5所示。

图5 无人机协同航路规划的合作型协同进化遗传算法流程

求解无人机协同航路规划模型的合作型协同进化遗传算法步骤如下［5］：

步骤1：初始化无人机子种群；

步骤2：从其他无人机子种群中选择代表个体，与待评价无人机子种群个体构成合作团队，对无人机个体进行评价；

步骤3：对无人机子种群进行选择、交叉和变异等进化操作，生成新的无人机子种群；

步骤4：判断算法终止条件是否满足，若满足，终止种群进化，将所有无人机飞行航路综合，输出优化结果；否则，转步骤2。

3.3 仿真分析

无人机协同突防航路规划，在已知任务分配方案和任务航路基础上展开［6］。无人机突防航路的起点是发射阵地，终点是任务航路上的任务转换点。设无人机发射阵地和任务转换点如表1所示。

初始化5个无人机航路子种群、每个子种群个体数量50，迭代代数50，交叉概率0.75，变异概率0.1，仿真结果如图6、图7所示：

图6 第30代和第50代最优个体

如图6（b）所示，5条无人机突防航路均能绕开敌地面防空火力威胁，到达指定终点。表2所示为第50代种群中最优的5条无人机协同突防航路航程点坐标。

表2 第50代最优航路航程点坐标

图7所示为无人机协同突防航路种群各目标函数值随迭代代数的变化关系。其中，突防航路时域协同指数平均值趋近于4的水平，突防航路空域协同指数呈上升趋势，且保持在很高水平，反映出无人机突防航路表现出良好的时域协同和空域协同关系。受威胁指数随迭代代数逐渐降低。突防时长指数通过一定代数的起伏，最后收敛于一个稳定值。

图7 目标函数值与迭代代数关系

4 结束语

共同遂行压制干扰任务的多架无人机突防航路在时域和空域上存在协同关系。本文从这种时域和空域上的协同关系入手，构建了多无人机协同突防航路规划模型。结合模型特点，利用合作型协同进化遗传算法对该模型进行求解，得到的多无人机突防航路表现出良好的时域、空域协同效果。

［1］黄长强，翁兴伟，王勇，等.多无人机协同作战技术［M］.北京：国防工业出版社，2012.

［2］朱收涛，曹林平，翁兴伟，等.采用改进粒子群算法的无人机协同航迹规划［J］.电光与控制，2012，19（12）：29-33.

［3］杨力.无人机航路规划技术研究［D］.南京：南京航空航天大学，2009.

［4］辛亭.多无人机协同作战关键技术研究［D］.南京：南京航空航天，2009.

［5］巩敦卫，孙晓燕.协同进化遗传算法理论及应用［M］.北京：科学出版社，2009.

［6］李少华，魏海光，周成平，等.一种海上无人飞行器的快速航迹规划方法［J］.四川兵工学报，2011，32（12）：73-76.

Cooperative Path Planning of Multi-UAV Based on Evolutionary Algorithm

LI Zi-jie,LIU Xiang-wei
（Electronic Engineering Institute,Hefei 230037，China）

Aiming at maximizing penetration path time synergy index and penetration path airspace synergy index,minimizing penetration time length index and intimidate index,restricted by the minimum length of straight path,flyable space,endurance and intro-mission route direction,the penetration path planning model of Multiple Unmanned Serial Vehicle（Multi-UAV）is constructed. Combining its characteristic,the model is solved by use of Cooperative Co-evolutionary Genetic Algorithms（CCGA）

Unmanned AerialVehicle（UAV），cooperativepath planning，CooperativeCo-evolutionary GeneticAlgorithms（CCGA）

TN974

A

1002-0640（2015）02-0085-05

2013-12-21

2014-01-23

李子杰（1986-），男，湖南常德人，博士研究生。研究方向：信息对抗装备作战运用与运筹分析。