基于分組的飛行器短期沖突對(duì)快速檢測(cè)算法

關(guān) 靜，張精衛(wèi)

（1.中國(guó)民航大學(xué)理學(xué)院，天津 300300；2.浙江久立特材科技股份有限公司，浙江 湖州 313028）

在空中交通管制系統(tǒng)中，為了維護(hù)飛行器在空中的飛行秩序，保證飛行安全，相關(guān)決策部門必須根據(jù)不同的飛行環(huán)境，制定不同的飛行間隔標(biāo)準(zhǔn)，同時(shí)要求飛行員及管制人員必須嚴(yán)格按照相關(guān)的飛行標(biāo)準(zhǔn)執(zhí)行[1]。近年來，隨著民用航空及通用航空的快速發(fā)展，飛行密度不斷增加，有效防止飛行器間發(fā)生碰撞，保證飛行器能夠安全到達(dá)指定位置，以及保障飛行器能夠遵循空中交通秩序使交通暢通成為空中交通管制的主要任務(wù)。而對(duì)飛行器的沖突檢測(cè)[2]是保障飛行器和其他財(cái)產(chǎn)安全的重要因素，為空中交通管制工作提供決策支持。

國(guó)內(nèi)外很多學(xué)者對(duì)飛行沖突實(shí)時(shí)檢測(cè)算法進(jìn)行了相關(guān)研究。Paielli等[3]提出了自由飛行情況下的短期沖突概率解決方案；Prandini等[4]和Hu等[5]提出基于航空器隨機(jī)運(yùn)動(dòng)概率模型，并考慮隨機(jī)擾動(dòng)的沖突概率計(jì)算方法；Lygeros等[6]研究了結(jié)合飛行計(jì)劃、航空器受氣候變化影響情況下的沖突檢測(cè)算法；Hwang等[7]進(jìn)一步完善了航空器航跡的跟蹤算法，在交互多模算法（IMM,interactive multiple models algorithm）的基礎(chǔ)上提出殘差均值交互多模算法 (RM-MM,residual-mean interacting multiple model algorithm)；李丹等[8]提出一種基于布朗運(yùn)動(dòng)的概率型空中交通沖突探測(cè)算法；王運(yùn)鋒等[9]提出航空器的位置差與速度差矢量?jī)?nèi)積小于0的航跡對(duì)才具有潛在沖突的理論，并根據(jù)安全飛行間隔規(guī)定，采用線性預(yù)測(cè)法對(duì)其進(jìn)行沖突的有效性確認(rèn)；王超等[10]提出飛機(jī)之間的模糊空間接近度概念及一種模糊沖突檢測(cè)方法；徐偉等[11-12]提出了具有機(jī)動(dòng)性檢測(cè)的交互式UKF算法和卡爾曼濾波的分層檢測(cè)算法；龔宏偉等[13]考慮了雷達(dá)數(shù)據(jù)的誤差及氣流等隨機(jī)因素影響，將卡爾曼濾波引入飛行器短期沖突檢測(cè)中，實(shí)現(xiàn)了更精確的預(yù)報(bào)；劉洋等[14]提出了一種概率型的短期沖突探測(cè)算法。邊園飛等[15]在研究解決飛行器碰撞檢測(cè)的有關(guān)問題中，通過減少參與檢測(cè)的飛行器對(duì)，即減少檢測(cè)次數(shù)來改進(jìn)檢測(cè)算法。

以上研究是從改進(jìn)飛行器之間的沖突檢測(cè)方法著手，提高單次檢測(cè)的效率，并通過減少虛警和漏警的情況，解決沖突盲警告、軌跡不變等問題，提高算法的實(shí)用性。通過對(duì)上述研究分析，提出了一種基于分組的飛行器沖突對(duì)快速檢測(cè)算法，研究處于同一飛行高度層的飛行器之間的飛行沖突檢測(cè)問題。該算法依據(jù)飛行器最小水平安全間隔，對(duì)沖突對(duì)檢測(cè)次數(shù)進(jìn)行優(yōu)化，在飛行器短期沖突檢測(cè)中具有很強(qiáng)的實(shí)用性。

1 沖突對(duì)檢測(cè)的快速算法

1.1 相關(guān)概念

定義1設(shè)S為飛行沖突待檢測(cè)空域，Ai（i=1，2，…）是第i個(gè)邊長(zhǎng)為2l的正方形，若滿足：

1）Ai∩Aj=，i≠j且 i，j=1，2，…；

2）A1∪A2∪…∪An∪…?S。

空域的劃分是將整個(gè)待檢測(cè)的空域S進(jìn)行離散化的操作：劃分之后的空域S被離散成若干個(gè)邊長(zhǎng)為2l的正方形待檢測(cè)空域Ai（i=1，2，…）。若將待檢測(cè)的目標(biāo)空域S放入一個(gè)平面直角坐標(biāo)系中，劃分結(jié)果如圖1所示。

圖1 正方形劃分覆蓋集Fig.1 Square divided cover set

定義 2對(duì)于點(diǎn)（x，y），其中 x∈[0，2l），y∈[0，2l），如果(x，y)滿足下列條件：

2）存在一個(gè) Ai，k∈（ki=1，2，…；k=1，2，…）滿足對(duì)于任意的點(diǎn)（x0，y0），x0≥x，y0≥y，即（x，y）是 Ai，k的左下頂點(diǎn)。則稱(x，y)為S的正方形劃分覆蓋集族。

正方形劃分覆蓋集族如圖2所示。

圖2 正方形劃分覆蓋集族Fig.2 Square divided cover set family

定義3對(duì)空域S上的任意兩點(diǎn)（px，py）和（qx，qy），若滿足

則稱點(diǎn)（px，py）和點(diǎn)（qx，qy）為S上的一個(gè)沖突對(duì)，記作（px，py）?（qx，qy）。

定義4對(duì)空域S中的全部沖突對(duì)組成的集合，稱為沖突對(duì)集，記作（S）。

定理1任取則對(duì)S上任意的沖突對(duì)（px，p）y?（qx，q）y，存在一個(gè)邊長(zhǎng)為2l的正方形A，其中使得（px，p）y∈A且（qx，q）y∈A。

證明 由于（px，p）y∈S，1為S上的一個(gè)正方形劃分覆蓋集，故存在一個(gè)A1∈1，使得（px，p）y∈A1。

如果（qx，q）y∈A1，則 A1即滿足定理結(jié)論。否則，由于，所以（qx，q）y在B（ii=1，2，…，8）標(biāo)示的范圍中，標(biāo)示形式如圖 3 所示，其中Bi為A1周圍外展1個(gè)單位的第i個(gè)區(qū)域。由1?可知：

若（qx，q）y∈B1∪B5，則存在A3∈3，使得（px，p）y∈A3，且（qx，q）y∈A3；

若（qx，q）y∈B3∪B7，則存在A2∈2，使得（px，p）y∈A2，且（qx，q）y∈A2；

若（qx，q）y∈B2∪B4∪B6∪B8，則存在 A4∈4，使得（px，py）∈A4，且（qx，qy）∈A4。

綜上，定理得以證明。

定理2對(duì)任意的其中滿足

圖 3 （qx，qy）位置圖Fig.3 （qx，qy）position

證明由于，故沖突對(duì)一致，即（S）。

1.2 哈希函數(shù)的構(gòu)造

由定理2可知，只要對(duì)4個(gè)正方形劃分覆蓋集中的全部正方形區(qū)域分別進(jìn)行沖突對(duì)探測(cè)，即可無(wú)遺漏的探測(cè)空域S中的所有沖突對(duì)。為了進(jìn)行4個(gè)正方形劃分覆蓋集中的全部正方形區(qū)域的沖突探測(cè)，首先要將空域S中的探測(cè)目標(biāo)按照所在的正方形分組。對(duì)于每個(gè)探測(cè)目標(biāo)，在4個(gè)正方形劃分覆蓋集中，分別存在1個(gè)正方形包含該目標(biāo)，因此需要將該目標(biāo)分別歸入4個(gè)組，并在這4個(gè)組中進(jìn)行沖突探測(cè)。

為了能快速的進(jìn)行分組，算法需要構(gòu)造4個(gè)不同的哈希函數(shù)，使得哈希函數(shù)的值與正方形一一對(duì)應(yīng)。

不妨假設(shè)，任意的點(diǎn)（x，y）∈S，x∈[0，2ml]，y∈[0，2ml]，其中m為正整數(shù)，則可以構(gòu)造4個(gè)哈希函數(shù)分別為

其中：[]表示取整；n，p 為整數(shù)，且 n ＞（m+1），p ＞ n2。

顯然，如上所構(gòu)造的4個(gè)哈希函數(shù)可映射到4個(gè)正方形劃分覆蓋集中的全部正方形，且在空域S內(nèi)不重復(fù)。

1.3 基于哈希表的改進(jìn)算法

計(jì)算過程中，通常用以哈希值為索引的哈希表[16-17]來實(shí)現(xiàn)快速檢索。檢測(cè)中將空域S內(nèi)待測(cè)目標(biāo)的分組按照前文所述的哈希值建立哈希表，則在一個(gè)完整探測(cè)周期內(nèi)，可以按照以下步驟進(jìn)行沖突探測(cè)。

步驟1獲取待測(cè)空域內(nèi)所有飛行器信息，將其位置信息映射到S內(nèi)的點(diǎn)（x，y），并分別代入4個(gè)哈希函數(shù)中得到哈希值，根據(jù)所得的哈希值在哈希表上快速檢索到對(duì)應(yīng)的目標(biāo)組，將飛行器的信息分別插入到這4個(gè)目標(biāo)組中，即實(shí)現(xiàn)待探測(cè)目標(biāo)的分組。

步驟2對(duì)每個(gè)目標(biāo)組進(jìn)行沖突探測(cè)，即兩兩進(jìn)行距離判斷，找到各目標(biāo)組的所有沖突對(duì)。

步驟3合并各個(gè)目標(biāo)組探測(cè)得到的全部沖突對(duì)信息，即除掉其中可能重復(fù)的沖突對(duì)。

步驟4輸出合并的結(jié)果，即為待測(cè)空域S內(nèi)的所有沖突對(duì)。

2 數(shù)值算例及分析

2.1 算法實(shí)現(xiàn)

算法的開發(fā)環(huán)境：VisualStudio2005Express。飛行器、飛行器集合、沖突對(duì)等數(shù)據(jù)模型可方便地用C#語(yǔ)言面向?qū)ο蟮姆绞絹肀硎荆瑢?shí)現(xiàn)算法所需的4個(gè)哈希函數(shù)，并以SortedDictionary泛型類實(shí)現(xiàn)哈希表。SortedDictionary泛型類不僅能夠?qū)⒐Ｖ底鳛殛P(guān)鍵字與飛行器集合數(shù)據(jù)建立對(duì)應(yīng)關(guān)系，還對(duì)哈希值關(guān)鍵字進(jìn)行了排序，這樣使關(guān)鍵字的檢索效率大幅提升?？紤]到哈希值的范圍，用64位有符號(hào)整數(shù)作為哈希值的類型。為不失一般性，假設(shè)檢測(cè)空域長(zhǎng)寬均不超過5 000 km，最小安全間隔按10 km計(jì)算，即l=10，分別取n=500，p=300 000可滿足算法要求。

為了進(jìn)行分析比較，實(shí)驗(yàn)程序中也設(shè)計(jì)和實(shí)現(xiàn)了傳統(tǒng)的沖突對(duì)檢測(cè)算法，該算法對(duì)全部的飛行器進(jìn)行逐對(duì)檢測(cè)，這樣能夠保證其輸出的沖突對(duì)結(jié)果是準(zhǔn)確可靠的。

檢測(cè)空域中的飛行器位置采用隨機(jī)的方式生成樣本，隨機(jī)樣本散點(diǎn)圖如圖4所示。樣本數(shù)據(jù)可以由任何工具生成并記錄在ASCII編碼的數(shù)據(jù)文件中，以便在算法運(yùn)行時(shí)加載和使用。

考慮到算法中執(zhí)行次數(shù)最多的是一對(duì)飛行器之間的沖突檢測(cè)，為了更準(zhǔn)確地評(píng)估算法的效率，算法中增加了計(jì)數(shù)器以記錄實(shí)際計(jì)算距離和判斷沖突的次數(shù)。

圖4 一組500個(gè)飛行器樣本的散點(diǎn)圖Fig.4 Scatter plot of a group of 500 aircraft samples

2.2 結(jié)果及分析

經(jīng)過對(duì)不同樣本的多次仿真實(shí)驗(yàn)，基于分組的飛行器沖突對(duì)快速檢測(cè)算法所輸出的沖突對(duì)與傳統(tǒng)算法輸出的沖突對(duì)完全一致，從而驗(yàn)證了算法的正確性。

改變飛行器位置樣本的規(guī)模，可觀察到快速算法和傳統(tǒng)算法判斷次數(shù)的變化規(guī)律。在表1中列出了100～1 000個(gè)樣本的判斷次數(shù)記錄，其判斷次數(shù)與樣本個(gè)數(shù)關(guān)系曲線，如圖5所示。

表1 飛行器樣本個(gè)數(shù)與判斷次數(shù)記錄表Tab.1 Record of aircraft sample and judgment times

圖5 飛行器樣本個(gè)數(shù)與判斷次數(shù)的關(guān)系圖Fig.5 Aircraft sample number vs.judgment times

可見，在空域固定，檢測(cè)目標(biāo)分組數(shù)也固定的情況下，隨著空域中飛行器數(shù)目的增加，傳統(tǒng)算法和快速算法的判斷次數(shù)都有所增加，但快速算法的判斷次數(shù)的增長(zhǎng)速度要遠(yuǎn)慢于傳統(tǒng)算法。故相對(duì)于傳統(tǒng)算法，待測(cè)空域中飛行器數(shù)目越多，快速算法的優(yōu)勢(shì)越明顯。

如果空域的大小不一致，則按照前文描述的情況，由于目標(biāo)的最小安全距離不變，檢測(cè)目標(biāo)的分組數(shù)也會(huì)變化，按照快速算法要求可相應(yīng)地調(diào)整n和p的值，再進(jìn)行計(jì)算。實(shí)驗(yàn)采用隨機(jī)生成的方式，分別制作了不同尺寸空域中的飛行器位置樣本，且為了研究需要，樣本的數(shù)量都設(shè)置為500個(gè)。經(jīng)過實(shí)驗(yàn)，分別記錄了傳統(tǒng)算法和快速算法的判斷次數(shù)，記錄結(jié)果如表2所示，隨著檢測(cè)空域的寬度變化，判斷次數(shù)的變化曲線如圖6所示。

表2 空域大小與判斷次數(shù)記錄表Tab.2 Record of airspace area and judgment times

圖6 空域大小與判斷次數(shù)的關(guān)系圖Fig.6 Airspace area vs.judgment times

可見，在空域中飛行器數(shù)目不變的情況下，空域增大時(shí)，傳統(tǒng)算法的判斷次數(shù)不會(huì)變化，而快速算法的判斷次數(shù)卻顯著減少，即空域越大，快速算法的優(yōu)勢(shì)越明顯。

綜上，快速算法在應(yīng)對(duì)大量檢測(cè)目標(biāo)、大范圍空域的情況下相對(duì)于逐個(gè)判斷的傳統(tǒng)算法能夠顯著減少判斷次數(shù)，大大縮短檢測(cè)時(shí)間，提高檢測(cè)效率，且結(jié)果準(zhǔn)確無(wú)遺漏。

快速算法能夠在判斷次數(shù)上體現(xiàn)出上述優(yōu)勢(shì)，是由于對(duì)檢測(cè)目標(biāo)進(jìn)行了合理的分組。不妨假設(shè)空域S中有k個(gè)待測(cè)目標(biāo)，則不難求出按照傳統(tǒng)算法，判斷次數(shù)應(yīng)為

假設(shè)1個(gè)正方形劃分覆蓋集用m個(gè)正方形覆蓋了空域S，則m可視為空域S尺寸的關(guān)鍵指標(biāo)。按照快速算法的要求，每個(gè)正方形中平均包含的檢測(cè)目標(biāo)數(shù)量為個(gè)，易知單個(gè)分組的平均判斷次數(shù)為次，而按照算法要求，總共有4m個(gè)分組，因此總判斷次數(shù)為

綜上可看出：當(dāng)空域增大時(shí)（即m增大），快速算法相對(duì)于傳統(tǒng)算法判斷次數(shù)會(huì)迅速減少，這主要是由于空域增大時(shí)，如果檢測(cè)目標(biāo)分布均勻，則距離就會(huì)拉大，從而最終通過分組只有極少的目標(biāo)之間還需進(jìn)行判斷；而空域不變時(shí)，若檢測(cè)目標(biāo)數(shù)量足夠大，則快速算法帶來的效率提升僅與空域的尺寸有關(guān)，空域越大，提升越明顯，這主要是由于對(duì)檢測(cè)目標(biāo)進(jìn)行了分組，而如前文所述，按照快速算法要求進(jìn)行的分組并不會(huì)造成沖突對(duì)遺漏。

3 結(jié)語(yǔ)

結(jié)合算例的仿真模擬將基于分組的飛行器沖突對(duì)快速檢測(cè)算法與傳統(tǒng)算法相比較，驗(yàn)證了快速檢測(cè)算法能夠在無(wú)遺漏檢測(cè)的基礎(chǔ)上，進(jìn)一步提高檢測(cè)的效率，提高飛行沖突檢測(cè)的實(shí)時(shí)性。同時(shí)在解決虛警、沖突盲警告和軌跡不變等問題時(shí)，在沖突檢測(cè)算法中選用判斷參與檢測(cè)的飛行器是否存在沖突風(fēng)險(xiǎn)的方法變得越來越復(fù)雜的情形下，快速檢測(cè)算法的優(yōu)勢(shì)將會(huì)更加突出。