一種改進(jìn)的基于意圖挖掘的航跡預(yù)測

焦衛(wèi)東++楊東玲++朱麗++楊麗萍

摘要： 意圖推斷和航跡預(yù)測是提高空中交通容量的重要ATC工具，混合估計算法和意圖推斷算法相結(jié)合的基于意圖的預(yù)測模型是比較嶄新的用于長期航跡預(yù)測的算法。本文提出一種改進(jìn)的基于意圖的航跡預(yù)測算法。使用高分辨率聚類挖掘ADS-B歷史航跡數(shù)據(jù)得到一條典型航跡，將典型航跡而不是傳統(tǒng)的計劃航跡用于提取意圖信息，再與IMM算法結(jié)合完成航跡的預(yù)測。使用新疆地區(qū)真實(shí)的ADS-B歷史航跡數(shù)據(jù)驗(yàn)證本文提出的算法的預(yù)測性能，仿真結(jié)果顯示改進(jìn)的預(yù)測算法具有更好的預(yù)測性能。

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.

關(guān)鍵詞： 高分辨率聚類；典型航跡；IMM算法；航跡預(yù)測

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

中圖分類號：V328.3 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2017）21-0092-06

0 引言

近年來空中交通密度快速增長，空中交通管制ATC（Air Traffic Control）的目標(biāo)就是安全、有效的管理運(yùn)行在全國空域系統(tǒng)中的航空器流量。為了達(dá)到這個目標(biāo)，基于航跡預(yù)測算法的決策支持工具被不斷研究和開發(fā)，因?yàn)榻煌ㄗ稍兺ǜ嬉蕾嚭娇掌魑磥淼暮桔E。通常，在這種集成系統(tǒng)環(huán)境下，飛行員和地面管制員共同決定航空器的未來航跡，一旦意圖明確，航空器必須遵照這個意圖飛行[1]。

大量的研究被投入到實(shí)現(xiàn)航跡預(yù)測中，航跡預(yù)測方法可被分為類：常規(guī)的預(yù)測方法、最壞情況的預(yù)測方法、概率型預(yù)測方法[2]。常規(guī)的航跡預(yù)測方法根據(jù)飛行計劃給出未來航空器位置，這種方法沒有考慮到航空器未來運(yùn)行的不確定性，因此精確度會隨著預(yù)測長度增加而降低或者預(yù)測的時間增大。最壞情況的預(yù)測方法在預(yù)測航跡過程中考慮了一系列假設(shè)的未來機(jī)動形式和最糟糕的情況。概率型方法通過模型的不確定性描述航空器未來軌跡的潛在變化，這種方法可以分為兩種類型：在常規(guī)航跡上增加誤差修正，或?yàn)槲磥砗桔E建立一套可能性模型，按照他們發(fā)生的概率計算。航空器未來運(yùn)行的不確定性可以通過使用意圖信息來降低，意圖信息的提取問題被稱為意圖推斷，并得到了廣泛的關(guān)注[3]。傳統(tǒng)的意圖推斷算法（Intent Inference Algorithm，IIA）通過建立航空器意圖模型的離散集合，用軌跡相關(guān)度來確定哪個意圖模型能最好地描述真實(shí)的航空器意圖，IIA算法可以順利增加從飛行員行為、飛行計劃和環(huán)境信息獲得的意圖信息量[4]。但是這種方法復(fù)雜度較高，可能會出現(xiàn)推斷的延遲，而且這種方法主要通過計劃航跡推斷，沒有很好地跟蹤航空器當(dāng)前模型，可能會引起預(yù)測精度降低。

歷史ADS-B數(shù)據(jù)是對飛行狀態(tài)的可靠性記錄，它包含影響航空器運(yùn)行的所有可能因素，比如飛行計劃的改變、飛行員傾向、天氣狀況等。這些信息可以被挖掘出來，用來分析航跡模式并用于航跡預(yù)測，提高預(yù)測準(zhǔn)確度。本文使用高分辨率聚類的數(shù)據(jù)挖掘方法對ADS-B歷史數(shù)據(jù)進(jìn)行聚類分析，將得到的聚類航跡作為典型航跡。從典型航跡中提取意圖信息，并將其與交互式多模型算法（Interacting Multiple Model，IMM）結(jié)合，最終得到改進(jìn)的基于意圖的航跡預(yù)測模型。

1 ADS-B數(shù)據(jù)挖掘及典型航跡

通過使用聚類算法，相同時空特征的航跡被聚為一個集群，我們將這個聚類集群的中心航跡定義為典型航跡，它代表了聚類航跡集群的一般模式。聚類航跡包含很多信息：航跡間的共同特征、產(chǎn)生原因等，這些隱藏的信息是可以用于推測未來飛行意圖的重要信息。本節(jié)主要描述了如何用高分辨聚類的數(shù)據(jù)挖掘方法分析歷史ADS-B數(shù)據(jù)并得到典型航跡。

1.1 航跡數(shù)據(jù)

ADS-B數(shù)據(jù)包含的信息有數(shù)據(jù)源識別信息、目標(biāo)狀態(tài)、ICAO 24位地址、時間、目標(biāo)的經(jīng)緯度、高度、速度信息、方向信息、數(shù)據(jù)鏈技術(shù)等，信息種類豐富；ADS-B設(shè)備體積小，便于安裝，造價低，因此設(shè)備成本低；由于ADS-B的位置信息來源于GNSS衛(wèi)星，數(shù)據(jù)精度更高且更新周期短，一般為1s/次；ADS-B的監(jiān)視數(shù)據(jù)是通過開放式的廣播方式向外界傳送，并不針對某個特定的用戶，數(shù)據(jù)獲取較容易；當(dāng)今數(shù)據(jù)時代，對ADS-B數(shù)據(jù)的分析并用于航跡預(yù)測具有重要意義。

1.1.1 ADS-B歷史航跡數(shù)據(jù)格式

若有N條歷史航跡組成一個歷史航跡集L，即

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

其中Lk表示L中的第k條航跡。假設(shè)由n個航跡點(diǎn)組成則

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

其中mi表示航跡Lk上的第i個航跡點(diǎn)。每個航跡點(diǎn)由w個屬性變量組成，則

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

其中mij表示航跡點(diǎn)mi的第j個屬性，我們通常關(guān)注航跡點(diǎn)的精度、緯度、高度及時間4個屬性變量，此時mi可以表示為mi=（x，y，z，t）。

1.1.2 數(shù)據(jù)預(yù)處理

由于存在串?dāng)_、信號遮擋等情況，真實(shí)的航跡數(shù)據(jù)可能存在問題，應(yīng)該針對不同的問題給出相應(yīng)的預(yù)處理。本文選用新疆地區(qū)的ADS-B CAT021格式數(shù)據(jù)，主要存在3種問題：①干擾航跡：部分航班號一天內(nèi)可能被分配執(zhí)行大于一次的航行任務(wù)，即存在多與一條的航跡。不應(yīng)只以航班號為依據(jù)從數(shù)據(jù)庫里提取航跡，還要考慮24位IACO地址，運(yùn)行時間，地面接收站IP地址等，排除干擾航跡，以增加航跡數(shù)據(jù)的準(zhǔn)確性； ②航跡數(shù)據(jù)缺失：由于地形遮擋、數(shù)據(jù)串?dāng)_等問題，ADS-B報文可能出現(xiàn)丟包現(xiàn)象，因此出現(xiàn)個別甚至大量航跡點(diǎn)缺失。對于缺失數(shù)據(jù)點(diǎn)比較少的航跡可以采用插值方法補(bǔ)全航跡。但是航跡數(shù)據(jù)缺失嚴(yán)重會致使航跡特征不明顯而不可用，在選取航跡時應(yīng)該去除此類航跡；③數(shù)據(jù)項重復(fù)：表現(xiàn)為時間信息重復(fù)和位置信息重復(fù)，數(shù)據(jù)信息重復(fù)會影響其可用性，需要刪除每條航跡中數(shù)據(jù)項重復(fù)的航跡點(diǎn)。

1.2 高分辨率聚類及典型航跡獲取

傳統(tǒng)的航跡聚類分析方法大多只能對位置信息進(jìn)行聚類，時間信息不明確[5]。本節(jié)提出了一種以全時間序列聚類為核心的時空航跡聚類方法，如圖1所示，主要思想是在每一采樣時刻進(jìn)行一次DBSCAN（Density-Based Spatial Clustering of Application with Noise）聚類。此過程需要考慮等間隔且小間隔采樣時間面上空間位置的聚類效果，類似圖像及信號處理中對空間及時間分辨率的定義，將其稱為高分辨率聚類方法。

1.2.1 時間k-means聚類

飛機(jī)實(shí)際運(yùn)行時，相同任務(wù)每天航班的速度和起飛時間可能不同，因此，可用運(yùn)行時間也會不同，本文采用相對時間的處理方式：首先提取選用的所有航跡段的相同開始點(diǎn)和截止點(diǎn)，其次將時間基準(zhǔn)（第一秒）定位到航跡開始點(diǎn)處，得到每段航跡相對運(yùn)行時間，再采用時間k-means聚類的方法得到統(tǒng)一運(yùn)行時間Tp。

k-means聚類又稱快速聚類或動態(tài)聚類，聚類前需先根據(jù)具體問題確定分類數(shù)k，根據(jù)距離函數(shù)通過迭代過程將數(shù)據(jù)分入k個聚類中，使得評價聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)[6]。

假設(shè)觀測樣本X中包含n個樣本點(diǎn)即X={x1，x2，…，xn}，每個樣本點(diǎn)用w個屬性，本文采用歐氏距離（4）作為相似性的評價標(biāo)準(zhǔn)：

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

k-means算法評價聚類性能時采用誤差平方和準(zhǔn)則函數(shù)。假設(shè)X包含的k個聚類子集為X1，X2，…，Xk，各個子集的樣本點(diǎn)數(shù)量為n1，n2，…，nk，各個子集的均值代表點(diǎn)為m1，m2，…，mk，則誤差平方和準(zhǔn)則函數(shù)公式為：

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

1.2.2 時間歸一及插值

為了能夠使選用的所有航跡在時間全區(qū)間相似，需要進(jìn)行時間歸一化。假設(shè)第i天飛行時間Ti，其在t時刻的位置為Sit，飛行時間歸一化到Tp后，飛機(jī)處于Sit位置的時刻變?yōu)閠′，時間歸一化公式[7]：

■=■（6）

雖然經(jīng)過時間歸一化航跡具備全時間區(qū)間相似特征，但是因?yàn)榇嬖谌笔У暮桔E點(diǎn)，并不是每條航跡在任意采樣時刻都存在航跡點(diǎn)，而全時間序列DBSCAN聚類需要每一采樣時間面上所有航班的航跡點(diǎn)都存在，可通過插值、重采樣解決該問題。其一、采用三次樣條插值補(bǔ)全缺失的航跡點(diǎn)；其二、進(jìn)行重采樣，采樣周期T=4s，如此，既可降低計算量又可以滿足高分辨率聚類對數(shù)據(jù)格式的要求。

1.2.3 全時間序列DBSCAN聚類

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

DBSCAN算法是一種基于高密度聯(lián)通區(qū)域的聚類算法，可以有效處理數(shù)據(jù)集中的噪聲數(shù)據(jù)，對噪聲具有抵抗性。而在聚類過程中偏離程度比較大的航跡會降低聚類的準(zhǔn)確性，相當(dāng)于噪聲數(shù)據(jù)，所以用DBSCAN算法對航跡數(shù)據(jù)做聚類分析，可以有效規(guī)避偏離航跡對聚類結(jié)果的影響。DBSCAN算法細(xì)節(jié)參照文獻(xiàn)[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比較，當(dāng)它們含有相同的對象時，計算它們的交集并更新V1為此交集；

③取t3時刻C■■與V1的交集，并更新V1，當(dāng)在t3時刻發(fā)現(xiàn)新的簇集合C■■時定位候選聚類簇V2。

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

1.2.5 典型航跡獲取

根據(jù)典型航跡的定義，對目標(biāo)簇集合內(nèi)的航跡求均值即是典型航跡。

2 改進(jìn)的航跡預(yù)測算法

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

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

3 實(shí)驗(yàn)仿真

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

3.1 高分辨率聚類的仿真

3.1.1 時間K-means聚類仿真結(jié)果

對歷史航跡集中的所有航跡運(yùn)行時間進(jìn)行k-means聚類。分類數(shù)目k=3，將運(yùn)行時間分為三類：時間值偏小類、中間類和時間值偏大類，結(jié)果如圖5所示。計算中間類內(nèi)時間的均值作為統(tǒng)一的運(yùn)行時間，因?yàn)檩^小時間和較大的時間都會對求取的Tp的準(zhǔn)確性產(chǎn)生較大影響，得Tp=2448s。

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

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

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

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

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

3.2 改進(jìn)的基于意圖的航跡預(yù)測算法的仿真

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

進(jìn)行蒙特卡洛仿真實(shí)驗(yàn)，圖9展示算法改進(jìn)前后預(yù)測結(jié)果（其中圖10是圖9的藍(lán)色虛橢圓標(biāo)注的局部放大圖）。顯然，改進(jìn)的算法具有更高的預(yù)測精度，因?yàn)榕c計劃航跡相比，運(yùn)行航跡更接近典型航跡。統(tǒng)計顯示大部分運(yùn)行航跡更接近典型航跡，因此改進(jìn)的基于意圖算法具有更好的預(yù)測效果。

圖11和圖12分別展示了改進(jìn)前后兩種方法的位置坐標(biāo)和速度預(yù)測誤差，可以看出改進(jìn)后的算法具有更低的預(yù)測誤差。

圖13展示了IMM跟蹤預(yù)測過程中各個時刻勻速直線運(yùn)動模型CV、勻速轉(zhuǎn)彎模型CT的模型概率變化情況，可以看出870～193s期間右轉(zhuǎn)彎模型概率最大，1460～1512s期間左轉(zhuǎn)彎模型概率增大，其它時刻主要取決于直線運(yùn)動模型，與實(shí)際的運(yùn)動情況相符。

4 結(jié)論

航跡預(yù)測是ATM應(yīng)用的關(guān)鍵技術(shù)之一，本文引入了高分辨率聚類和典型航跡的概念，闡明了如何用高分辨率聚類的數(shù)據(jù)挖掘算法提取典型航跡。實(shí)驗(yàn)證明典型航跡與飛行計劃軌跡相比包含更多的飛行信息、更能代表飛行意圖。提出基于典型航跡的改進(jìn)的預(yù)測算法。通過使用新疆地區(qū)真實(shí)的ADS-B數(shù)據(jù)仿真驗(yàn)證改進(jìn)的算法的性能，仿真結(jié)果顯示改進(jìn)的基于典型航跡意圖挖掘的航跡預(yù)測方法具有更好的預(yù)測性能。

參考文獻(xiàn)：

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

[2]殷允楠.空中交通流量統(tǒng)計預(yù)測技術(shù)研究[D].南京：南京航空航天大學(xué)，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]吳鹍，潘薇.基于數(shù)據(jù)挖掘的四維飛行軌跡預(yù)測模型[J].計算機(jī)應(yīng)用，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]葛柏君.短期區(qū)域飛行流量預(yù)測問題研究[D].南京：南京航空航天大學(xué)，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]陸晶瑩.高速高機(jī)動目標(biāo) IMM 跟蹤算法研究 [D]. 南京：南京理工大學(xué)，2010.