一种改进的基于意图挖掘的航迹预测

摘要： 意图推断和航迹预测是提高空中交通容量的重要ATC工具，混合估计算法和意图推断算法相结合的基于意图的预测模型是比较崭新的用于长期航迹预测的算法。本文提出一种改进的基于意图的航迹预测算法。使用高分辨率聚类挖掘ADS-B历史航迹数据得到一条典型航迹，将典型航迹而不是传统的计划航迹用于提取意图信息，再与IMM算法结合完成航迹的预测。使用新疆地区真实的ADS-B历史航迹数据验证本文提出的算法的预测性能，仿真结果显示改进的预测算法具有更好的预测性能。

Abstract： Intent inference and trajectory prediction are important air traffic control （ATC） tools for enhanced air traffic capacity. The prediction model based on intention combined by hybrid estimation algorithm and intention inference algorithm is a new algorithm， which can be used to make long-term trajectory prediction. In this paper， an improved trajectory prediction algorithm based on intention is proposed. High-resolution clustering is used for mining historical ADS-B track data in order to obtain a typical trajectory. The typical trajectory is used for extract the intent information instead of the flight plan path. Then the intent information is combined with IMM algorithm to complete the prediction of the trajectory. The prediction performance of the proposed algorithm is tested using real ADS-B data from Xinjiang ATM Bureau. The simulation results show that the improved algorithm has a better prediction performance.

关键词： 高分辨率聚类；典型航迹；IMM算法；航迹预测

Key words： high resolution clustering；typical trajectory；IMM algorithm；trajectory prediction

中图分类号：V328.3 文献标识码：A 文章编号：1006-4311（2017）21-0092-06

0 引言

近年来空中交通密度快速增长，空中交通管制ATC（Air Traffic Control）的目标就是安全、有效的管理运行在全国空域系统中的航空器流量。为了达到这个目标，基于航迹预测算法的决策支持工具被不断研究和开发，因为交通咨询通告依赖航空器未来的航迹。通常，在这种集成系统环境下，飞行员和地面管制员共同决定航空器的未来航迹，一旦意图明确，航空器必须遵照这个意图飞行[1]。

大量的研究被投入到实现航迹预测中，航迹预测方法可被分为类：常规的预测方法、最坏情况的预测方法、概率型预测方法[2]。常规的航迹预测方法根据飞行计划给出未来航空器位置，这种方法没有考虑到航空器未来运行的不确定性，因此精确度会随着预测长度增加而降低或者预测的时间增大。最坏情况的预测方法在预测航迹过程中考虑了一系列假设的未来机动形式和最糟糕的情况。概率型方法通过模型的不确定性描述航空器未来轨迹的潜在变化，这种方法可以分为两种类型：在常规航迹上增加误差修正，或为未来航迹建立一套可能性模型，按照他们发生的概率计算。航空器未来运行的不确定性可以通过使用意图信息来降低，意图信息的提取问题被称为意图推断，并得到了广泛的关注[3]。传统的意图推断算法（Intent Inference Algorithm，IIA）通过建立航空器意图模型的离散集合，用轨迹相关度来确定哪个意图模型能最好地描述真实的航空器意图，IIA算法可以利增加从飞行员行为、飞行计划和环境信息获得的意图信息量[4]。但是这种方法复杂度较高，可能会出现推断的延迟，而且这种方法主要通过计划航迹推断，没有很好地跟踪航空器当前模型，可能会引起预测精度降低。

历史ADS-B数据是对飞行状态的可靠性记录，它包含影响航空器运行的所有可能因素，比如飞行计划的改变、飞行员倾向、天气状况等。这些信息可以被挖掘出来，用来分析航迹模式并用于航迹预测，提高预测准确度。本文使用高分辨率聚类的数据挖掘方法对ADS-B历史数据进行聚类分析，将得到的聚类航迹作为典型航迹。从典型航迹中提取意图信息，并将其与交互式多模型算法（Interacting Multiple Model，IMM）结合，最终得到改进的基于意图的航迹预测模型。

1 ADS-B数据挖掘及典型航迹

通过使用聚类算法，相同时空特征的航迹被聚为一个集群，我们将这个聚类集群的中心航迹定义为典型航迹，它代表了聚类航迹集群的一般模式。聚类航迹包含很多信息：航迹间的共同特征、产生原因等，这些隐藏的信息是可以用于推测未来飞行意图的重要信息。本节主要描述了如何用高分辨聚类的数据挖掘方法分析历史ADS-B数据并得到典型航迹。

1.1 航迹数据

ADS-B数据包含的信息有数据源识别信息、目标状态、ICAO 24位地址、时间、目标的经纬度、高度、速度信息、方向信息、数据链技术等，信息种类丰富；ADS-B设备体积小，便于安装，造价低，因此设备成本低；由于ADS-B的位置信息来源于GNSS卫星，数据精度更高且更新周期短，一般为1s/次；ADS-B的监视数据是通过开放式的广播方式向外界传送，并不针对某个特定的用户，数据获取较容易；当今数据时代，对ADS-B数据的分析并用于航迹预测具有重要意义。

1.1.1 ADS-B历史航迹数据格式

若有N条历史航迹组成一个历史航迹集L，即

L={L1，L2，…，Lk…，LN}（1）

其中Lk表示L中的第k条航迹。假设由n个航迹点组成则

Lk={m1，m2，…，mi，…，mn}（2）

其中mi表示航迹Lk上的第i个航迹点。每个航迹点由w个属性变量组成，则

mi={mi1，mi2，…，mij，…，miw}（3）

其中mij表示航迹点mi的第j个属性，我们通常关注航迹点的精度、纬度、高度及时间4个属性变量，此时mi可以表示为mi=（x，y，z，t）。

1.1.2 数据预处理

由于存在串扰、信号遮挡等情况，真实的航迹数据可能存在问题，应该针对不同的问题给出相应的预处理。本文选用新疆地区的ADS-B CAT021格式数据，主要存在3种问题：①干扰航迹：部分航班号一天内可能被分配执行大于一次的航行任务，即存在多与一条的航迹。不应只以航班号为依据从数据库里提取航迹，还要考虑24位IACO地址，运行时间，地面接收站IP地址等，排除干扰航迹，以增加航迹数据的准确性； ②航迹数据缺失：由于地形遮挡、数据串扰等问题，ADS-B报文可能出现丢包现象，因此出现个别甚至大量航迹点缺失。对于缺失数据点比较少的航迹可以采用插值方法补全航迹。但是航迹数据缺失严重会致使航迹特征不明显而不可用，在选取航迹时应该去除此类航迹；③数据项重复：表现为时间信息重复和位置信息重复，数据信息重复会影响其可用性，需要删除每条航迹中数据项重复的航迹点。

1.2 高分辨率聚类及典型航迹获取

传统的航迹聚类分析方法大多只能对位置信息进行聚类，时间信息不明确[5]。本节提出了一种以全时间序列聚类为核心的时空航迹聚类方法，如图1所示，主要思想是在每一采样时刻进行一次DBSCAN（Density-Based Spatial Clustering of Application with Noise）聚类。此过程需要考虑等间隔且小间隔采样时间面上空间位置的聚类效果，类似图像及信号处理中对空间及时间分辨率的定义，将其称为高分辨率聚类方法。

1.2.1 时间k-means聚类

飞机实际运行时，相同任务每天航班的速度和起飞时间可能不同，因此，可用运行时间也会不同，本文采用相对时间的处理方式：首先提取选用的所有航迹段的相同开始点和截止点，其次将时间基准（第一秒）定位到航迹开始点处，得到每段航迹相对运行时间，再采用时间k-means聚类的方法得到统一运行时间Tp。

k-means聚类又称快速聚类或动态聚类，聚类前需先根据具体问题确定分类数k，根据距离函数通过迭代过程将数据分入k个聚类中，使得评价聚类性能的准则函数达到最优[6]。

假设观测样本X中包含n个样本点即X={x1，x2，…，xn}，每个样本点用w个属性，本文采用欧氏距离（4）作为相似性的评价标准：

d（xi，xj）=■（xik-xjk）2■（4）

k-means算法评价聚类性能时采用误差平方和准则函数。假设X包含的k聚类子集为X1，X2，…，Xk，各个子集的样本点数量为n1，n2，…，nk，各个子集的均值代表点为m1，m2，…，mk，则误差平方和准则函数公式为：

E=■■ ■ p-m ■ 2（5）

1.2.2 时间归一及插值

为了能够使选用的所有航迹在时间全区间相似，需要进行时间归一化。假设第i天飞行时间Ti，其在t时刻的位置为Sit，飞行时间归一化到Tp后，飞机处于Sit位置的时刻变为t′，时间归一化公式[7]：

■=■（6）

虽然经过时间归一化航迹具备全时间区间相似特征，但是因为存在缺失的航迹点，并不是每条航迹在任意采样时刻都存在航迹点，而全时间序列DBSCAN聚类需要每一采样时间面上所有航班的航迹点都存在，可通过插值、重采样解决该问题。其一、采用三次样条插值补全缺失的航迹点；其二、进行重采样，采样周期T=4s，如此，既可降低计算量又可以满足高分辨率聚类对数据格式的要求。

图11和图12分别展示了改进前后两种方法的位置坐标和速度预测误差，可以看出改进后的算法具有更低的预测误差。

图13展示了IMM跟踪预测过程中各个时刻匀速直线运动模型CV、匀速转弯模型CT的模型概率变化情况，可以看出870～193s期间右转弯模型概率最大，1460～1512s期间左转弯模型概率增大，其它时刻主要取决于直线运动模型，与实际的运动情况相符。

4 结论

航迹预测是ATM应用的关键技术之一，本文引入了高分辨率聚类和典型航迹的概念，阐明了如何用高分辨率聚类的数据挖掘算法提取典型航迹。实验证明典型航迹与飞行计划轨迹相比包含更多的飞行信息、更能代表飞行意图。提出基于典型航迹的改进的预测算法。通过使用新疆地区真实的ADS-B数据仿真验证改进的算法的性能，仿真结果显示改进的基于典型航迹意图挖掘的航迹预测方法具有更好的预测性能。

参考文献：

[1]Nolan M. Fundamentals of air traffic control [M]. Cengage learning， 2010.

[2]殷允楠.空中交通流量统计预测技术研究[D].南京：南京航空航天大学，2010.

[3]Yepes J L， Hwang I， Rotea M. New algorithms for aircraft intent inference and trajectory prediction[J]. Journal of guidance， control， and dynamics， 2007， 30（2）： 370-382.

[4]Krozel J， Andrisani D. Intent inference and strategic path prediction[C]//AIAA Guidance， Navigation， and Control Conference and Exhibit. 2005： 6450.

[5]王涛波，黄宝军.基于4D航迹的模糊聚类分析[J].交通信息与安全，2013，31（180）：38-42.

[6]Tang X， Gu J， Shen Z， et al. A flight profile clustering method combining twed with K-means algorithm for 4D trajectory prediction[C]//Integrated Communication， Navigation， and Surveillance Conference （ICNS）， 2015. IEEE， 2015： S3-1-S3-9.

[7]躯d，潘薇.基于数据挖掘的四维飞行轨迹预测模型[J].计算机应用，2007，27（11）：2637-2639.

[8]Ester M， Kriegel H P， Sander J， et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Kdd. 1996， 96（34）： 226-231.

[9]Gariel M， Srivastava A N， Feron E. Trajectory clustering and an application to airspace monitoring[J]. IEEE Transactions on Intelligent Transportation Systems， 2011， 12（4）： 1511-1524.

[10]葛柏君.短期区域飞行流量预测问题研究[D].南京：南京航空航天大学，2008.

[11]Xi L， Jun Z， Yan B Z， et al. Simulation study of algorithms for aircraft trajectory prediction based on ADS-B technology[C]//System Simulation and Scientific Computing， 2008. ICSC 2008. Asia Simulation Conference-7th International Conference on. IEEE， 2008： 322-327.

[12]Song Y， Cheng P， Mu C. An improved trajectory prediction algorithm based on trajectory data mining for air traffic management[C]//Information and Automation （ICIA）， 2012 International Conference on. IEEE， 2012： 981-986.

[13]陆晶莹.高速高机动目标 IMM 跟踪算法研究 [D]. 南京：南京理工大学，2010.