基于NSGA-II 算法的三维多目标航迹规划*

王 瑛，郑煜坤，吕茂隆，李正欣

（空军工程大学装备管理与无人机工程学院，西安 710051）

0 引言

飞行器航迹规划是指在综合考虑飞行距离、时间、机动特性等一系列条件的情况下，得到的能规避障碍且保证飞行安全的最优航迹，可分为无人机航迹规划和民用飞机航迹规划［1］。由于其机动特性和规划目标不同，因此，采用的方法和最终航迹也不同。

目前无人机航迹规划已拓展至三维空间，多采用稀疏A*算法［2］、改进蚁群算法［3-4］、RRT 法［5］等进行，优先考虑飞行航迹的距离和避障效果。而在民航航迹规划领域，孟令航等［6］以改航代价最小为规划目标，利用不确定测度和云团状态转移矩阵建立二维航迹规划模型。王世锦等［7］采用改进元胞自动机进行航迹规划，在减少规划时间的同时提升了规划效果。李雄等［8］针对民航飞行的特点，提出了综合安全和效率的多目标改航模型，有效规避了危险天气等障碍区域。但多数民航航迹研究仍基于二维空间进行，忽视高度维对规划效果的影响，造成空域资源浪费［6-8］，同时规划目标设置单一，未能充分考虑飞行过程的安全性及可行性。

随着民用航空的快速发展，飞行流量逐年上升，部分航路将不可避免地穿越障碍区域，合理利用空域高度进行航迹规划比传统二维航路改航更能提升空域利用率和空域安全性。因此，本文充分考虑空域环境的影响，以飞行航程、航迹离散系数、角度变化量、转弯点个数这4 项指标最小为规划目标，以民用飞机的机动特性和民航飞行规则为规划约束建立三维多目标航迹规划模型，并利用增加了删除算子的NSGA-II 算法求解该问题，最后进行实例分析和比较，证明了该模型的可行性。

1 环境构建

1.1 栅格模型

在三维航迹规划中，栅格法是指将规划空域划分为规则立方体以表示飞行航迹的一种空间建模方法［8］，如图1 所示：

图1 栅格示意图

根据空域结构的特点设置栅格块的长、宽、高，由于民航飞行高度有限，可令栅格块的长、宽为r'km，高度为l'km。栅格模型的建立步骤可表示如下：

1）沿X 轴、Z 轴、Y 轴依次对栅格块进行标号，并建立栅格块标号与其中心点坐标之间的转换关系：

式中，floor 为向下取整，mod 为取余，N 代表栅格块标号，GX、GY、GZ 分别为沿X 轴、Y 轴、Z 轴的栅格块数量，可将规划空域分为GX×GY×GZ 个栅格块。

2）构建栅格块的状态函数：

式中，GN代表标号为N 的栅格块，ZW、ZT和ZMO分别代表危险天气空域、“三区”空域和山区，Zfree代表自由空域。

3）将起点、终点置于规划空域两侧中心处，沿Y 轴进行航迹规划。

1.2 地表环境

为模拟规划空域的地表环境，可采用式（3）、式（4）建立原始随机地形和山峰模型［5］：

1.3 “三区”环境

我国空域结构复杂，存在大量“三区”空域，即“危险区”、“限制区”和“禁飞区”［7］。“三区”空域是为保障军事训练、维护战略目标安全而设置的特殊空域，通常为一规则多边形。因此，“三区”空域是影响民航飞行的重要因素，原则上任何航路均需避让，但由于训练区域转移、新航路开辟等原因，许多航路都穿越了“三区”。

1.4 危险天气

雷雨、飓风等危险天气会对飞行安全造成严重影响。当发生局部暴雨时，飞机可在积雨云上方或雷雨范围外通过。由于空气湿度存在差异，积雨云常分布在2 000 m～15 000 m 之间［9］。假设暴雨的作用范围如下：

2 基于NSGA-II 的规划模型

2.1 基本思想

遗传算法是基于进化论创建的，利用选择、杂交、变异等遗传算子模拟生物进化历程，不断寻找最优解的规划算法。其中，NSGA-II 在传统遗传算法的基础上，引入快速非支配排序方法和精英保留策略，拓展了pareto 最优解的范围，提高了针对MOP 的求解能力［10］。

2.2 编码方式

在进行三维航迹规划时，可采取整数编码方式对染色体进行编译，数字1～9 分别对应9 个前进方向，如图2 所示。由于沿Y 轴进行规划，且起点、终点位于最外侧栅格，则染色体长度为GY-1，其基因型与实际航迹的转换规则可表示为：

式中，xi表示染色体的第i 个基因，ni表示第i 个基因对应的栅格序号。

图2 染色体编码示意图

2.3 目标函数

不同于军用飞机和无人飞行器，民用航空的主要任务是在确保安全的前提下，以最小的经济代价完成既定飞行目标［7］。在航迹规划过程中，不仅要考虑航程长短等经济效益，而且要考虑转弯点个数、航迹离散程度等安全效益。因此，采用以下目标函数进行三维航迹规划：

1）飞行距离

式中，s 为起点栅格块，gi为染色体上第i 个基因对应的栅格块，gGY-1对应终点p，d（gi，gi+1）为栅格块之间的距离，M 为罚函数。

2）航迹离散系数

式中，X（gi）为gi的横坐标，Z（gi）为gi的横坐标，表示航迹在X 轴上的平均值，SX为航迹在X 轴上的离散程度。

3）角度变化量

式中，f（Δθi）为判别函数，用来判断航迹是否转向。

5）罚函数

式中，K 为罚因子，可取K=1 000，C（gi）为栅格块gi的状态值。

2.4 约束条件

为确保空域的合理使用以及飞行安全，民航航迹规划需要满足一定的约束条件，分为飞机机动特性约束和飞行规则约束。机动特性约束是指为了维持飞机正常飞行而允许的极限姿态，包括俯仰角约束和最小转弯半径约束。飞行规则约束是指管理部门为了保证空域合理使用而制定的相关规则，包括飞行高度约束和飞行范围约束。其具体内容如下：

1）俯仰角约束：民航飞机的俯仰角应控制在-15°～25°之间［9］，否则容易造成飞机失速、解体等危险。

2）最小转弯半径约束：飞机在水平面转向时航迹的最小转弯半径，大型客机约为5 km，中型客机约为3 km。

3）飞行高度约束：为保证双向行驶飞机的正常运行，防止撞机等安全事故发生，有关部门制定了以下巡航高度层的分布规则［11］：

表1 巡航高度层划分规则

其中，高度以海平面为基准进行测量，单位为km，Δh 表示高度层间隔。

4）飞行范围约束：民航飞行要规避“三区”、危险天气和山脉，即有：

3 算法描述及流程

3.1 算法描述

NSGA-II 利用快速非支配排序方法和精英保留策略提高了选择算子的搜索能力，且无需对目标函数进行权重赋值或同量纲处理。为了加快运算速度，减少无效计算，在传统遗传算子的基础上，引入删除算子，及时删除超出规划范围的染色体。

3.1.1 快速非支配排序方法

1）由适应度函数确定任意两个体之间的支配关系，定义pareto 支配关系如下：

3.1.2 精英保留策略

将父代种群与子代种群融合产生复合种群，并利用快速非支配排序梳理种群中个体顺序，产生新一代父种群，从而将优良基因保存下来。

3.1.3 遗传算子

在对航迹规划问题进行求解的过程中，遗传算子能够及时剔除界外航迹，保留优质航迹，寻找新航迹，采用正确的遗传算子将确保最终航迹的质量和效能。

1）选择算子：将目标函数设置为适应度函数，采用期望值法进行选择。首先，针对个体数为2 N 的复合种群进行快速非支配排序，计算全部个体的irank和L（i）d。其次，根据选择规则选出N 个个体。选择规则表述如下：

即当个体xi与xj级别不同时，选择级别小的；当其级别相同时，选择拥挤度大的。

2）杂交算子：采用单点交叉方式。首先将种群中个体随机配对并设置交叉位置，根据杂交概率Pc判断是否进行交叉；若进行交叉，则在交叉位置交换两个体的相应染色体；最后判断生成的个体是否满足范围约束，若不满足，执行删除算子操作并重复上述步骤。

3）变异算子：采用基本变异操作。首先随机选择变异个体和变异位置，根据变异概率Pm判断是否进行变异操作；若进行变异，则改变变异位置的基因编码；最后判断生成的个体是否满足范围约束，若不满足，执行删除算子操作并重复上述步骤。

4）删除算子：根据个体基因的编码情况判断其是否满足规划范围约束，若不满足则删除该个体。相应的判断规则如下：

3.2 算法流程

结合4 种遗传算子及排序和选择的相关策略，可得出以下算法求解流程：

1）初始化种群，设置进化代数Gen=0，终止条件为Gen＞Gen'；

2）判断是否生成初代子群，若是，则执行步骤4）；若否，则执行步骤3）；

3）对初始种群进行快速非支配排序，之后执行选择、交叉、变异、删除操作生成初代子群，执行步骤2）；

4）设置进化代数Gen=1；

5）合并父、子代种群，生成复合种群，执行步骤6）；

6）判断是否生成新父种群，若是，则执行步骤7）；若否，则执行步骤8）；

7）对新父种群进行选择、交叉、变异、删除操作生成新子种群，执行步骤9）；

8）对复合种群进行快速非支配排序，并选择前N 个个体生成新父种群，执行步骤6）；

9）判断进化代数Gen 是否小于Gen'，若是，则令Gen=Gen+1，并执行步骤5）；若否，则算法结束，输出结果。

4 实例分析

4.1 参数设置

4.2 仿真结果

根据飞行规则［9］，起点、终点位于进近管制区，高度约为6 km，可令其栅格标号分别为211 和7 811，由栅格块的信息可知该模型符合飞机机动特性约束和飞行规则约束。利用NSGA-II 算法和三维A*算法分别对模型进行求解，其中三维A*算法是基于启发型搜索函数而建立的，可通过构造空间中任意点距起点和终点距离的代价函数，获得一系列拥有最小代价的点集，从而产生基于全局信息的最短路径。规划结果如图3 所示。

图3 规划结果示意图

图中，黑色粗实线为原航迹，其穿越部分“三区”。黑色虚线为使用NSGA-II 算法得到的航迹，黑色细实线为使用三维A*算法得到的航迹，所有规划航迹避开了“三区”、暴雨和山峰，符合相关约束。为清晰表示航迹的特征和具体规划细节，绘制如下航迹俯视图：

图4 航迹俯视图

表2 航迹属性

由表中数据可知，航迹②利用空域高度对暴雨天气进行规避，缩短了飞行距离，比其他航迹少16.4 km。航迹①、⑤拥有最小的角度变化量和转弯点个数，其余指标均处于中等水平，性能较优。航迹③、④的各项指标值较为均衡，性能良好。而航迹⑥的各项指标均排名最后，且角度变化量和转弯点个数差距较大，整体性能较差。

根据以上结果不难看出，基于NSGA-II 算法的三维航迹规划较A*算法更为优越，且一次运算能产生多条具有不同属性的航迹，确保了飞行安全和效率，方便使用者在不同环境条件和任务目标下进行选择，为民航航迹规划提供了新方法。

5 结论

本文通过模拟复杂空域环境，设置确保飞行经济和安全的多项规划目标和约束条件，建立了三维多目标航迹规划模型并利用NSGA-II 算法完成求解，扩大了传统民航航迹的研究范围，提高了空域资源利用率及规划结果的鲁棒性和适用性，能够帮助决策者在不同的环境条件和任务目标下作出选择。但是，本文的研究仅针对静态空域，且未考虑多机飞行时的航迹关联和相互影响，今后将以动态天气条件下的多机航迹规划为研究方向。