一種改進的基于意圖挖掘的航跡預測

焦衛東++楊東玲++朱麗++楊麗萍

摘要： 意圖推斷和航跡預測是提高空中交通容量的重要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，如此，既可降低計算量又可以滿足高分辨率聚類對數據格式的要求。

1.2.3 全時間序列DBSCAN聚類

為了在聚類過程中明確時間變量，本文采用全時間序列聚類，沿著航跡運動方向，對相同時間間隔采樣的每一時刻層面上航跡點進行一次DBSCAN聚類，得到每一采樣時刻的聚類簇集合。

DBSCAN算法是一種基于高密度聯通區域的聚類算法，可以有效處理數據集中的噪聲數據，對噪聲具有抵抗性。而在聚類過程中偏離程度比較大的航跡會降低聚類的準確性，相當于噪聲數據，所以用DBSCAN算法對航跡數據做聚類分析，可以有效規避偏離航跡對聚類結果的影響。DBSCAN算法細節參照文獻[8-9]。圖2（a）為全時間序列DBSCAN聚類示意圖，其中（i=0，1，2，…）表示t時刻的DBSCAN聚類簇。

1.2.4 全時間序列聚類中心遍歷

遍歷搜索可以找到如圖2（a）所有時刻聚類集群中包含的交集，如圖2（b）所示，具體步驟為：

①將t1時刻的簇集合C■■（包含L1，L2和L3）定為候選聚類簇V1；

②將t2時刻的簇集合C■■與V1比較，當它們含有相同的對象時，計算它們的交集并更新V1為此交集；

③取t3時刻C■■與V1的交集，并更新V1，當在t3時刻發現新的簇集合C■■時定位候選聚類簇V2。

④以此類推最終得到的所有時刻簇集合的交集V1，稱為目標簇集合。

1.2.5 典型航跡獲取

根據典型航跡的定義，對目標簇集合內的航跡求均值即是典型航跡。

2 改進的航跡預測算法

概率型航跡預測的一個常用且具有較強前瞻性的方法是通過混合估計算法IMM與意圖推斷算法相結合的基于意圖的航跡預測算法 [3，10-12]，包括狀態估計模塊、意圖推斷模塊和IMM航跡預測模塊。IMM算法是卡爾曼濾波法對應的一種全面自適應濾波算法，它是一種N個卡爾曼濾波器同時工作的跟蹤預測算法，針對不同的目標運動狀態應用不同的卡爾曼模型濾波器，對濾波器的輸入、輸出進行了巧妙的結合實現交互。IMM算法原理圖如圖3所示，它是一種遞歸循環算法，每一次循環過程包括以下四大歩：輸入交互；卡爾曼濾波；模型概率更新；輸出交互組合[13]。

以上方法主要用飛行計劃來推測意圖信息，更新IMM概率轉移矩陣。需要注意的是典型航跡是從飛機飛過的真實歷史航跡路徑中提取得到，而飛行計劃代表的是飛機預測飛過的粗略的飛行意圖。典型航跡包括飛行計劃信息和一些其它的因素，比如：飛行計劃改變，飛行員傾向，氣象因素和可能引起飛行航跡改變的空域結構。因此用典型航跡代替飛行計劃航跡來提取航跡意圖，將會提高預測精度。圖4展示改進的算法框圖，飛行計劃被通過聚類歷史航跡數據得到的典型航跡取代。

3 實驗仿真

仿真使用從地窩堡國際機場（ZWWW）飛往首都國際機場（ZBAA）的航班在新疆范圍內的ADS-B歷史航跡數據，選用的航跡均處于巡航階段，涉及的航班號有：CSN6903、CSN6909、CSN6932、CHH7146、CHH7246、CHH7346、CCA1296、CCA1292、CCA1276、CCA1902、CCA1294、CCA1478。

3.1 高分辨率聚類的仿真

3.1.1 時間K-means聚類仿真結果

對歷史航跡集中的所有航跡運行時間進行k-means聚類。分類數目k=3，將運行時間分為三類：時間值偏小類、中間類和時間值偏大類，結果如圖5所示。計算中間類內時間的均值作為統一的運行時間，因為較小時間和較大的時間都會對求取的Tp的準確性產生較大影響，得Tp=2448s。

得到Tp后根據公式（6）對每條航跡時間進行歸一化，然后再進行插值和重采樣，以便進行后續全時間序列DBSCAN聚類。

3.1.2 全時間序列DBSCAB聚類、遍歷及典型航跡生成仿真結果

重采樣時間T=4s，即每四秒執行一次DBSCAN聚類任務，根據選用數據的長度可知需要在612個時間層面上分別執行聚類。圖6展示的是T=1197s 采樣時刻所有航班點分布及聚類結果，圖中“+”表示聚類中心，點“o”表示邊界點，“.”表示噪聲點。由圖可知在不提前確定分類數的情況下，DBSCAN算法可以輕松地區分開偏離較大的航跡點，發現航跡點高密度區域。

遍歷搜索612個時刻的聚類簇，求交集，得到最終的航跡聚類簇，計算航跡聚類簇的均值航跡作為典型航跡，高分辨率聚類結果時空數據展示形式如圖7所示。

圖8所示為經緯坐標下的高分辨率聚類結果，展示了歷史航跡、典型航跡和計劃航跡，從圖可以看出真實飛行航跡與飛行計劃航跡總是存在一定程度的偏差，統計顯示典型航跡比飛行計劃更能代表真實的飛行意圖。

3.2 改進的基于意圖的航跡預測算法的仿真

以2014年11月19日航班CHH7346在新疆上空運行的ADS-B航跡數據為例驗證改進的基于意圖的航跡預測算法，并與改進前的算法比較。以這段數據的第一個點作為起始航路點，從ADS-B數據中獲取的起始位置坐標為（91.2510°，42.8519°），初始速度為974.61海里/小時，初始航向為91.9°。將航跡數據進行坐標轉換為笛卡爾坐標系下的數據。航跡點的采樣間隔T=1s，從典型航跡上進行意圖提取后得知，870-893s處于勻速右轉彎階段，角速度？棕=？仔/360，1460～1512s處于左轉彎階段，角速度？棕=-2？仔/360，其它時間段處于勻速直線運動階段。

進行蒙特卡洛仿真實驗，圖9展示算法改進前后預測結果（其中圖10是圖9的藍色虛橢圓標注的局部放大圖）。顯然，改進的算法具有更高的預測精度，因為與計劃航跡相比，運行航跡更接近典型航跡。統計顯示大部分運行航跡更接近典型航跡，因此改進的基于意圖算法具有更好的預測效果。

圖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]吳鹍，潘薇.基于數據挖掘的四維飛行軌跡預測模型[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.