基于半自由飞行模式的多机协同航路规划

毛 亿，陈 平，徐 颖,2，杨 毅

（1.空中交通管理系统与技术国家重点实验室,江苏 南京 210007；2.中国科学院空天信息创新研究院,北京 100094）

随着时间的推移，空中交通管制系统已经无法适应新的社会需求。“自由飞行”的概念是上个世纪为解决民航客流快速增长而提出的，被认为是未来最可能的空管系统模式，因为它提供了目前空中交通集中管制系统无法提供的以下功能：1）每架飞机可以自由选择起飞和降落的位置；2）每架飞机可以以最小的飞行时间自由规划其航线；3）飞行中的飞机可以通过使用冲突消解制导律来避免碰撞。在现有的空管系统中，由于设施和通信技术的落后，以及监管模式的不足，导致“自由飞行”实施困难。在“自由飞行”模式下，空管局无法有效管理所有在飞飞机。首先，由于在该模式下每架飞机都可以自由决定其飞行路线，空管系统可能无法实时接收到每架飞机的飞行信息，难以对非法飞行进行拦截和监督。其次，每架飞机的飞行信息无法实时传输到空中交通管制系统，给空中交通管制系统实时控制飞机带来了巨大的安全隐患。最后，在自由飞行模式下，每个飞行员会完全自主地选择航线飞行，从而导致航线冲突，而自主选择的冲突消解策略很可能导致新的冲突。

针对“自由飞行”存在的问题，本文扩展了“自由飞行”的概念，提出了半自由飞行模式，在实现“自由飞行”功能的同时，提供空域安全以及与每架飞机的通信，一定程度上，半自由飞行可以看作是自由飞行的一个过渡阶段。与自由飞行不同的是，半自由飞行空中交通管制（SFF ATC）系统从所有飞机接收信息，然后制定总体飞行计划，因此多机航路规划是系统中最重要的部分。

1988 年Canny[1]证明了路线规划是一个NP问题。此后，路径规划被广泛应用于许多不同的领域，包括智能交通系统、空间应用、自主机器人、军事制导和导航系统等[2−3]。在过去的几十年里，学者们广泛致力于飞行器的路径规划，为了加快规划过程，目前已提出了几种规划方法和优化算法。

图论算法。Voronoi 图法是解决路径规划问题中应用最广泛的方法。在文献[4−5]的研究中，威胁区域被建模为点，这些威胁点被用来生成Voronoi 图，然而Voronoi 图法往往不能很好地处理约束条件。另一种常用的方法是概率路线图，它使用由大小相同的方形单元组成的数字化网格来表示路线规划的环境[3,6]。

群体智能算法。为解决路径规划问题，已提出许多群体智能算法，包括遗传算法(GA)[7]、进化规划(EP)[8−9]、粒子群优化算法(PSO)[10]和蚁群优化算法(AOC)[11−12]。这些算法具有很强的鲁棒性和灵活性，可用于解决不同类型的优化问题，然而计算速度限制了其在多架飞机航路规划中的应用。

启发式搜索算法。A*是一种最佳启发式搜索算法，用于寻找从给定初始节点到目标节点的最小代价路径[13]。LI 等[12]介绍了D*搜索算法。然而，随着问题空间变大，对于A*或D*，搜索最优或接近最优路径所花费的时间呈指数增长算法。

本文提出了一种基于动态网格和协同动态规划的多机协同航路规划算法，以解决多架飞机的航路规划问题。该方法在避免飞行冲突的同时，实现了多架飞机的航路规划功能，并且进一步提供了路线重新规划的功能，即当某架飞机决定改变目的地时，SFF ATC 系统可以实时重新规划其航线，同时保证新航线不影响其他飞机的航线。数值仿真结果验证了该路径规划方法的有效性性。

1 SFF ATC 系统描述

SFF ATC 系统的工作是维持在其控制区域内飞行的所有飞机的安全性，为每架飞机提供通信和航线支持，同时监督整个飞行网络，以确保其正常运行。SFF ATC 系统的常规工作流程是从接收其控制的飞机的飞行请求开始，然后在内部系统中计算最优飞行计划，接下来向每架飞机发送飞行计划，此外该系统在几分钟的间隔将提供更新的飞行计划。

SFF ATC 系统的工作模式如图1 所示，系统有以下4 个接口提供外部通信。

1)与即将起飞飞机的接口。SFF ATC 系统接收即将起飞飞机的飞行请求，包括估计时间、起飞和降落的位置以及飞机本身的信息，然后系统向飞机发送一个带有飞行计划的回复，接下来飞机向系统反馈是否符合该飞行计划。

2)与空中飞行飞机的接口。在飞行过程中，飞机必须将自己的信息以飞行报告的形式发送给SFF 空管系统。这样，系统可以获取每架飞机的飞行状态，对每一次飞行进行监控，同时对所有飞机的飞行路线进行调节和控制。系统收到飞机的飞行报告后，会根据实际情况将计划的飞行路线返回给每架飞机。飞行报告包括以下信息：飞机当前位置和其他飞行状态(如剩余燃料)；决定是否改变目的地，如果是，则使用新的目的地坐标。此外，系统返回的飞行航线可以分为两种情况：不变，飞机按照原航线飞行，直到收到下一条航线指令；更改，飞机接收到一条新航线，并沿着这条新航线飞行，直到接收到下一条航线指令。

3)与指挥官窗口的接口。指挥官可以在指挥官窗口向SFF ATC 系统发送指令，并观察每架飞机的飞行状态和计划路线。指挥官传达的指令包括改变飞机的等级、禁用一些机场、迫使一些飞机停止飞行。

4)与环境效应器的接口。该接口将外部环境影响因素导入SFF ATC 系统，包括风场、温度、气压等。此信息将用于路由规划模块。

在图1 所示的工作模式下，SFF ATC 系统可以同时满足便捷和安全的要求。对于飞行员来说，必须要做的工作就是输入起飞和降落的位置。

图1 SFF ATC 系统的工作模式

2 路线规划

2.1 路线规划要求

路线规划是传统空中交通管制系统中不可避免的问题，路线规划方法决定了空管系统的效率。“自由飞行”的方法是省去航线规划过程，让每架飞机自己规划一条航线。一般来说，飞机的航线是从起飞位置到着陆目的地之间的一条直线。但自由飞行也会引起一些问题，包括飞机冲突和缺乏监督。

在半自由飞行中，飞机不得自行规划航线，因此航路规划是SFF ATC 系统的关键模块。半自由飞行中的路径规划是一个多机多约束的优化问题。

航路规划模块导入的数据包括当前每架飞机的飞行请求和飞行报告。每个飞行请求中的信息包括飞行高度、起飞位置、期望起飞时间、降落位置、飞机最小转弯半径。飞行报告中的信息包括实时的飞行状态，如3D 坐标、速度矢量、剩余飞行时间等，此外关于是否改变目的地的决定也应该报告。

航线规划模块对航班及其信息进行排序，并提供一个飞行计划列表，如表1 所示。

表1 飞行计划一览表

SFF ATC 系统将计划的航线返回给相应的飞机。每架飞机只需要追踪自己的航线，直到到达目的地或接到新指令。规划的航线应考虑3 个因素：性能指标、飞行约束和环境干扰。

航路规划的性能指标包括飞行时间和飞行路径两部分。协同航路规划的目标是最小化所有飞机的飞行时间和航路之和。

飞行约束包括3 个不同的变量：两架飞机之间的距离约束、禁飞区约束和最小转弯半径约束。距离约束为式(1)，要求任意两架飞机之间的距离小于安全距离。

禁飞区限制规定限制飞机进入禁飞区，决策方法见2.2 节。最小转弯半径约束与网格生成有关，如2.2 节所述。

环境干扰对飞机的飞行路线有一定的影响，其中最大的因素是风场。在飞行过程中，顺风飞行的飞行时间会有所减少。

2.2 路线规划的数学描述

考虑到实际问题和需求，路径规划问题可以用数学模型来描述。

假设航路规划模块收到共N架飞机的飞行请求，起飞窗口为(φT，φT，tT)i，i=1，2，···，N，也可以在发射坐标系中转移到(xT，yT)i。飞机Ai的着陆位置(φL，φL)i，i=1，2，···，N，也可以在发射坐标系中转移到(φT，φT)i。优化每架飞机的4D 航线pi(t)，在发射坐标系中包括(x(t)，y(t)，z(t))i，最小化性能指标，如下式：

飞机Ai的路径 Ti(t)必须满足以下约束。

1)安全距离约束

2)禁飞区限制

在自由飞行过程中，飞机必须避开所有的禁飞区，包括飞行禁区、限制区和危险区域。操作环境中的这些实际区域可能具有不同的形状。本文用3 种几何形状简要地表示这些禁飞区：半椭球、圆柱体和长方体。在现实中，可以通过这3 种基本形状的适当组合来充分描述或近似禁飞区。另外，位置和尺寸这些基本形状的参数可以定义为时间函数来表示禁飞区造成的威胁系数。

（a）三维半椭球禁飞区域用7 个参数来描述，分别为：中心位置的坐标(xs，ys，zs)、3 个半轴(a，b，c)和一个定向角θ。与基础坐标系（X，Y，Z)的转换由式(4)实现。半椭球形禁飞区如图2 所示。

图2 椭球形禁飞区

在转换到基础坐标系后，如果给定点(xp，yp，zp)满足

那么它就在半椭球形禁飞区之外。

(b)长方体禁飞区域用7 个参数来描述，分别为：中心位置的坐标(xc,yc,zc)、三维(a,b,c)和一个定向角θ。与基础坐标系（X，Y，Z)的转换由式(4)实现。长方体禁飞区如图3 所示。

图3 长方体禁飞区

在转换到基础坐标系后，如果给定点(xp，yp，zp)满足

那么它就在长方体禁飞区之外。

(c)圆柱体禁飞区域用5 个参数来描述，分别为：中心位置坐标(xc,yc,zc)、底面半径R、高度L。与基础坐标系（X，Y，Z)的转换由式(8)实现。圆柱体禁飞区如图4 所示。

图4 圆柱型禁飞区

如果给定点(xp，yp，zp)在圆柱体外，经过变换后满足以下条件之一：

3)最小转弯半径约束

式中：Δy是飞机在x轴上飞过Δx时，沿y轴的偏离距离；Δymax是飞机在x轴上飞过Δx时沿y轴的最大偏差距离。最小转弯半径约束示意图如图5所示。

图5 最小转弯半径约束示意图

3 协同动态规划方法

本节介绍协同动态规划方法来解决上述多架飞机的协同航路规划问题。协同动态规划方法分为实时动态网格法和协同动态规划算法两部分。

3.1 实时动态网格法

网格法是一种常用的单元分解建模方法，将飞行空间划分为三维规则网格。飞行环境可以通过网格的分配来描述。在后续的路线规划中，网格将作为基本单元。

网格方法具有以下优点：一是规则的网格阵列易于计算机存储和计算，相邻网格之间简单直接的关系避免了处理障碍物边界信息时的复杂计算；其次，当网格间距足够小时，网格方法可以描述任意形状的任何障碍物，因而具有广泛的应用前景。

网格法的缺点主要体现在环境描述的精度与优化算法的效率之间的冲突。网格尺寸越小，其描述越准确，搜索计算占用的存储空间越大，所花费的运行时间就越长。但是，如果以降低描述精度为代价来减少存储空间和运行时间，那么搜索结果与实际最优路径之间可能存在较大的差异。

为了克服上述缺点，本节提出了一种实时动态网格方法。该方法生成了飞机Ai在t时刻的特定坐标系和网格。具体方法如下。

假设飞机Ai在时间t的当前位置为(x0,y0,z0)i，目标位置为(xT,yT,zT)i。建立飞机Ai的相对坐标系，其中原始点为(x0,y0,z0)i，y'轴为从(x0,y0,z0)i至目标点(xT,yT,zT)i的连线，x'轴为y '轴在原始点的垂直面与水平面的交叉线，x'轴、y'轴、z'轴构成一个笛卡尔坐标系。原理图如图6 所示。

图6 飞机Ai 相对坐标系示意图

第i架飞机A的网格i基于上述的相对坐标系进行划分，具体方法如下。

假设沿着x'、y'和z'轴的间隔数为Nx、Ny、Nz，间隔与各轴最大值的关系可以描述为

式中：Nymax为沿y轴的最大间隔数；dis 为飞行器当前位置到目标位置的距离；dis0为初始时刻飞行器位置到目标位置的距离，t=0；Δymax可以通过式(11)计算得到；Nz是C乘以Nx，其中C与上升速度有关。Nx的示意图如图7 所示。

图7 网格参数设置示意图

3.2 协同动态规划算法

在多架飞机的飞行过程中，任意两架飞机之间的飞行安全距离是需要考虑的主要约束条件。此外，安全距离约束使得大多数单一航路规划方法难以解决多架飞机的航路规划问题。

本节提出了一种求解多架飞机协同航路规划问题的协同动态规划算法，具体步骤如下。

步骤1，初始化时间变量t=0，并定义空域的大小为：

步骤2，输入威胁区域和路径点的信息以及风场模型的信息。

步骤3，输入每架飞机 Ai的起飞位置(x0，y0，z0)i，起飞时间ti0，以及目标位置(xT，yT，zT)i。步骤4，构建各飞行器的相对坐标系和网格Ai，i=1，2，···，N，具体方法见3.1 节。

步骤5，考虑到乘客的舒适度，优先考虑短途航班。按飞机到目标位置的距离排序：距离最小的飞机编号为1，距离最大的飞机编号为N。

步骤6，计算飞机Ai的性能指标和最优航线。

步骤6.1，计算第i架飞机飞行轨迹从第0 步p(x0，y0，z0)到第一步p(xn1，y1，zn1)的性能指标。其中，xn1∈(x0−Δx，x0+Δx)，zn1∈(z0−Δz，z0+Δz)，Δy和Δz满足式(10)的约束。

计算点(xn1,y1,zn1)的性能指标为：

式中：J{p(xn1，y1，zn1)}是点p(xn1，y1，zn1)的性能指标；J{p(x0，y0，z0)}是前一个点p(x0，y0，z0)的性能指标；dis(p0，1)是点p(x0，y0，z0)与p(xn1，y1，zn1)之间的距离，也表示从p(x0，y0，z0)到p的移动过程中增加的性能指标p(xn1，y1，zn1)；R(p(xn1，y1，zn1))表示飞行轨迹从p(x0，y0，z0)到p(xn1，y1，zn1)的约束，包括安全距离约束、威胁区域约束等，R(p(xn1，y1，zn1))的计算方法在2.2 节中介绍；ΔVA2是点p(xn1，y1，zn1)的风力因素；k1、k2、k3是对应于每个指标的权重系数。

在存储Ω(xn1，y1，zn1)中保存每个点性能指标最小的最优路径来源p(xn1，y1，zn1)。

步骤6.2，计算第i架飞机飞行轨迹从第一步p(xn1，y1，zn1)到第二步p(xn2，y2，zn2)的性能指标。其 中，xn2∈[xn1−Δx，xn1+Δx]，zn2∈[zn1−Δz，zn1+Δz]，Δy和Δz满足式（10）约束条件。

计算点(xn2，y2，zn2)的性能指标为：

在存储Ω(xn2，y2，zn2)中保存每个点性能指标最小的最优路径来源p(xn2，y2，zn2)。

步骤6.k，计算第i架飞机飞行轨迹从(k−1)步p(xn(k−1)，y(k−1)，z(k−1))到第k步p(xnk，yk，znk)的性能指标。其中，xnk∈[xn(k−1)−Δx，xn(k−1)+Δx]，znk∈[zn(k−1)−Δz，z n(k−1)+Δz]，Δy和 Δz满足式（10）约束。

计算点(xnk，yk，znk)的性能指标为：

在存储Ω(xnk，yk，znk)中保存每个点性能指标最小的最优路径来源p(xnk，yk，znk)。

步骤6.Nx，计算第i架飞机飞行轨迹从第(Nx−1)步p(xn(Nx−1)，y(Nx−1)，z(Nx−1))到 第Nx步p(xnNx，yNx，znNx)的性能指标。其中，xnNx∈[xn(Nx−1)−Δx，xn(Nx−1)+Δx]，znNx∈[zn(Nx−1)−Δz，zn(Nx−1)+Δz]，Δy和 Δz必须满足式（10）约束条件。

计算点(xnNx，yNx，znNx)的性能指标为：

在存储Ω(xnNx，yNx，znNx)中保存每个点性能指标最小的最优路径来源p(xnNx，yNx，znNx)。

步骤7，找到最优轨迹Ti。从目标点p(xT，yT，zT)回到p(x0，y0，z0)，转换从ith相对坐标系x'-y'-z'到基本坐标系X-Y-Z，得到Ti。

步骤8，如果i

步骤9，平滑轨迹Ti并跟踪它，时间间隔为Δt。

步骤10，检查所有飞行器是否达到目标点，如果达到，则结束算法，执行步骤9；否则，继续执行步骤2。

步骤11，输出所有飞机Ai(i=1,2,···N)的航线和性能指标。

4 数值模拟

本节通过3 个仿真来验证SFF ATC 中协同动态规划方法的可行性。这些仿真从3 个方面测试了路径规划模块以及路径规划方法。仿真1 展示了多架飞机同时进行航路规划的功能。仿真2 展示了在路径规划过程中避免两架飞机冲突的功能。仿真3 展示了飞机航线重新规划的功能。

根据图1 所示的SFF ATC 系统的工作模式，系统接收每架计划第二天起飞的飞机信息，然后根据协同动态规划算法为这些飞机规划飞行路线。一般来说，SFF ATC 系统会接收第二天计划起飞的每架飞机的信息。

4.1 3D 规划的路由仿真结果

在SFF ATC 系统接收到第二天每架飞机的飞行信息后，多机航路规划模块开始工作。SFF ATC 系统生成如表1 所示的飞行计划，并根据其要求规划飞机航线。

模拟1 给出了50 架飞机的起飞窗口和目标位置：(φT,φT,tT)i和(xT,yT)i，i=1，2，···，N。利用协同动态规划算法优化50 架飞机的航线。最优结果必须满足式(2)—(9)的约束，并且全局性能指数（式(2)）应最小化。采用协同动态规划算法计算的数值结果如图8—11 所示。图8 为飞行模拟中周围的风模型，图9 为飞行区内的三维规划航线，图10和图11 分别为图9的水平视图和垂直视图。在仿真结果中，我们可以看到每架飞机到达目的地的飞行路线，此外禁止飞行路线进入任何威胁区域。

图8 风模型地图

图9 50 架飞机的3D 规划航线

图10 50 架飞机在水平面的规划航线

图11 垂直平面50 架飞机的规划航线

仿真1的结果(图9—11)表明，协同动态规划可以为多架飞机规划航线。飞行冲突情况反映在图9 中。即使两条轨道相交，我们也不能判断它们是否会碰撞，因为每架飞机起飞的时间是不同的。仿真2 选取两条航线分析冲突解决功能。

4.2 飞行冲突解决分析

本节讨论了解决SFF ATC 系统中飞行冲突的方法。在SFF 模块中，解决航班冲突的方法不是通过冲突解决规则，而是通过航线规划过程中的冲突惩罚函数。

为了测试解决冲突的能力，选择两条航线Ti和Tj描述其能力：Ti的 起飞时间ti是351.6 s，Tj的起飞时间tj是94.7 s。如果飞机Ai直飞目的地，飞行航线Ti和Tj将会发生冲突。在Aj飞机航路规划过程中，系统预测飞行冲突，因此飞机Aj选择另一条路线作为最佳路线。仿真结果如图12 所示。

图12 两条3D 路线的避让示意图

从仿真结果可以看出，飞机Aj在与A i碰撞前改变了其计划路线Tj，因此与 Ai不会发生飞行冲突。SFF ATC 系统与自由飞行系统的不同之处在于，在自由飞行系统中，冲突解决在两架飞机注意到将发生碰撞时生效，而SFF ATC 系统则提前规划飞机的航线以避免碰撞。

4.3 重新规划路线分析

本次仿真测试了路线重新规划的功能。飞机在飞行过程中会出现航线重新规划问题。飞机 Ai的原始目的地是(xT，yT)，假设飞机Ai在tip 时刻变更为一个新的目的地(xT*，yT*)。

重新规划的航线如图13 所示，蓝线为飞机原规划的航线，红线为重新规划到新目的地的航线。

图13 路线重新规划示意图

在该航路重新规划仿真中，重新规划的航路正确到达目标目的地，满足安全距离和禁飞区约束。

4.4 与集中管制模式的对比

目前多机协同管制模式主要有集中管制模式和自由飞行模式两种。现有集中管制模式要求飞机必须通过固定的雷达管制点，以保证飞机飞行全程的安全性，但是其飞行距离上必然有所增加。而自由飞行模式则对飞机在空飞行的轨迹不做任何规定，飞行员可根据自己需要自由在空中选择飞行路径。当所有飞行员均协同配合采用最佳飞行路径时，所得到的飞行路径为半自由飞行路径。当各飞行员完全按照自己意愿飞行时，其随机性太大，不易做比较。因此，本节仅在半自由飞行和集中管理两种模式之间做对比。

本次仿真计划是在与第4.3 节仿真相同的条件下ATC 系统的飞机飞行路线。规划的结果如图14 所示。红星为与飞机通信的地面雷达塔，绿线为现有空管系统的飞机必须通过地面雷达塔的计划航线。

图14 传统ATC 和半自由ATC 规划路径对比

现有空管系统获得的规划航线飞行距离即绿线为582.83 km,SFF 空管系统获得的规划航线飞行距离为546.21 km。造成这种情况的主要原因是现有空管系统的飞机必须通过地面雷达塔，从而无法选择最优路径。

与现有的空管系统相比，SFF 空管系统的航路规划方法可以为飞机提供更短的飞行路线。50 条轨迹全部规划结果对比如表2 所示。相较于集中管理模式，半自由飞行模式能够平均降低飞行距离18.70%。

表2 规划航路对比表

5 结论

半自由飞行是本文提出的一种新的空中交通管制模式。“半自由飞行”集中了所有的信息并向每架飞机发送个性化的指挥和控制指令。在这种控制模式下，多航路规划是空中交通管制过程中的关键技术环节。通过数值模拟，可以得到以下结论。

1) SFF ATC 系统中的每架飞机都可以自由选择起飞和降落位置，并将计划发送给SFF ATC 系统，系统将在没有特殊情况下批准飞机的请求。

2)各飞机飞行距离最小的航线由空管系统规划，不允许飞机自主规划，从而减少全球飞行距离，保证系统安全。

3)航路规划方法可以避免飞机之间的飞行碰撞。

综上所述，SFF ATC 系统可以实现自由飞行系统的功能，每架飞机都能以最小的飞行距离飞到目的地。在飞行过程中，SFF ATC 系统与飞机保持联系，对飞机进行监督，并在飞机必须改变目的地时就重新规划的航线提供反馈。此外，SFF ATC 系统的通信方式保证了每架飞机都在空管系统的控制下，从而避免了空管系统缺乏监控的问题。

半自由飞行是短期内改善空中交通管制系统的一种可行方法。本文对半自由飞行及其路径规划方法进行了研究，证明了该方法在民用航空领域的可行性。半自由飞行可以作为空中交通集中管制模式向自由飞行模式过渡。在半自由飞行模式下，飞行员可以自由飞到任意目的地，但必须按照空管系统提供的计划路线飞行。一方面半自由飞行给了每个飞行员自由，另一方面空中交通管制系统仍然能够监督飞机。