蘇志剛, 符笑嫻, 郝敬堂

(1. 中國民航大學中歐航空工程師學院, 天津 300300; 2. 中國民航大學智能信號與圖像處理天津市重點實驗室, 天津 300300; 3. 福建通航航空產業(yè)有限公司, 福建 福州 350000)

?

基于動態(tài)三角剖分的潛在沖突篩選方法

蘇志剛1,2, 符笑嫻1,3, 郝敬堂1

(1. 中國民航大學中歐航空工程師學院, 天津 300300; 2. 中國民航大學智能信號與圖像處理天津市重點實驗室, 天津 300300; 3. 福建通航航空產業(yè)有限公司, 福建 福州 350000)

摘要：圍繞動態(tài)Delaunay三角剖分(dynamic delaunay triangulation,DDT)方法難以對空域動態(tài)三角剖分中產生的反轉三角形實現穩(wěn)定局部更新問題,提出以順序的點刪除與點增加的局部更新方式替代反轉三角形的局部更新方式的改進方法。實驗結果表明,改進的DDT方法獲得的潛在沖突航空器數目與空域內航空器密度無關,且具有更低的局部更新時間復雜度和穩(wěn)健性。改進的DDT方法更穩(wěn)健,更適用于空管指揮系統(tǒng)的潛在沖突篩選任務。

關鍵詞：空中交通管理; 沖突檢測; 動態(tài)Delaunay三角剖分; 移動點集; 動態(tài)更新

0引言

近年來,隨著經濟的飛速發(fā)展,民用航空器總量迅速增加,使得航空器運行空域變得越來越擁擠,加之人為、天氣、故障等因素的影響,航空器間空中沖突、甚至空中相撞風險日益增大。例如:1996年沙特與哈薩克斯坦的客機在空中相撞,導致300多人遇難。2002年德國與俄羅斯的客機在空中相撞,機上70多人遇難。

地面空管指揮系統(tǒng)中的短期沖突告警(short term conflict alert,STCA)子系統(tǒng)[1]可以逐對判斷航空器間突破安全間隔標準的風險[2-4],對存在危險接近或相撞可能性的航空器給出相應的警示,協(xié)助管制員對空域內航空器進行調度、管理。隨著航空器數目的增大,STCA子系統(tǒng)計算復雜度將以平方量級增長。為有效地降低系統(tǒng)計算復雜度,提高短期沖突檢測的可靠性、實時性,STCA子系統(tǒng)進行沖突檢測前需要對潛在沖突進行篩選[5-6]。

距離門限法是一種經典的潛在沖突篩選方法,以航空器間的距離為準則篩選潛在沖突對,可以在一定程度上減少STCA負荷。然而隨著空中航空器數量的增多,特別是在終端區(qū)域,航空器密度加大,以航空器間距離為基礎的距離門限法需要跟蹤更多的潛在沖突對。近年來,有學者將圖形學的Delaunay三角剖分技術應用于潛在沖突篩選處理[6-9],使得潛在沖突對篩選數量與空域內航空器密度關系不大,從而降低了系統(tǒng)計算復雜度與空域內航空器數目之間的關聯(lián)。

空域內航空器的移動特征,使學者將移動點的Delaunay三角剖分技術應用于空管領域[7-10]。文獻[7]將快拍式Delaunay三角剖分(snapshot Delaunay triangulation,SDT)用于潛在沖突篩選。SDT方法需要周期地根據航空器位置信息進行Delaunay三角剖分,沒有利用刷新前后航空器位置關系的繼承性,因此,其計算復雜度較高。動能Delaunay三角剖分(kinetic Delaunay triangulation,KDT)方法[8,10]根據移動點的速度、位置信息,以連續(xù)時間的方式預測三角網格發(fā)生拓撲變化的時刻,僅在發(fā)生拓撲變化的時刻對發(fā)生拓撲變化的局部進行三角剖分更新。KDT方法解決了空間三角剖分的拓撲結構的繼承問題,可以有效地降低系統(tǒng)預選的復雜度,但對拓撲結構變化時刻的解算會引入額外計算量,當存在大量拓撲變化時,相應引入的復雜度較大[11-12]。動態(tài)Delaunay三角剖分(dynamic Delaunay triangulation,DDT)方法[9]檢測在離散時間點處的拓撲變化,對局部進行三角剖分更新。DDT方法與KDT方法相比,減少了拓撲結構變化時刻解算的計算量。文獻[9]所提出的DDT方法可以有效地解決航空器進入、離開或位置更新等情況下的空域Delaunay三角剖分的動態(tài)更新問題,但當空域Delaunay三角剖分的拓撲結構發(fā)生較大變化時,如存在反轉三角形的情況時,該方法無法有效地完成空域Delaunay三角剖分的局部更新,甚至可能陷入死循環(huán)[13]。

本文將在文獻[9]的DDT方法基礎上,針對反轉三角形的存在導致DDT方法不穩(wěn)定問題,提出一種可以有效解決反轉三角形存在時的局部更新的方法,使得改進的DDT方法更適于應用到短期沖突檢測的篩選處理中。

1空域Delaunay三角剖分

當航空器在航路上飛行時,航空器間的短期沖突檢測主要是針對同一高度層的航空器進行的,因此將空域中同一高度層的航空器看作離散點集,并依據Delaunay三角剖分準則,使得剖分后三角形的外接圓內不包含除頂點處航空器以外的任意航空器,形成以航空器為頂點的不均勻的三角形網格,如圖1所示。由圖1可見,空域內的航空器以最近鄰的三個航空器形成三角形,連接航空器的線段(三角形的邊)均不相交,且與遠處的航空器不直接發(fā)生聯(lián)系。這個特點與空管指揮系統(tǒng)中的潛在沖突航空器的特征相似,因此,可以利用Delaunay三角剖分所獲得的空域內航空器的拓撲結構,并以此作為潛在沖突篩選手段。

圖1　空域Delaunay三角剖分

空域Delaunay三角剖分的初始化就是根據系統(tǒng)中航空器的初始位置,按照靜態(tài)離散點集的方式對其進行Delaunay三角剖分?？沼駾elaunay三角剖分的初始化可以采用分治算法、逐點插入法、三角網生長法等經典算法實現,本文采用逐點插入法。逐點插入法的起始需要獲得包含全部離散點集的凸多邊形,然后采用逐點插入的方式進行Delaunay三角剖分。為降低尋找凸多邊形的復雜度,可將關注空域的四角設置4個虛擬點,進而形成包含空域全部航空器的凸多邊形,而且執(zhí)行逐點插入法即可完成空域的初始Delaunay三角剖分。

2拓撲結構的動態(tài)更新

空域內航空器的運行將引起空域三角網格的改變,由于航空器的軌跡的連續(xù)性,航空器間的拓撲結構呈現出緩變特點,使得空域Delaunay三角剖分具有相對穩(wěn)定性。對于空域的三角網格,在緩變過程中出現不滿足Delaunay三角剖分準則的三角網格也只發(fā)生在局部的,而非整體性的。DDT方法就是根據空域內航空器的增、減及位置變化,對空域的初始Delaunay三角剖分進行局部動態(tài)更新,實現空域Delaunay三角剖分的動態(tài)更新的目的。

空域內出現新增航空器時,可以采用點插入技術對空域內局部Delaunay三角剖分進行更新[14]。首先檢索出外接圓包含新增航空器的三角形,刪除相應三角形,形成凸多邊形。將凸多邊形的頂點與新增航空器點相連接即完成局部Delaunay三角剖分。假設需要判斷出現在點P4處的航空器是否位于ΔP1P2P3的外接圓內。根據點P1、P2、P3和P4的橫、縱坐標xi和yi(i=1,2,3,4)可以定義矩陣

(1)

假設P1、P2、P3為逆時針排列,若C1234的行列式|C1234|>0,則點P4在ΔP1P2P3的外接圓內,若行列式|C1234|<0,則點P4在ΔP1P2P3的外接圓外[15]。由于三角形頂點的排列順、逆時針判斷較為不便,因此引入輔助點P5,使其位于P1P2的延長線上,且坐標為(x5,y5)=(2x2-x1,2y2-y1)。顯然輔助點P5一定位于ΔP1P2P3的外接圓外。所以,若點P4在ΔP1P2P3的外接圓內,判斷準則

(2)

必然成立。

若空域內某航空器飛離時,由于該點的消失,使得空域Delaunay三角剖分的局部出現空腔,而且該空腔有可能不是凸多邊形,直接對其三角剖分可能出現交叉的邊。可以采用凸耳權值的點刪除算法進行維護[16]。

航空器運動引起空域三角形緩變,出現局部三角形不再滿足Delaunay三角剖分準則,即原有的外接圓內出現了其他航空器。進入三角形外接圓的航空器與該三角形構成兩個共邊三角形結構,利用局部優(yōu)化程序(local optimization procedure,LOP)可以實現局部拓撲更新[13,17]。

3對反轉三角形的局部更新

前面的DDT方法可以實現對空域內航空器間拓撲結構的基本動態(tài)維護,然而,當存在位置變化較大的航空器、或存在尺度較小的三角形時會出現三角形反轉的可能性。三角形反轉即為該三角形的頂點排列的順、逆時針順序發(fā)生改變,如圖2所示。圖2中點A在前后兩個時刻的位置變化,使得三角網格頂點ABC由順時針方向轉變?yōu)槟鏁r針方向。反轉ΔABC有存在使其周邊的三角形不再滿足Delaunay三角剖分準則,如圖2(b)的陰影區(qū)域。采用LOP處理已經無法獲得正確的Delaunay三角剖分,需要新的局部動態(tài)維護方案。

圖2　反轉三角形網格對局部的影響

實現對反轉三角形的局部拓撲更新的前提是需要定位反轉三角形。判斷是否存在反轉三角形的基礎是檢測三角形頂點的排列方向是否發(fā)生改變。定義在第n時刻三角網格頂點矩陣

(3)

式中,xi(n)和yi(n)分別為三角形第i(i=1,2,3)個頂點Pi在第n時刻的橫、縱坐標。如果三角形的頂點P1、P2和P3是按順時針排列,則三角形頂點矩陣T(n)的行列式|T(n)|<0,反之則|T(n)|>0。因此,三角形頂點排列方向是否發(fā)生改變可由式(4)判斷。

(4)

式(4)表明根據相鄰時刻的三角形頂點矩陣行列式的值是否異號可以判斷三角形是否為反轉三角形。遍歷空域內全部三角形,檢索出所有反轉三角形。

反轉三角形確定后,還需要進一步確定反轉點。反轉點是指進入反轉三角形的共邊三角形內部的反轉三角形的頂點,如圖2所示的頂點A。反轉點鄰近離散點的局部拓撲結構發(fā)生急劇變化,需要進行重新Delaunay三角剖分。對于反轉三角形,可以存在3個與其共邊的三角形,因此需要根據反轉點與共邊三角形的關系確定反轉點。

判斷某點在三角形內部的方法可采用內角和法、同向法、重心法等方法,本文采用計算效率較高的重心法。假設判斷ΔP1P2P3的頂點P1是否為反轉點,點P1所對應的共邊三角形為ΔP2P3P4,需要判斷下一時刻點P1是否落在ΔP2P3P4內。定義矩陣

(5)

(6)

(7)

利用式(5)～式(7)可得

(8)

(9)

式中,(·)-1表示求倒數操作。因此,若點P1落在共邊ΔP2P3P4內需滿足

(10)

若式(10)不成立,則說明點P1未落在共邊ΔP2P3P4內。

由于航空器間安全距離的限制,航空器的單次位置變化量通常小于Delaunay剖分后的三角形尺度,反轉點一般只落在反轉三角形的共邊三角形內。反轉點在短時間內跨越多個三角形,落在非共邊三角形內的可能性非常小,本文不予考慮。

由于反轉點的存在,反轉三角形周邊的部分三角形需要重新進行局部Delaunay三角剖分。本局部的Delaunay剖分等價于原來所處位置消失了一個點,同時在反轉點的共邊三角形內增加一個新點。因此,對于反轉三角形的局部更新可以用刪除點與增加點的方式進行局部更新。由圖2(b)可見,反轉點A在共邊三角形中按增加點進行更新時,可能會影響刪除點區(qū)域的剖分,因此,反轉三角形的局部更新需要按刪除點、增加點的順序進行更新。

4仿真實驗

本部分將采用數值仿真的方法比較改進的DDT方法與SDT方法、距離門限方法作為潛在沖突篩選方法的篩選效率。根據空管指揮系統(tǒng)的實際指標,仿真實驗中考慮1 000km×1 000km空域?？沼騼群娇掌鞯奈恢眉八俣纫噪S機方式產生,其中航空器的位置分布服從以空域中心為的二維高斯分布,航空器速度大小服從700～1 000km/h內的均勻分布,速度方向服從360°方向的均勻分布。假設空域內的航空器以勻速直線運動。

首先,分析空域內航空器數目對不同篩選方法初始化時間及篩選潛在沖突航空器數量的影響。將空域內航空器數目由20加逐步增加到500架,在每個數據點執(zhí)行100次蒙特卡羅實驗,分別統(tǒng)計改進的DDT方法、SDT方法、距離門限法在以50km和100km為門限時完成首次潛在沖突航空器檢測所需的時間和潛在沖突航空器的平均數量,如圖3所示。

圖3　空域內航空器數量對篩選方法初始化的影響

如前所述,改進的DDT方法和SDT方法篩選潛在沖突航空器是利用空域航空器的Delaunay三角剖分實現的。這兩種方法確定的潛在沖突航空器的平均數量是指空域內航空器所在三角剖分中的邊的平均數。距離門限法是計算兩兩航空器之間的距離,通過與相應門限值比較來確定是否存在潛在沖突對。因此,距離門限法的初始化時間與門限值無關,改進的DDT方法和SDT方法均需要完成空域航空器的Delaunay三角剖分,所以兩者的初始化時間也相同,如圖3(a)所示。由如圖3(a)還可以看出,隨著空域內航空器數目的增加,所有方法的初始化時間均增加,而且距離門限法時間增長速度明顯快于改進的DDT方法和SDT方法。當空域內航空器數目較少時,距離門限法的效率優(yōu)于改進的DDT方法和SDT方法,但空域內航空器數目增加到一定數量時,改進的DDT方法和SDT方法將優(yōu)于距離門限方法。

在潛在沖突航空器篩選方面,由圖3(b)可見,距離門限方法所篩選出的潛在沖突航空器數目與空域內航空器數目及門限大小有關。空域內航空器數目的增大,導致篩選出的潛在沖突航空器平均數呈線性增長,而且增長的速率與門限有大小有關。在圖3(b)中,航空器數目的增大,導致空域內航空器的密度加大,由此可以推斷,在航空器密集區(qū)域,如終端區(qū)域等,采用距離門限方法篩選出手潛在沖突航空器數量將顯著增加。由圖3(b)可見,改進的DDT方法和SDT方法所篩選出的潛在沖突航空器數目約為3,并且與空域內航空器的數目或航空器的密度無關,因此,更適宜使用在航空器密集區(qū)域的短時沖突告警檢測的篩選處理。

其次,分析空域內增、減航空器對篩選方法效率的影響?？紤]空域內已有航空器200架,采用逐一增加的方式將航空器數量增加到225架,考察每增加一架航空器時,每個篩選方法對時間的消耗。同樣,在每個數據點處進行100次蒙特卡羅實驗。實驗結果如圖4所示。由圖4可見,距離門限方法的刷新時間隨著航空器數目的增加而增大,這與圖3(a)結果一致。隨著航空器數目的增加,SDT方法的時間消耗有些許增加,這是因為每次空域Delaunay三角剖分的離散點數增加所致。改進的DDT方法的時間消耗基本不變,且時間消耗最低。每次增加1個目標,對于改進的DDT方法只是對空域Delaunay剖分的局部進行更新,因此,每次引入的計算量基本相當。

圖4　空域內航空器數量逐一增加對刷新時間的影響

相類似地考慮空域內航空逐一刪除對篩選方法效率的影響。仍然假設空域內已有航空器200架,采用逐一刪除方式將航空器數量減少到175架,考察每刪除一架航空器時,每個篩選方法對時間的消耗。同樣,在每個數據點處進行100次蒙特卡羅實驗。實驗結果如圖5所示。與圖4相比較,距離門限方法的刷新時間與航空器數目相關,SDT方法的時間消耗也與航空器數目有關,但受影響程序不顯著,改進的DDT方法的時間消耗基本不受航空器數目的影響,且時間消耗最低。

圖5　空域內航空器數量逐一減少對刷新時間的影響

再考慮同時增加若干架航空器對各篩選方法的時間消耗的影響。實驗條件同前,只是每次增加的航空器個數由1個逐步增加到25個。在每種情況下進行100次蒙特卡羅實驗,統(tǒng)計結果如圖6所示。與圖4相比較可見,距離門限法和SDT方法的時間消耗一致,而對于改進的DDT方法,時間消耗存在一定的增長。這是因此每次增加的航空器數目不同,局部更新的量也相應地增大,從而導致時間消耗增加。

圖6　批量增加空域內航空器數量對刷新時間的影響

最后,分析空域Delaunay剖分中存在反轉三角形時,各種篩選方法的時間消耗?？紤]空域內存在航空器200架,通過交換某個三角形的兩個頂點坐標來形成反轉三角形,分別統(tǒng)計存在1個到25個反轉三角形時的幾種方法的時間消耗。在每個實驗條件下進行100次蒙特卡羅實驗,實驗結果如圖7所示。由圖7可見,當空域內Delaunay剖分中存在反轉三角形時,空域內航空器數目未發(fā)生改變,所以不影響距離門限方法和SDT方法的時間消耗,而對于改進的DDT方法,反轉三角形數量影響著局部更新復雜度,隨著反轉三角形數量的增大,改進的DDT方法的時間消耗呈線性增長。在實際運行環(huán)境中,瞬時增加的反轉三角形的個數通常較少,一般不會超過3個,由圖7可見,在較少反轉三角形的條件下,改進的DDT方法的時間消耗明顯低于其他方法。

圖7　空域內反轉三角形個數對刷新時間的影響

5結論

本文對DDT方法的改進,使其可以有效地解決空域Delaunay三角剖分中的反轉三角形檢測問題,通過對反轉點的確定,可以用順序點刪除與點添加的局部更新方式實現對反轉三角形的局部更新。本文所提方法既保持了DDT方法的局部更新特點,又解決文獻[9]中DDT方法無法對反轉三角形情況進行拓撲更新的缺陷,因此,本文提出的改進的DDT方法是一種穩(wěn)健、高效的Delaunay三角剖分動態(tài)維護方法。實驗結果表明,該方法在航空器潛在沖突篩選處理上具有較明顯的效率優(yōu)勢。

參考文獻：

[1] EUROCONTROL. Eurocontral guidance material for short term conflict alert, May 2009[EB/OL].[2015-06-13].http:∥www.eurocontrol.int/publications/eurocontrol-guidance-material-short-term-conflict-alert.

[2] Hess M, Heidger R, Bredemeyer J. Tracker quality monitoring by nondedicated calibration flights[J].IEEEAerospaceandElectronicSystemsMagazine, 2014, 29(8): 10-16.

[3] Liu W, Hwang I. Probabilistic aircraft mid-air conflict resolution using stochastic optimal control[J].IEEETrans.onIntelligentTransportationSystems, 2014, 15(1): 37-46.

[4] Matsuno Y, Tsuchiya T. Stochastic 4D trajectory optimization for aircraft conflict resolution[C]∥Proc.oftheIEEEAerospaceConference, 2014：1-10.

[5] Richard E, Jonathan F. Multiobjective optimization of safety related systems: an application to short-term conflict alert[J].IEEETrans.onEvolutionaryComputation, 2006, 10(2): 187-198.

[6] Chiang Y J, Klosowski J T, Lee C, et al. Geometric algorithms for conflict detection/resolution in air traffic management[C]∥Proc.ofthe36thIEEEConferenceonDecisionandControl, 1997: 1835-1840.

[7] Liu X, Han S C. Delaunay method for free flight conflict detection[J].JournalofDataAcquisition&Processing,2002,17(4):446-449.(劉星,韓松臣.用于自由飛行沖突探測的Delaunay方法[J].數據采集與處理,2002,17(4):446-449.)

[9] Su Z G, Wang Z, Wu R. Robust dynamic Delaunay triangulation technology for moving points[J].SystemsEngineeringandElectronics, 2013, 35(8): 1764-1768. (蘇志剛, 王爭, 吳仁彪. 面向移動點的穩(wěn)健動態(tài)Delaunay三角剖分技術[J].系統(tǒng)工程與電子技術, 2013, 35(8): 1764-1768.)

[10] Rubin N. On kinetic Delaunay triangulations: a near quadratic bound for unit speed motions[C]∥Proc.oftheIEEE54thAnnualSymposiumonFoundationsofComputerScience, 2013, 519-528.

[11] Zhou Y, Sun F, Wang W, et al. Fast updating of Delaunay triangulation of moving points by bi-cell filtering[J].ComputerGraphicsForums, 2010, 29(7): 2233-2242.

[12] Machado P, Castro M, Tournois J, et al. Filtering relocations on a Delaunay triangulation[J].ComputerGraphicsForums, 2009, 28(5): 1465-1474.

[13] Zhou Y F, Sun F, Wang W P, et al. A new algorithm for fast updating Delaunay triangulation of moving points based on local fixing[J].JournalofComputer-AidedDesign&ComputerGraphics,2011,23(12):2006-2012.(周元峰,孫峰,王文平,等. 基于局部修復的移動數據點Delaunay三角化快速更新方法[J].計算機輔助設計與圖形學學報,2011,23(12):2006-2012.)

[14] Kolingerová I, ?alik B. Improvements to randomized incremental Delaunay insertion[J].ComputersandGraphics, 2002, 26(3): 477-490.

[15] Guibas L, Russel D. An empirical comparison of techniques for updating Delaunay triangulations[C]∥Proc.ofthe20thAnnualSymposiumonComputationalGeometry, 2004：170-179.

[16] Devillers O. On deletion in Delaunay triangulation[C]∥Proc.ofthe15thAnnualACMSymposiumonComputationalGeometry, 1999: 181-188.

[17] Rubin N. On topological changes in the Delaunay triangulation of moving points[J].Discrete&ComputationalGeometry, 2013, 49(4) : 710-746.

蘇志剛(1972-),男,教授,博士,主要研究方向為雷達信號處理、陣列信號處理、空中交通管理、信息融合。

E-mail:ssrsu@vip.sina.com

符笑嫻(1990-),女,碩士研究生,主要研究方向為空中交通管理、沖突檢測。

E-mail:fuxiaoxian1990@163.com

郝敬堂(1989-),男,助理實驗員,碩士,主要研究方向為空中交通管理、空管目標仿真、空管中間件。

E-mail:liuzhijingquan1989@126.com

Dynamic triangulation based method for screening potential conflicts

SU Zhi-gang1,2, FU Xiao-xian1,3, HAO Jing-tang1

(1.Sino-EuropeanInstituteofAviationEngineering,CivilAviationUniversityofChina,Tianjin300300,China;2.TianjinKeyLaboratoryforAdvancedSignalProcessing,CivilAviationUniversityofChina,Tianjin300300,China; 3.FujianGeneralAviationIndustryCompanyLimited,Fuzhou350000,China)

Abstract:Focusing on the difficulty that the dynamic delaunay triangulation (DDT) method could not stably realize local updating for the inverted triangle produced in the airspace triangulation, a modified method is proposed to replace the local updating for the inverted triangle with two local updatings in sequence in cases of point deletion and point insertion. Experimental results show that the number of potential conflict aircrafts using the modified DDT is independent with the aircraft density in airspace, and the modified DDT method has much lower time complexity of local updating. Modified DDT is more robust and more suitable for screening the potential conflict aircrafts in the air traffic control automation system.

Keywords:air traffic management; conflict detection; dynamic delaunay triangulation (DDT); moving point set; dynamic updating

收稿日期：2015-02-15；修回日期：2015-12-16；網絡優(yōu)先出版日期：2016-03-22。

基金項目：國家科技支撐計劃 (2011BAH24B12)；中央高?；究萍紭I(yè)務費中國民航大學專項項目(3122014H003)資助課題

中圖分類號：TP 302

文獻標志碼：A

DOI:10.3969/j.issn.1001-506X.2016.06.36

作者簡介：

網絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160322.1650.010.html