基于K-近鄰的自由飛行沖突探測研究

趙元棣，孫 禾，王潔寧

(中國民航大學(xué)a.天津市空管運(yùn)行規(guī)劃與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室;b.空中交通管理研究基地，天津 300300)

1 引 言

隨著空中交通需求的不斷增加，導(dǎo)致空域資源緊張，空中交通異常擁擠，為民航業(yè)的發(fā)展帶來了巨大的挑戰(zhàn).為解決此問題，美國人威廉·克頓在1965年首次提出了“自由飛行”的概念，并在近些年受到越來越多的重視.美國航空無線電委員會(huì)(Radio Technical Commission for Aeronautics，RTCA)在1995年給出了“自由飛行”的定義［1］:自由飛行是在儀表飛行規(guī)則下的一種安全有效的飛行體系.在該體系中，飛行員可以更加靈活地選擇適合自己的航路和速度.

在自由飛行的條件下，航空器的飛行距離大幅度減少，不僅為航空公司節(jié)約了燃油消耗，還可以提高空域的利用率.與此同時(shí)，自由飛行也必然導(dǎo)致管制員的工作負(fù)荷增大.飛行航路和速度的不確定性使得管制員難以像固定航路飛行那樣事先判斷航空器之間是否存在沖突，只能通過實(shí)時(shí)計(jì)算航空器之間的距離來進(jìn)行沖突探測.因此，研究自由飛行條件下的沖突探測問題對(duì)于保障飛行安全、提高運(yùn)行效率起到了至關(guān)重要的作用［2］.近些年，國內(nèi)外已經(jīng)有許多學(xué)者對(duì)此問題進(jìn)行了研究，并取得了一些成果.Alliot等［3］討論了如何利用遺傳算法來解決空中交通管制中的沖突探測與解脫問題;Krozel等［4］采用最優(yōu)控制理論提出了一種針對(duì)兩架航空器在自由飛行條件下的沖突探測與解脫方法;Versteegt等［5］將動(dòng)態(tài)密度的概念引入沖突探測與解脫的研究領(lǐng)域，并提出了航空器沖突解脫次數(shù)最少(Minimised number of Aircraft Solve Conflicts，MASC)的方法.在國內(nèi)，靳學(xué)梅［6］針對(duì)兩架航空器的沖突探測問題，使用矢量法構(gòu)建了基于距離探測和時(shí)間探測的數(shù)學(xué)模型，并以此為基礎(chǔ)進(jìn)一步提出了針對(duì)多架航空器的沖突探測方法，用實(shí)例進(jìn)行了仿真驗(yàn)證.程麗媛［7］在靳學(xué)梅的研究基礎(chǔ)上，以航空器的質(zhì)心空間運(yùn)動(dòng)軌跡為模型，對(duì)多架航空器之間沖突群的探測進(jìn)行研究，并建立了數(shù)學(xué)模型.劉星等［8］應(yīng)用遺傳算法有效地解決了自由飛行條件下的飛行沖突探測與解脫問題，并且能盡量使航線接近理論上最省油的直線航線.

劉星等［9］和劉昕［10］均考慮到民用航空器在大部分時(shí)間內(nèi)都是在固定高度飛行，從而將三維立體問題簡化為二維平面問題，應(yīng)用二維Delaunay剖分方法從數(shù)據(jù)處理效率角度對(duì)自由飛行沖突探測問題進(jìn)行了研究.本文試圖將航空器的飛行沖突探測問題推廣到三維空間中進(jìn)行研究，然而三維Delaunay剖分方法具有計(jì)算復(fù)雜度高、易退化、對(duì)于非均勻分布數(shù)據(jù)較敏感等缺點(diǎn)，并不適合于本文研究內(nèi)容［9］.航空器在自由飛行條件下會(huì)呈現(xiàn)出位置不易確定、數(shù)量規(guī)模動(dòng)態(tài)變化等特點(diǎn)，對(duì)于沖突探測方法的計(jì)算效率和穩(wěn)定性的要求較高.本文將計(jì)算幾何中的K-近鄰方法引入自由飛行沖突探測問題，可以實(shí)時(shí)、快速、準(zhǔn)確地計(jì)算出每架航空器與其距離最近的K架航空器之間是否存在沖突，并通過仿真實(shí)驗(yàn)證明了本文方法的有效性和魯棒性.

2 K-近鄰方法

K-近鄰(K-Nearest Neighbor，KNN)方法最早是由Cover和Hart在1967年首次提出的一種非參數(shù)分類方法［11］.由于其具有簡單直觀、易于實(shí)現(xiàn)、對(duì)數(shù)據(jù)的噪聲和采樣密度不敏感等優(yōu)點(diǎn)，現(xiàn)已成為數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中的經(jīng)典方法之一.K-近鄰方法在原理上依賴于極限定理，其基本思想是:對(duì)于已知對(duì)象x，在度量空間內(nèi)搜索距離x最近的K個(gè)目標(biāo)對(duì)象，若這K個(gè)近鄰大多數(shù)屬于某一類別，則x也屬于該類別.當(dāng)K趨于無窮大時(shí)，K-近鄰方法逼近于 Bayes最優(yōu)分類方法［12］.由于 K-近鄰方法兼顧了計(jì)算效率與穩(wěn)定性，特別適合于在動(dòng)態(tài)環(huán)境下連續(xù)搜索K個(gè)距離最近的目標(biāo)對(duì)象，因此目前已被廣泛應(yīng)用于模式識(shí)別［13，14］、文本分類［15，16］、交通流預(yù)測［17］等領(lǐng)域.

由于本文所研究的沖突探測問題是假定在自由飛行條件下進(jìn)行的，航空器的數(shù)量及其空間位置均呈現(xiàn)出動(dòng)態(tài)不確定性，需要沖突探測方法具有較高的計(jì)算效率和較強(qiáng)的穩(wěn)定性.本文利用兼?zhèn)溥@兩種特點(diǎn)的K-近鄰方法較好地解決了自由飛行條件下的沖突探測問題.設(shè)三維空間點(diǎn)集為P={P1，…，Pn}，對(duì)于其中每一點(diǎn)Pi，計(jì)算與其歐氏距離最近的K個(gè)點(diǎn)Pi，1，…，Pi，K，稱為Pi的 K-近鄰，圖1所示為K=5時(shí)的情況.

圖1 三維點(diǎn)集K-近鄰Fig.1 KNN of 3D point set

3 基于K-近鄰的沖突探測方法

3.1 基本思想

假設(shè)在某指定空域內(nèi)，所有航空器在某時(shí)刻的空間位置坐標(biāo)構(gòu)成三維空間點(diǎn)集P，本文利用其中每個(gè)點(diǎn)的K-近鄰對(duì)未來一段時(shí)間內(nèi)的沖突及潛在沖突進(jìn)行快速、有效地探測.其基本思想是:將二次雷達(dá)實(shí)時(shí)獲得的航空器空間位置坐標(biāo)按照不同時(shí)段存儲(chǔ)起來，并計(jì)算各時(shí)段內(nèi)每架航空器的K-近鄰，根據(jù)沖突判定規(guī)則搜索每架航空器與其K-近鄰之間的距離即可判斷當(dāng)前時(shí)段內(nèi)是否存在沖突或潛在沖突.

這種方法避免了對(duì)整個(gè)空域內(nèi)的每對(duì)航空器進(jìn)行距離探測，只需探測每架航空器與其周圍的有限架航空器之間的距離是否滿足沖突判定規(guī)則，從而大幅度節(jié)省了計(jì)算時(shí)間.此外，在不同時(shí)段內(nèi)，當(dāng)空域內(nèi)的部分航空器位置發(fā)生改變時(shí)，無需針對(duì)整個(gè)空域內(nèi)所有航空器進(jìn)行距離數(shù)據(jù)更新，只需更新與其相關(guān)聯(lián)的航空器的距離信息即可，在提高沖突探測效率的同時(shí)，增加了算法的可延續(xù)性.

3.2 方法描述

基于K-近鄰的思想，本文方法的具體步驟如下:

(1)在某時(shí)段內(nèi)，利用二次雷達(dá)記錄整個(gè)空域內(nèi)所有航空器的空間位置坐標(biāo)，生成三維空間點(diǎn)集P={P1，…，Pn}，其中Pi=(xi，yi，zi)，i=1，…，n.

(2)對(duì)每一個(gè)點(diǎn)Pi∈P，計(jì)算與其歐式距離最近的K個(gè)點(diǎn)Pi，1，…，Pi，K∈P，并根據(jù)距離按照升序排列.當(dāng)對(duì)P中的所有點(diǎn)均完成上述K-近鄰計(jì)算后，即可通過全部歐式距離生成一個(gè)n×K維的距離矩陣D={dij}，其中第i行第j列元素dij表示第i架航空器與距其第j位近的航空器之間的歐氏距離.

(3)根據(jù)事先給定的沖突判定規(guī)則，將其中所定義的沖突間隔與潛在沖突間隔作為閾值，搜索距離矩陣D中所有滿足上述規(guī)則的距離，進(jìn)而判斷出存在沖突或潛在沖突的航空器對(duì).

3.3 與傳統(tǒng)方法的比較分析

在實(shí)際運(yùn)行中，空域內(nèi)航空器的空間位置會(huì)隨著時(shí)間推移而發(fā)生變化，因此為了實(shí)現(xiàn)對(duì)航空器進(jìn)行全程飛行沖突探測，需將飛行全程所需的時(shí)間劃分為若干個(gè)時(shí)間段，在每個(gè)時(shí)間段內(nèi)實(shí)時(shí)更新航空器的三維空間坐標(biāo)，直至該航空器飛出此空域.在此動(dòng)態(tài)情況下，利用全空間計(jì)算方法和三維Delaunay剖分方法需在每個(gè)時(shí)間段均對(duì)全部航空器進(jìn)行重新計(jì)算，效率較低且可延續(xù)性較差，而本文方法只需局部更新距離矩陣中的部分信息即可完成沖突的重新探測.

此外，若空域內(nèi)的航空器數(shù)量規(guī)模較大，利用全空間計(jì)算方法和三維Delaunay剖分方法的計(jì)算復(fù)雜度較高，而且其中有相當(dāng)規(guī)模的計(jì)算對(duì)沖突探測結(jié)果是沒有影響的(如距離較遠(yuǎn)的航空器對(duì)之間的距離)，本文通過自適應(yīng)地計(jì)算K值可以盡量避免對(duì)結(jié)果“無影響”的距離計(jì)算，從而提高了計(jì)算效率和穩(wěn)定性.

4 算例

利用Matlab軟件實(shí)現(xiàn)本文方法，并對(duì)自由飛行條件下的沖突探測進(jìn)行模擬仿真實(shí)驗(yàn).假設(shè)空域范圍為100 km×100 km，隨機(jī)生成25架航空器的空間位置、航向和速度等信息.本文判定兩架航空器是否存在沖突或潛在沖突的規(guī)則是:當(dāng)它們的水平距離小于最低水平間隔標(biāo)準(zhǔn)10 km，且垂直距離小于最低垂直間隔標(biāo)準(zhǔn)0.3 km時(shí)，意味著它們已經(jīng)發(fā)生沖突;當(dāng)水平間隔大于10 km而小于15 km時(shí)，表示兩架航空器存在潛在沖突.

4.1 沖突及潛在沖突探測結(jié)果

首先假設(shè)某時(shí)刻空域內(nèi)有25架在不同高度層飛行的航空器.在確定其空間位置坐標(biāo)后，計(jì)算每架航空器的K-近鄰(取K=5)，結(jié)果如表1所示.其中，每個(gè)單元格括號(hào)中的第一個(gè)數(shù)字代表航空器序號(hào)，第二個(gè)數(shù)字代表它們之間的距離.例如，第1行第1列的單元格中(22，12.3)表示A1航空器與A22航空器之間的距離為12.3 km.對(duì)于每架航空器，其K-近鄰是按照距離由小到大排列的，以方便飛行沖突的探測.

利用前面提到的沖突判定規(guī)則對(duì)表1進(jìn)行搜索，可以得到存在沖突以及潛在沖突的航空器對(duì)，具體結(jié)果為:

存在沖突的航空器對(duì)包括(A6，A12，7.8)，(A9，A10，8.1);

存在潛在沖突的航空器對(duì)包括(A1，A22，12.3)，(A3，A23，13.1)，(A11，A13，14.6).

圖2所示為從不同角度展示的沖突探測結(jié)果，其中實(shí)線段表示存在沖突的航空器對(duì)，虛線段表示存在潛在沖突的航空器對(duì).

表1 航空器的K-近鄰計(jì)算結(jié)果Table 1 KNN calculation result of aircraft

圖2 航空器沖突探測結(jié)果Fig.2 Conflict detection result of aircraft

當(dāng)有另外一架航空器飛出(或飛入)此空域時(shí)，只需在表1中刪除(或增加)一行，并修改表1中的部分距離信息，即可快速、準(zhǔn)確探測是否由此航空器帶來沖突風(fēng)險(xiǎn).例如，在上述算例中，假設(shè)A1航空器飛出此空域，只需刪除表1中的第1行數(shù)據(jù)，清空第15行第1列以及第22行第1列的單元格，并將每行剩余的距離數(shù)據(jù)向前遞補(bǔ)即可進(jìn)行重新探測.

4.2 本文方法與傳統(tǒng)方法的對(duì)比

針對(duì)上述算例，在實(shí)驗(yàn)環(huán)境為2.4 GHz CPU，4 GB內(nèi)存的PC機(jī)上，分別采用全空間計(jì)算方法和三維Delaunay剖分方法進(jìn)行沖突探測計(jì)算，均可得到與表1相同的計(jì)算結(jié)果.然而，三種方法的計(jì)算復(fù)雜度和速度卻有較大的區(qū)別.表2所列為每種方法的計(jì)算復(fù)雜度，以及針對(duì)不同規(guī)模的航空器進(jìn)行沖突探測所需的距離判斷次數(shù)和計(jì)算時(shí)間.相比于兩種傳統(tǒng)的計(jì)算方法，本文方法在計(jì)算復(fù)雜度和計(jì)算速度方面均有顯著的優(yōu)勢.而且航空器的數(shù)量規(guī)模越大，本文方法在計(jì)算效率方面的優(yōu)勢就越明顯.

表2 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)Table 2 Experimental data statistics

對(duì)上述25架航空器進(jìn)行沖突探測時(shí)，所需距離判斷次數(shù)的示意圖如圖3所示.若兩架航空器需要將它們之間的距離與沖突判定規(guī)則進(jìn)行比較，則將它們用一條線段相連.由圖3可以直觀地看出本文方法與傳統(tǒng)方法相比大幅度地減少了距離判斷次數(shù)，從而節(jié)省了計(jì)算時(shí)間，提高了計(jì)算效率.

圖3 與傳統(tǒng)方法對(duì)比結(jié)果Fig.3 Comparison result with traditional methods

4.3 K值的自適應(yīng)計(jì)算

如前文所述，本文方法在進(jìn)行沖突探測時(shí)需要進(jìn)行Kn次距離判斷，因此K值的選取將直接影響計(jì)算復(fù)雜度.為了盡量減少計(jì)算時(shí)間，本文采用自適應(yīng)的方法計(jì)算K值.首先，根據(jù)空域內(nèi)航空器的數(shù)量將K賦值為一個(gè)較小的數(shù)值，然后利用K-近鄰方法進(jìn)行沖突探測.若某航空器與其第K個(gè)近鄰存在沖突或潛在沖突，意味著與其存在沖突的航空器可能不止K個(gè)，因此將K值增大ΔK至K'，再通過計(jì)算該航空器的K'－近鄰進(jìn)行沖突探測，直至其與第K'個(gè)近鄰不存在沖突為止.一般來說，利用K的初始賦值即可探測出全部的沖突;即使出現(xiàn)上述情況，本文方法也只需對(duì)距離矩陣進(jìn)行局部調(diào)整，最大限度地節(jié)省了計(jì)算時(shí)間.例如，假設(shè)空域內(nèi)有120架航空器，利用本文方法求得距離矩陣，其中A39航空器、A92航空器均與其第K(K=5)個(gè)近鄰存在潛在沖突，如表3所示.將K自適應(yīng)增大至K'(K'=6)，重新計(jì)算這兩架航空器的K'－近鄰，發(fā)現(xiàn)其與第K'個(gè)近鄰不存在潛在沖突，則計(jì)算結(jié)束，如表4所示.

表3 K-近鄰對(duì)應(yīng)的距離矩陣Table 3 Distance matrix for KNN

表4 K'－近鄰對(duì)應(yīng)的距離矩陣Table 4 Distance matrix for K'NN

從上述仿真結(jié)果可以看出，本文所采用的K-近鄰方法避免全局搜索，只在每架航空器周圍進(jìn)行局部搜索就能有效地探測出在自由飛行條件下的航空器群之間的飛行沖突.在不同時(shí)間段內(nèi)，當(dāng)航空器的位置發(fā)生變化時(shí)，只需局部修改距離矩陣，即可實(shí)時(shí)、準(zhǔn)確地探測飛行沖突，大幅度節(jié)省了計(jì)算時(shí)間，為管制員進(jìn)行沖突解脫創(chuàng)造條件.

5 研究結(jié)論

(1)本文采用K-近鄰方法對(duì)在三維空間中自由飛行的航空器進(jìn)行沖突探測，通過理論分析與仿真實(shí)驗(yàn)，表明本文方法能夠快速、有效地探測出存在沖突或潛在沖突的航空器.此外，當(dāng)航空器位置發(fā)生變化時(shí)，只需局部修改距離矩陣即可重新探測，大幅度提高了計(jì)算效率.

(2)對(duì)于K值的確定，本文提出了其自適應(yīng)計(jì)算方法，當(dāng)K的初始賦值不能探測到全部的沖突時(shí)，通過適當(dāng)增加K值、局部調(diào)整距離矩陣即可解決該問題.

(3)本文方法只能對(duì)航空器進(jìn)行沖突探測，而無法給出具體的解脫策略，這也是本文的未來發(fā)展方向.

［1］Final report of RTCA task force 3-free flight implementation［R］.Washington DC:RTCA Inc，1995.

［2］周向華.沖突探測與解脫技術(shù)在未來空中交通管理中的應(yīng)用［D］.南京:南京航空航天大學(xué).2009.［ZHOU X H.Research on technologies of the conflict detection and resolution for future air traffic management［D］.Nanjing:Nanjing University of Aeronautics and Astronautics，2009.］

［3］Alliot J M，Gruber H，Joly G，et，et al.Geneticalgorithms for solving air traffic control conflicts［C］//The Ninth Conference on Artificial Intelligence for Applications，1993:338-344.

［4］Krozel J，Mueller T，Hunter G.Free flight conflict detection and resolution analysis［C］//AIAA Guidance，Navigation and Control Conference，San Diego，California USA，July，1996.

［5］Versteegt H H，Visser H G.Traffic complexity based conflictresolution［J］.Air Traffic Control Quarterly，2003，11(2):103-122.

［6］靳學(xué)梅，自由飛行行空域中多機(jī)沖突探測與解脫技術(shù)研究［D］.南京:南京航空航天大學(xué).2004.［JIN X M.The research of technologies on the conflict detection and resolution among multi-aircraft in free flight airspace［D］.Nanjing:Nanjing University of Aeronautics and Astronautics，2004.］

［7］程麗媛.自由飛行空域中多機(jī)沖突探測與解脫技術(shù)研究［D］.南京:南京航空航天大學(xué).2005.［CHENG L Y.Research on technologies of the conflict detection and resolution among multi-aircraft in free flight airspace［D］.Nanjing:Nanjing University of Aeronautics and Astronautics，2005.］

［8］劉星，胡明華，韓松臣.自由飛條件下的沖突探測與解脫方法［J］.南京理工大學(xué)學(xué)報(bào)，2002，26(增刊):56-60.［LIU X，HU M H，HAN S C.The study on flight conflicts detection and solving［J］.Journal of Nanjing University of Science and Technology，2002，26(Supp):56-60.］

［9］劉星，韓松臣.用于自由飛行沖突探測的Delaunay方法［J］.數(shù)據(jù)采集與處理，2002，17(4):446-449.［LIU X，HAN S C.Delaunay method for free flightconflict detection［J］. Journal of Data Acquisition ＆ Processing，2002，17(4):446-449.］

［10］劉昕.基于計(jì)算幾何方法的飛行沖突檢測［J］.電子測量技術(shù)，2007，30(4):87-89.［LIU X.Conflict detection in free flight based on computational geometry method［J］. Electronic Measurement Technology，2007，30(4):87-89.］

［11］T M Cover，P E Hart.Nearest neighbor pattern classification［J］.IEEE Transactions on Information Theory，1967，13(1):21-27.

［12］劉曉紅.基于支持向量機(jī)和K近鄰的聯(lián)合分類研究［D］.哈爾濱:哈爾濱工程大學(xué).2011.［LIU X H.Research on the joint classification based on support vector machine and K-nearest neighbor［D］.Harbin:Harbin Engineering University，2011.］

［13］周而重，逄玉俊.一種改進(jìn)的K近鄰法在模式識(shí)別中的應(yīng)用［J］.沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，25(4):475-478.［ZHOU E Z，PANG Y J.Application of an improved K-nearest neighbor approach in pattern recognition［J］. Journalof Shenyang NormalUniversity(NaturalScience)，2007，25(4):475-478.］

［14］V Vaidehi，S Vasuhi，R Kayalvizhi，et al.Person authentication using face recognition［C］//Proceedings of the World Congress on Engineering and Computer Science，2008.

［15］徐曉艷.基于K近鄰算法的中文文本分類研究［D］.合肥:安徽大學(xué).2012.［XU X Y.Research of Chinese text classification based on K neighbor algorithm［D］.Hefei:Anhui University，2012.］

［16］魯婷.K-近鄰中文文本分類方法的研究［D］.合肥:合肥工業(yè)大學(xué).2010.［LU T.The research on K-nearest neighbor Chinese text categorization algorithm［D］. Hefei:HeFei University of Technology，2012.］

［17］于濱，鄔珊華，王明華，等.K近鄰短時(shí)交通流預(yù)測模型［J］.交通運(yùn)輸工程學(xué)報(bào)，2012，12(2):105-111.［YU B，WU S H，WANG M H，et al.K-nearest neighbor model of short-term traffic flow forecast［J］.Journal of Traffic and Transportation Engineering，2012，12(2):105-111.］

［18］楊小運(yùn).約束Delaunay三角剖分算法的研究與應(yīng)用［D］.武漢:武漢科技大學(xué).2012.［YANG X Y.The research and application of the delaunay triangulations algorithm［D］. Wuhan:Wuhan University of Science and Technology，2012.］