基于ADS-B IN 的多机冲突解脱及路径规划*

姚 飞，王 军，谢凯承，李广春，单 娴

（1.郑州航空工业管理学院民航学院，郑州 450046；2.郑州航空工业管理学院大数据科学研究院，郑州 450046；3.中国民用航空中南地区空中交通管理局河南分局流量管理室，郑州 450000）

0 引言

随着空中交通流量不断增加，空域越来越拥挤，对航空器的防撞系统要求越来越高。现今航空器的空中避撞主要通过空中交通防撞系统（Traffic Collision Avoidance System，TCAS）来实现。文献［1］指出TCAS 虽然可以有效地进行冲突探测和提供解脱策略，但目前的TCAS 仍存在很多不足，例如探测范围较近、探测目标有限、误警率较高、仅提供垂直方向解脱策略，对于飞行流量较大的终端区或飞行航迹比较灵活的通航飞机，无法给出有效的冲突探测和路径规划。

由于采用大量先进的通信、导航与监视设备，受空中复杂情况及气象等要素约束，不仅需要飞行员与管制员协同配合，还需要航空器具备有效的冲突预测与解脱的能力。文献［2-3］指出广播式自动相关监视（Automatic Dependent Surveillance-Broadcast，ADS-B）技术的不断发展，尤其是空空监视ADS-B IN 技术的发展，该技术能够提供高精度、高更新率的信息，飞行驾驶员能及时掌握本机周围大范围多目标的交通态势，可以在飞行规则允许范围内自主选择飞行高度、路线和速度，减轻管制员的工作负荷，提高飞行效率和安全性。

根据民航局最新规划，预计我国2025 年实现ADS-B IN 初始运行［4］。文献［5］以位置误差的概率统计特性，评估了当前ADS-B 运行间隔下的目标冲突和危险接近等碰撞风险。文献［6］提出了基于ADS-B 技术的冲突探测系统的组成，但文章没有阐述多机冲突解脱的具体方法。文献［7］将ADS-B IN监视范围内的区域划分为26 个区域，每个区域由专门判别目标是否与本机相关的规则，计算和处理工作量较大。文献［8］建立了几何型冲突预测模型，并设计算法进行仿真计算，这种方法虽然比较简单，但有一定的局限性，与传统的TCAS 方法一样。

目前冲突解脱模型主要集中在碰撞风险研究，未能进行航迹规划和提供管制策略。文献［9］以概率统计学为基础研究航空器的碰撞风险。文献［10］针对空中交通管制中的冲突探测与解脱问题，提出了一种几何最优的冲突探测与解脱方法。文献［11］采用最优控制理论和微分方程研究了固定航路条件下的多机冲突解脱问题，提出了改变航向的飞行策略。同时，针对上述问题国内外学者提出了大量的算法，例如人工智能算法［12］、改进量子遗传算法［13］、Swarm 方法和Steer 算法［14］、遗传算法［15］、改进蚁群算法［16］、狼群算法［17］等。

针对冲突解脱模型研究主要分为几何型和概率型两大类，几何型冲突探测算法是基于两架飞机最近一段时间的位置与速度矢量进行航迹外推，再根据设定的保护区模型预测未来是否发生冲突，这种方法比较简单但有一定的局限性，与传统的TCAS 方法相同。本文通过深入分析机载TCAS 和ADS-B IN 技术的特点，借鉴国内外自由飞行下利用随机微分方程建立冲突模型的方法，假设飞行中不确定因素导致的误差服从正态分布［18］，根据自由飞行下的碰撞风险设计适合机载设备和空管设备的冲突解脱与恢复算法，也为人工飞行解脱与恢复提供借鉴。

1 飞行冲突预测模型建立

通过空空监视ADS-B IN 技术，机载计算机可以预测范围更远的航空器，并提前规划出与周围所有飞机都保持安全间隔的最优飞行路径，从而实现整个空域安全高效的自由飞行。航空器在空中飞行受到多种不确定因素的影响，无论是航迹规划，还是碰撞风险的研究，都必须知道飞机确切的位置、速度、航向、高度等因素。若忽略飞行动力学、气象、人为因素等多种不确定因素，对于实际飞行中会造成很大的误差。因此，飞机在“可视”状态下，对于碰撞风险的研究才更有意义。根据相关文献［18］，大部分学者都将不确定因素引起的飞机定位误差假设为服从正态分布，且得到的结论也符合实际情况。因此，本文假设由不确定因素引起的飞机定位误差服从正态分布，利用相对运动原理，基于平面直角坐标系建立2 架飞机在水平投影面和垂直投影面上的随机运动模型，当2 架飞机相对运动距离小于最小安全间隔时认为碰撞发生。

据此建立基于相对运动原理和平面直角坐标系的水平方向冲突预测模型和垂直方向冲突预测模型。在时间段［t，T］内，飞机在水平方向和垂直方向定位误差服从N1（0，δ12）、N2（0，δ22）正态分布，其概率密度函数为：

自由飞行环境下两飞机发生碰撞的概率为P=P1×P2。P1和P2分别表示在水平方向和垂直方向上发生碰撞的概率。

1.1 模型的基本假设

为建立自由飞行环境下飞行冲突预测模型，进行如下假设：

1）多架飞机之间的运行状态相互独立；

2）飞机水平运动和垂直运动相互独立；

3）飞机自由飞行是在高空区域飞行；

4）飞机随机因素导致误差服从正态分布；

5）相对速度与两飞机之间连线的夹角简称为角度；

6）建立x-y-z 坐标系，x-y 所在平面的运动为水平方向上的运动，z 轴方向上的运动为垂直方向上的运动，采用的速度均为相对速度。

1.2 水平方向冲突预测模型的建立

两架飞机在水平投影面上相对运动示意图1所示，为了表述方便，假设飞机A 的起始位置为坐标原点（0，0），可分解计算沿坐标轴投影到水平投影面的速度分量，定位误差服从正态分布。飞机B 的位置为（x，y），同样可分解计算沿坐标轴投影到水平投影面的速度分量，定位误差服从正态分布。根据相对运动原理，假设飞机A 在此平面无实际运动的速度，转化为在原点做标准的布朗运动B1（t）服从分布N1（0，δ12），概率密度函数如式（2），飞机B 以水平相对速度v1飞行，两架飞机水平相对距离为R，角度为θ［23］。因此，两架飞机的飞行状态可转化为飞机A 以原点做标准的布朗运动，飞机B 以水平相对速度v1飞行、水平相对距离为R 的相对运动。

图1 水平投影面上飞机相对运动示意图

按以上假设建立飞机沿相对速度方向运动的微分方程模型，S（t）为飞机B 在速度v1方向上运动的距离。

由几何关系可知飞机A 和飞机B 在任意时刻的水平方向上的距离满足如下方程式：

式中，X（t）为在时刻两飞机之间的水平方向上的距离，由式（2）可知，B1（t）的均值为0，方差为δ1。

飞机在水平面上发生碰撞定义为X（t）＜D1，其中X（t）为t 时刻两飞机的水平相对距离，D1为规定的水平方向上最小安全间隔。则飞机在水平面的碰撞概率为P（X（t）＜D1）。

1.3 垂直方向冲突预测模型的建立

根据两架飞机在水平方向上飞行状态分析，利用相对运动原理转化为飞机A 在原点做标准的布朗运动B2（t）服从分布N2（0，δ22），其概率密度函数为如式（6），飞机B 以垂直相对速度v2飞行，初始时刻两飞机的相对高度差H。

式中，Y（t）为在时刻t 两飞机之间的垂直方向上的距离，由式（6）可知，B2（t）的均值为0，方差为δ2。

飞机在水平面上发生碰撞定义为Y（t）＜D2，其中Y（t）为t 时刻两飞机的垂直相对距离，D2为规定的垂直方向上最小安全间隔。则飞机在垂直方向上的碰撞概率为P（Y（t）＜D2）。

飞机发生碰撞一定是两飞机的水平相对距离和垂直相对距离同时小于规定的最小安全距离，用式子表达为：

式中，NP 为飞机架次，架/h。

每架飞机的危险系数都是相对于某一个本机的，多机航迹规划作为一种整体规划，具有协同性，即所有飞机遵循同样的规划原则，因此，每架飞机应具有唯一的危险系数。以ADS-B IN 监视范围内的每一架飞机为本机，计算周围所有飞机的危险系数，其中危险系数最大的目标机定义为本机的危险系数。根据每架飞机的危险数调整规划优先级，保证最危险的两架冲突飞机获得最远的安全间隔和最早的航迹改变，危险系数是路径规划过程中规划顺序、规划方向、冲突判定、快速求解和最优解等项目的重要依据。

2 飞行冲突解脱与路径规划模型的建立

根据ADS-B IN 数据，可以预测和发现冲突，消除所有潜在的碰撞威胁，并始终保持足够的安全间隔和最短路径，计算出最优的冲突解脱路线和回归路线，提高飞行的安全和效率。传统的垂直解脱策略通常不适用于多机冲突场景。此外，改变高度对飞机燃油消耗比较大。因此，本文采用水平解脱策略，主要分为改变航向和改变航速两种，然而飞机改变速度存在一定的延时，且速度会受气象、气流、飞行高度等影响，无法进行精确的计算，因此，本文采用的是以保速调向方式为主，调速方案只作为对调向方式的改进和补充。

2.1 模型的基本假设

根据中国空中交通管理安全规定以及实际运行情况，为尽快寻找出安全有效的冲突解脱方案，简化如下：

1）航空器在巡航阶段采用定高飞行，可简化为二维平面的冲突解脱问题；

2）按照中国空中交通管理安全规定：两架航空器之间的安全间隔为20 km，若两架航空器距离小于20 km 时，则发生飞行冲突；

3）为提高计算的精确度，计算移动的步长采用最小安全距离的一半即10 km；

4）在改变航向时，本文假设航向角可在-45°～45°中任意选取，在调整速度时假设民用航空器的速度可在预计速度的30%～130%范围内变化；

5）研究区域为200 km 的正方形区域，每隔10 km 设置一个计算点，飞机沿网格节点飞行；

6）在研究区间内飞机做直线飞行没有飞行方向的变化。

2.2 冲突解脱的目标函数

2.2.1 位置点更新函数

2.2.2 航向调整策略的目标函数

采取航向调整的策略防止冲突时，为节省冲突解脱时间，同时减少燃料消耗，民用航空器在能够规避冲突的前提下，使每个节点距离原航迹的和最小，则公式为：式中，Li为第i 架航空器的每个节点与原航迹距离总和。

为满足最小安全距离的约束，要求两机之间满足：

式中，δ=20 km。（xi，yi），（xj，yj）分别为i 机和j 机在该水平面内的坐标。

2.2.3 速度调整策略的目标函数

单独使用速度调整可能使速度调整幅度较大，且速度变化较大，航空器在高空中飞行较难保持所必需的升力，在上文假设中只假设了30%的速度调整量。本文中不单独使用速度调整策略来解决航迹冲突规划问题，只用来做航向调整策略的补充，在航向调整策略中航空器会在预计碰撞点之前作出航向改变以增加飞行路径来避免飞行冲突，本质上与减小速度来避免飞行冲突是一样的。因此，速度调整策略目标函数的形式与航向调整策略的目标函数一致，则公式为：

式中，Vi为第i 架航空器的每个节点与原航迹距离总和。

3 飞行冲突解脱与路径规划算法设计

3.1 遗传算法原理

遗传算法是一种随机搜索算法，新一代是由前一代可行解通过交叉或变异运算形成的。经过多次迭代运算，算法趋于收敛，进而得到问题的最优解或次优解。

3.2 适应度函数的改进

根据遗传算法的原理，第i 个个体被选取的概率可由式（16）计算得到。由于群体的差异性降低，算法可能出现早期收敛。因此，改进算法的适应度函数降低适应度之间的差异程度，以维护群体的多样性，避免算法出现早期收敛。

当子代的适应度小于父代且满足最小安全间隔时，就用子代染色体代替父代来进行下一轮的迭代，当子代的适应度大于父代或最小安全距离小于20 km 时用父代染色体来开始下一轮迭代，这样，就可以保持种群个数不变且个体都是符合约束的，迭代方程如式（17）。

式中，n 为种群的个体数，N 为迭代次数，y为通过变异突变得到的个体，f 为适应度，D 为每个节点飞机之间的相对距离。

3.3 采用改进遗传算法的飞行冲突解脱

3.3.1 问题简化

根据遗传算法的原理，需要对每一条航迹的坐标进行编码。在边长为200 km 的正方形区域内，每隔10 km 设置一个计算点，这样共有21 个点。按照两架飞机进行计算的变量数有126 个，编码工作较大。为此，对问题进行简化如下：

1）三维立体问题简化为二维平面问题，多机避免冲突时只在水平面内改变方向；

2）飞机的飞行速度不变；

3）飞机可选航向：原航向，左偏45°，右偏45°。

经过上述3 步简化就可以避免直接对飞机的3个空间坐标进行编码，对每架飞机的每步飞行方向进行编码，飞机只有3 个飞行方向，采用二进制编码，两位就可表示出所有情况，00（0）和01（1）表示按原方向飞行，10（2）表示向原航向左侧飞行，11（3）表示向原航向右侧飞行，一个染色体就是84 个bit。

3.3.2 算法步骤

针对多机解脱策略，设计改进遗传算法，其计算步骤如下：

步骤1：初始化参数。确定解脱所需步数、航向改变角度、最小安全间隔、飞机初始位置点、飞机飞行方向、最大迭代次数、初始种群个数、变异概率、交配概率。

步骤2：产生初始可行解。将产生的初始种群解码，再转换成相应的偏转方向和角度，通过式（10）可以得到飞机在每个飞行节点的坐标，看两架飞机是否满足式（13），若满足则作为一个可行解保留下来。筛选足够多的满足最小安全距离的个体组成初始种群。

步骤3：计算初始种群中每个个体的适应度。由式（11）、式（12）可计算得到每个个体的适应度。

步骤4：进行染色体突变和交配。

步骤5：检查新得到的个体是否满足式（13）要求，用式（11）和式（12）计算每个个体的适应度。

步骤6：由式（7）进行更新迭代，若子代的适应度小于父代且满足最小安全间隔时，就用子代染色体代替父代来进行下一轮的迭代，当子代的适应度大于父代或最小安全距离小于20 km 时，用父代染色体来开始下一轮迭代，始终用每个个体迭代中出现的最优的个体去进行下一次迭代。

步骤7：由式（11）和式（12）计算每个个体的适应度，记录最优值和最优个体。

步骤8：若迭代次数没有超过最大限制或最优值出现次数没有超过限制，则返还步骤4。

4 仿真验证结果及分析

本文假设水平方向和垂直方向上的运动相互独立，水平相对速度、角度、垂直相对速度都为变量，在模型中不易求解。先研究垂直方向相对速度为定值，水平相对速度和角度在一定的范围区间变化对碰撞风险的影响。在垂直相对速度确定情况下，可以给出改变水平方向速度或改变角度来降低碰撞风险的措施。

本文以ICAO 规定的安全等级4.5 次事故/108飞行小时为目标［22］，若高于此标准则对应的角度和速度为可行方案，低于此标准则为不可行方案。

4.1 不定步长航向调整策略的仿真计算

按照10 km 的间隔将冲突区域划分为20×20个方格，飞机沿网格线飞行的距离和沿网格对角线飞行的距离是不同的。假设飞机沿网格线飞行到下一节点和沿对角线飞行到下一节点所用时间相同。因此，飞机飞行每步都在网格节点上，有利于初始研究，并对后续改进提供一定参考。

表1 不同角度和速度下的危险系数

设初始种群有150 个个体，最大迭代次数100，两飞机冲突解脱情况如图2，最优值的迭代情况如图3，用冲突预测模型得到的每个节点的危险系数值如图4。从图3 中可以看出最优值呈现出阶梯式下降，从45 代之后始终处于恒定值，即认为得到了最优解，由于对适应度函数进行了改进，可以清晰地从图3 看出最优值的迭代情况呈现阶梯式下降且都是确定的值。从图4 可以看出在第10 个飞行节点碰撞危险系数最大，且小于指定的安全目标等级（4.5 次事故/108飞行小时），在其他节点碰撞危险系数都是0，没有碰撞风险。若在第9 个飞行节点和第11 个飞行节点进行精细的划分可以得到更精确的结果。

图2 不定步长2 机航迹规划

图3 最优值迭代情况

图4 每个节点的碰撞风险系数

4.2 定步长航向调整策略的仿真计算

设定每架飞机预计航线方向步长均为10 km，最小安全距离为20 km。若有航向的调整必定会造成有的飞行节点不在网格节点上，实现起来要比不定步长航向调整策略复杂一些，仿真模拟效果更接近于实际情况。

多机飞行冲突可分为两机连续冲突和多机汇聚冲突，如图5 和图6 所示。对于这两种典型的多机飞行冲突，通过本文提出的无冲突航迹规划方法可以快速地找出一条最优的无冲突航迹，如图7 和图8 所示。仿真计算后的航迹点完全错开，并且相互之间的水平间隔始终满足航路最小间隔20 km 的要求。

图5 连续两机冲突

图6 多机汇聚冲突

图7 采用航向调整策略的两机航迹规划

图8 采用航向调整策略的四机航迹规划

4.3 加入速度调整策略两机航迹规划优化仿真计算

从图7 中可以看出飞机调向次数较多，这是由于设置的目标函数造成的，飞机为避免冲突不得不在碰撞点之前进行多转向来在航路上消耗时间以达到避免冲突的目的，但转向次数过多在实际飞行中并不现实，转向次数过多实际上就是在航路上消耗时间，用速度调整策略可以达到相同的目的，加入减速策略的两飞机冲突解脱情况如图9。未加入减速策略的定步长航向调整策略的最优值为56.569，加入速度调整策略的定步长航向调整策略的最优值为28.284，减少了近50%，可见加入减速策略不仅可以减少转向次数也可以极大地减少最优值。

图9 采用航向和速度调整策略的两机冲突解脱

5 结论

本文结合ADS-B IN 技术特点，建立了多因素的概率型飞行冲突预测和解脱模型，并设计了基于改进遗传算法的飞行冲突解脱与路径规划算法。该算法不仅保持了传统遗传算法全局搜索和跳出局部最优的能力，且能够对一些适应度较高的个体进行控制，维护群体的多样性，进而提高了寻优的能力，避免了遗传算法易出现早期收敛现象。基于安全目标等级4.5 次事故/108飞行小时（h）为限制条件，通过多机航向调整、速度调整2 种策略冲突解脱的仿真，保证了飞机之间的安全间隔，实现了解脱后自动回归到原航迹上，验证了该算法在多机飞行冲突解脱问题中的可行性、高效性和优越性。