基于威胁建模的多航迹规划算法*

杨海燕，张帅文，韩 城

（1.空军工程大学空管领航学院，西安 710051；2.空军工程大学研究生院，西安 710051）

0 引言

航迹规划从20世纪50年代以来成为国际上的研究热点，它是指在综合考虑各种因素之后，为飞行器选取一条从起点到终点的运动轨迹，使之满足约束条件并圆满完成任务[1]。但在战场中，态势瞬息万变，各种障碍、威胁实时变化，预先制定好的航迹在飞行时可能不再适用。一个解决办法便是飞行前多航迹的规划，提前制定出多条备选航迹使飞行器在遇到突发威胁时能保障其生存率和任务完成率。因此，研究飞行器的多航迹规划具有重要意义和价值。

与单航迹规划相比，多航迹规划问题的难点主要体现在：规划空间中威胁区评估和航迹建模、多航迹的解算。目前对于威胁建模，文献[2]使用等效数字地形的方法模拟威胁，简化了航迹规划模型，但威胁区模型简单。文献[3]将飞行空间网格化，求解飞机在特定方向上飞行时的最优代价函数，以此作为航迹，减少了约束条件的限制，但适用范围有限。多航迹规划的求解算法有进化算法[4-5]、启发式算法等。文献[4]将K均值聚类算法结合遗传算法，每隔若干代聚类出航迹子群，子群再进化出最优航迹。它避免了搜索空间以及各种假设的限制，但对于K值的确定尚无较好解决办法。文献[5]是多峰值代价函数优化问题，利用聚类排挤小生境遗传算法生成多航迹。其中排挤机制良好地实现了种群多样性，但小生境技术中参数难以设定。

本文以飞行器的多航迹规划为背景，以规划空间中威胁区的评估为基础构建多航迹规划模型，引入排挤机制（exclusion mechanism）策略，提出了K-均值聚类（K-means clustering）与粒子群算法（PSO）相结合的算法，简称为EKM-PSO。K-均值聚类对航迹种群进行了分类，排挤机制解决了K的取值问题，克服了人工确定种群数量K时的主观性，最后使用基于威胁适应度函数的粒子群算法生成多条航迹，提高了解的精度和计算效率，满足战场备选航迹的实际需要。

1 多航迹规划问题建模

1.1 规划空间中威胁评估模型

规划空间是指进行航迹规划时的目标区域[6]，本文中代表给定的任务空间，选用三维直角坐标系对任务空间进行建模，将规划空间中任意一点表示为（x，y，z）。多航迹规划建模主要解决飞行器在规划空间中如何避开各种已知或突发威胁区域，到达指定的位置。

1.1.1 障碍物模型建立

考虑到飞机在实际飞行的过程中，遇到最大的地形威胁是山峰，所以对障碍物的建模参考了有关山峰的数学表达式。由文献[7]可知，山峰模型的数学近似表达式为：

其中，hi表示第i个山峰的高度；（xi，yi）是第i个山峰的中心坐标；ki是山峰的梯度；（x，y）是山峰上一点在水平面的投影坐标；z（x，y）是山峰上任意一点的高度。通过实验发现将山峰梯度设为18较合理，假设两个山峰的地理中心坐标分别为（0，0，0）和（50，50，0），高度分别为 40 和 50，则山峰的三维模型如图1所示。

图1 山峰的三维模型图

飞机在遇到山峰时应提前转弯或爬升，根据文献[7]，飞机在当前坐标位置（x，y，z）时坠毁概率为：

以此作为障碍物威胁的代价函数。其中，Rm是山峰i与飞机高度相同的横截面的半径，表达式为。R是飞机与山峰i的同高度横截面圆心点之间的距离，表达式为。由此可知，当飞机与山峰的距离大于20 m时，飞机安全。当飞机与山峰的距离小于5 m时，飞机坠毁。

1.1.2 雷达探测区域模型建立

对于雷达的作用范围，用以下函数[8]在地形图中进行模拟：

其中，z（x，y）是雷达探测范围的高程，（xi，yi，0）是雷达i的位置坐标，Kh为雷达探测性能的系数，Rmax是敌方雷达的最大探测距离。假设敌方雷达坐标（-50，-50，0），则探测范围在地形中如下页图2所示。

雷达对目标的探测精度及概率受环境影响较大，且与其他各种因素密切相关。为了简化模型，假设为我机（x，y，z）与敌雷达的距离平方，则我方飞机被敌雷达i探测到的概率为[7]：

图2 雷达探测范围的三维模型图

由此可知，若敌方雷达数目为n，则我机在整个航路上被敌方雷达探测到的概率为：

此即我机受敌方雷达威胁的代价函数。

1.1.3 防空火力威胁区模型建立

防空火力阵地在地图中作用范围的模拟函数为[8]：

其中，z（x，y）是火力阵地作用范围的等效高程，（x0，y0，0）是火力阵地的位置坐标，R0是防空导弹最大作用距离。则防空火力阵地在地形中如图3所示。

图3 火力阵地三维环境模型图

当我机在敌防空火力威胁区飞行时，受到导弹的威胁程度值PM与防空火力阵地探测到我机的概率PV、地空导弹的齐射概率AM、地空导弹每发的毁伤概率ωM、导弹可靠飞行概率YM以及导弹齐射的数量N有关。计算式[9]如下：

由于地空导弹的发射概率、单发的杀伤概率和可靠飞行概率都取决于导弹自身的研发过程，所以将其中的AM、ωM、YM当作常数，简化上式为：

图4 我机与敌防空火力阵地的位置关系

图4中RS是我机与火力阵地的径向距离，△h是我机相对阵地的高度，α是我机与火力阵地视线到水平面的夹角。则PV可表示为：

式中，K为比例系数。则我机受到敌方火力威胁的代价函数ff为：

1.2 多航迹规划问题的适应度函数

通过以上对地形、雷达、防空火力等威胁区的建模，得出相应的代价函数。之后建立粒子群算法中的适应度函数如下[10]：

1.3 约束条件

在航迹规划问题中，飞机的自身性能对飞行有很大影响，在建模过程中主要考虑以下几个因素作为约束条件[11]。

1.3.1 最大水平转弯角

由于性能约束，飞机在转弯过程中只能以小于某数值的转弯角度进行转弯。设3个相邻的航迹点为、和，则转弯角度ψ为：

由此构造我机转弯角度的约束条件：

1.3.2 最大俯仰角

飞机在爬升或下降的过程中，一般不能超过最大的爬升或下降梯度，假设最大的俯仰角为θ，通常取值范围为。设两个相邻的航迹点为和，构造俯仰角的约束条件：

1.3.3 最小步长

飞机在每次机动前必须直飞一段距离，否则会影响对飞机的导航。这段距离的最小值被称为最小步长。设两个相邻的航迹点为和，最小步长为lmin，则最小步长的约束条件为：

1.3.4 最大航程约束

为了满足飞机的续航性能，在规定的航程中完成任务，飞机在飞行过程中必须考虑航迹总长的限制。设dmax是最大航程，航迹中有n个航迹点，第i个航迹点为，则最大航程约束条件为：

2 粒子群算法与基于排挤机制的K-均值聚类

2.1 粒子群算法

粒子群算法是一种仿照鸟群捕食原理的智能算法。每个粒子都是解空间中的一个可能解，而决定解的好坏的是适应度函数。粒子仅需要适应度函数值的辅助便可以确定最优解的方位，无需其他信息。粒子通过计算适应度函数，寻找粒子群体中的两个极值，并不断更新自身的速度和位置，最终搜索出最优粒子所在位置。这两个极值分别是粒子自身在搜索过程中遇到的个体最优解和群体所有粒子搜索出的历史最优解。更新粒子位置以及速度的公式[9]为：

其中，vkid是指第i个d维粒子在进行了第k次进化后的速度，xkid是指第i个d维粒子在进行了第k次进化后的位置。ω是惯性权重，c1和c2是固定的常数，一般为2。ξ和η、γ是在0～1之间的随机数。为粒子在进行了k次进化后的个体最优值，是粒子在进行了k次进化后的全局最优值。使用以上的位置和速度更新公式，经过若干次的迭代进化后，便能得到满足要求的粒子。

2.2 基于排挤机制的K-均值聚类

为规划出不同航迹，需要将所有航迹聚类，K-均值聚类使飞行方式相近的航迹被划分为同一簇，再在每一簇中用算法寻找最优。但是运用聚类需要解决的一个问题便是聚类中心数目K的取值，一般文献中都是由人为指派，本文使用基于排挤机制的K-均值聚类方法[12-13]。排挤机制的思想来源于“物竞天择，优胜劣汰”的自然界法则，种群中的个体为了生存，必须争夺有限的资源，对其他个体进行排挤。在聚类的过程中，适应度高的个体排挤适应度低的个体，而适应度低的个体因被排挤就被迫加入到与自己最相近，最合适的种群中。这样经过若干次迭代，每个个体都被分配到由一个适应度高的个体所领导的种群中。排挤机制的引入克服了人为指定K值的主观性，实现了算法的自适应功能。

3 多航迹规划问题的算法设计及流程

3.1 算法设计

本文的多航迹规划问题中一条航迹即是一个粒子，首先向规划空间中随机指派出n个粒子的位置和速度，确定聚类中心需要计算n个粒子的适应度函数值，将粒子按函数值大小进行排序为，然后引入排挤机制，记x1为第1个聚类中心c1。比较c1与x2的欧氏距离，若两粒子距离小于给定的阈值，则两粒子同属一个聚类中心c1；若两粒子距离大于给定阈值，则两粒子属于不同的聚类中心，记x2为第2个聚类中心c2。再比较x3与之前聚类中心的距离，确定属于哪个聚类中心，或构成新的聚类中心。之后的粒子相互比较排挤以此类推。欧氏距离的计算式如下[14]（假设粒子的维数为 j）：

计算每个粒子与各个聚类中心的距离，将粒子归为与之距离最小的聚类中心所属的那一簇。计算每一个簇中粒子的均值，并使其更新为此簇的新聚类中心。均值的计算方法如下[15]：

其中，Ni为第i簇中粒子的个数，c'i为新的聚类中心。如果每一簇中的聚类中心均未发生更新，则停止算法，否则重新确定聚类中心。接着对每一簇中的粒子运用式（17）、式（18）进行速度和位置的更新，当迭代到达指定代数时，输出每个簇中粒子的全局最优值，由此得到多条航迹。

3.2 流程

第1步：在模型中生成三维地形、构建障碍物，雷达威胁区域和防空火力威胁区域。

第2步：粒子群算法的初始化，合理设置算法中的各项参数。随机在地图上选取n个粒子，并指定它们的速度。

第3步：根据式（11）计算n个粒子的适应度函数值，并以此对所有粒子进行排序。

第4步：由排挤机制确定k个聚类中心，并进行K-均值聚类，直到聚类中心不再发生变化。

第5步：用粒子群算法式（17）、式（18）对同一簇中每个粒子的速度和位置进行迭代。

第6步：输出每个簇中粒子的全局最优值，若满足规定的迭代次数或预先设定的条件，则终止算法。否则，转向第4步。

第7步：生成由k个簇进化而来的k条航迹。

4 仿真实验与分析

仿真实验环境为VC++6.0和MatlabR2016a，任务规划空间为200 km×200 km×80 m，规划空间由多个山峰以及雷达和防空火力阵地组成。飞机的起点为（100，-100，0），终点为（-100，100，0）。设定飞行器最大水平转弯角为60°，最小步长为5 km，最大俯仰角为±90°。算法中粒子个数为40，维数78，ω=0.7，c1=c2=2，迭代次数为 1000。

图5是经过排挤聚类而生成的航迹三维图，图6是其对应的平面图。仿真后航迹参数见表1。由这两幅图可以看出，由于地形和威胁区的限制，由排挤机制确定聚类中心数目为2，即生成两条航迹。这两条航迹在空间上相对分离，具有独立性，且均能有效地避开山峰和雷达、防空火力阵地。若其中一条因突发威胁不可使用，可以切换到另一条航迹继续执行任务。其中黄色航迹比红色航迹适应度函数值更低，相比于红色航迹，黄色航迹距离所有的威胁区都较远，因此，飞行时优先使用黄色航迹。

图5 多航迹三维图

图6 多航迹平面图

表1 航迹参数

下页图7是使用未引入排挤机制的K-均值聚类生成的航迹三维图，图8是其对应的平面图。由两图可以看出，由于未引入排挤机制，粒子之间没有相互排挤，两簇之中的粒子相关度较高，表现为航迹在空间中不能分离，独立性不强。虽然两条航迹也能够避开威胁区，但它们在很多区段都相互靠近，不能满足实际中备选航迹的使用需求[16-18]。

图7 单航迹三维图

图8 单航迹平面图

通过以上的仿真看出，粒子群算法可以进化得到满足多个约束条件的航迹，而引入排挤机制的K-均值聚类主要用于构建多个具有独立性的种群，克服了人为指定K值的主观性，通过粒子之间的相互排挤使生成的航迹能够在空间上具有较高的离散度。使用本文所提出的算法可以基本满足作战和飞行的需求。

5 结论

本文对不同威胁区进行了建模，综合考虑了飞行器的多个约束条件，使用粒子群算法和基于排挤机制的K-均值聚类解决了飞行器的多航迹规划问题。K-均值聚类用于维持种群的多样性，排挤机制则使生成的航迹空间离散，独立性强，良好地解决了K的取值问题。粒子群通过迭代快速寻优，实现了算法的自适应。仿真结果说明算法可以满足作战中多航迹预先规划的要求，保证飞机安全完成战斗任务。