基于分離軸算法的機(jī)場(chǎng)場(chǎng)面飛行器沖突告警研究

吳壽英 李 煒

1(四川大學(xué)視覺(jué)合成圖形圖像技術(shù)國(guó)防重點(diǎn)學(xué)科實(shí)驗(yàn)室 四川 成都 610065) 2(四川大學(xué)空天科學(xué)與工程學(xué)院 四川 成都 610065)

0 引 言

由于目前機(jī)場(chǎng)場(chǎng)面缺少完備的沖突事件檢測(cè)和告警系統(tǒng),導(dǎo)致機(jī)坪航空器之間的擦碰事件時(shí)有發(fā)生,造成大量人員航班延誤。因?yàn)闄C(jī)坪人手不足,地勤和航空器操作員存在視線(xiàn)盲區(qū),導(dǎo)致機(jī)坪繁忙階段特別容易發(fā)生航空器之間的擦碰問(wèn)題。為有效監(jiān)控與管理場(chǎng)面飛機(jī)的安全運(yùn)行,減少機(jī)場(chǎng)地面交通擦碰事件的發(fā)生,國(guó)內(nèi)外航空界對(duì)此做了較多的研究,提出了一些理論與方法[1-2]。但總體上都是從硬件設(shè)備以及策略方面降低機(jī)場(chǎng)飛機(jī)之間的碰撞問(wèn)題。減少航空器間的沖突及碰撞是機(jī)場(chǎng)安全運(yùn)行的重要保證,由于航空器后機(jī)會(huì)受到前機(jī)尾流的影響,所以在地面滑行時(shí)保證航空器間的安全距離是有效避免沖突及碰撞的手段,葉右軍[3]研究了基于航空器間安全距離的碰撞模型,以降低航空器之間的碰撞風(fēng)險(xiǎn)。另外,潘衛(wèi)軍等[4]分析了機(jī)場(chǎng)沖突熱點(diǎn)的時(shí)空分布特征,通過(guò)對(duì)機(jī)場(chǎng)建模構(gòu)建航空器的滑行和避讓機(jī)制,提出基于機(jī)場(chǎng)沖突熱點(diǎn)時(shí)空分布特征的航空器地面滑行路徑優(yōu)化模型,從而降低場(chǎng)面飛機(jī)的沖突或碰撞事件。葛亞威等[5]利用A-SMGC系統(tǒng)監(jiān)視模塊與路由規(guī)劃模塊的結(jié)合,構(gòu)建沖突探測(cè)系統(tǒng)框架來(lái)減少?zèng)_突碰撞事件以及提升機(jī)場(chǎng)運(yùn)行安全,類(lèi)似的研究還有許多[6-8]。

上述這些理論方法雖然在一定程度上對(duì)場(chǎng)面航空器沖突預(yù)警,但是其虛警率高。牟奇鋒等[9]通過(guò)航空器外形及關(guān)鍵尺寸設(shè)計(jì)類(lèi)碰撞盒的可變多邊形還原航空器,且考慮航空器在運(yùn)動(dòng)過(guò)程中對(duì)地面空間占用的影響,將其機(jī)頭保護(hù)層沿運(yùn)動(dòng)方向前推至一個(gè)制動(dòng)距離,從而降低虛警率。杜金峰等[10]使用基于北斗二代定位數(shù)據(jù)的機(jī)場(chǎng)場(chǎng)面短期沖突探測(cè)算法,可以根據(jù)飛機(jī)不同運(yùn)動(dòng)狀態(tài)設(shè)定最小安全距離且判定沖突類(lèi)型從而減少虛警率。

機(jī)場(chǎng)場(chǎng)面目標(biāo)危險(xiǎn)接近與告警實(shí)質(zhì)上是其在告警區(qū)域內(nèi)的碰撞檢測(cè)問(wèn)題。根據(jù)監(jiān)控飛機(jī)的地理位置坐標(biāo)和型號(hào)可重建飛機(jī)模型,進(jìn)而獲得該飛機(jī)模型在2D場(chǎng)面下的區(qū)域坐標(biāo)范圍,從而可以轉(zhuǎn)化為二維場(chǎng)景下的多邊形碰撞檢測(cè)問(wèn)題。本文設(shè)計(jì)基于最近點(diǎn)的分離軸碰撞檢測(cè)算法,重建飛機(jī)目標(biāo)模型,并對(duì)模型頂點(diǎn)進(jìn)行弧形檢測(cè),構(gòu)建模型監(jiān)控告警區(qū)。通過(guò)計(jì)算機(jī)模擬仿真場(chǎng)面飛機(jī)危險(xiǎn)接近場(chǎng)景,仿真實(shí)驗(yàn)結(jié)果表明,本文算法可有效降低程序時(shí)間復(fù)雜度加快沖突檢測(cè)速度,同時(shí)弧形處理可降低虛警率。

1 重建飛機(jī)模型

由于飛機(jī)是多邊形,且常見(jiàn)的載人客機(jī)模型輪廓都差不多,所以圍繞航空器的外圍輪廓,根據(jù)其外部形狀特征,通過(guò)模型關(guān)鍵尺寸即可構(gòu)建飛機(jī)模型基層區(qū)域。飛機(jī)模型可以用17條邊包圍,如圖1所示,假設(shè)已知的坐標(biāo)點(diǎn)為飛機(jī)頭頂點(diǎn)A0(x0,y0),則沿順時(shí)針?lè)謩e將各個(gè)頂點(diǎn)坐標(biāo)標(biāo)記為A1,A2,…,A16。

圖1 飛機(jī)模型編號(hào)

過(guò)頂點(diǎn)A0作一條中線(xiàn)平分模型,直線(xiàn)與x軸夾角為飛機(jī)的朝向θ。設(shè)飛機(jī)關(guān)鍵尺寸為hi、wi,當(dāng)i<7時(shí),分別為Ai到A0頂點(diǎn)的θ-π/2方向和θ方向的兩個(gè)分量,如圖2所示。當(dāng)i≥7時(shí),分別為θ+π/2方向和θ方向的兩個(gè)分量,如圖3所示。

圖2 飛機(jī)模型頂點(diǎn)坐標(biāo)計(jì)算(i<7)

圖3 飛機(jī)模型頂點(diǎn)坐標(biāo)計(jì)算 (i≥7)

當(dāng)i<7情況下,飛機(jī)朝向和關(guān)鍵尺寸已知,由圖2可知Ai(xi,yi)頂點(diǎn)的坐標(biāo)為:

式中:m與n分別為Ai到A0頂點(diǎn)之間x軸和y軸投影的距離,根據(jù)幾何原理可得:

則有:

同理,當(dāng)i≥7時(shí),則有:

機(jī)場(chǎng)場(chǎng)面沖突檢測(cè)就是防止碰撞,所以要制定安全距離,進(jìn)行危險(xiǎn)接近觸發(fā)告警機(jī)制。危險(xiǎn)接近告警就是模擬告警區(qū),對(duì)于特定的安全距離閾值可以構(gòu)造飛機(jī)告警區(qū),從而構(gòu)造飛機(jī)之間的安全距離。飛機(jī)模型是一個(gè)非凸多邊形,如果直接計(jì)算航空器之間的碰撞關(guān)系則會(huì)非常復(fù)雜,所以把非凸多邊形劃分為多個(gè)凸多邊形是自然會(huì)想到的解決方法。如圖1所示,飛機(jī)模型被劃分為6個(gè)凸多邊形,其中有效多邊形為5個(gè)(a-e)。接下來(lái)是飛機(jī)模型安全區(qū)域的碰撞檢測(cè),本文把檢測(cè)過(guò)程分為粗略檢測(cè)階段和精細(xì)檢測(cè)階段,其中精細(xì)檢測(cè)即直接對(duì)飛機(jī)凸多邊形進(jìn)行兩兩檢測(cè)。

由于場(chǎng)面飛機(jī)較多,直接進(jìn)行精細(xì)檢測(cè)會(huì)消耗較多檢測(cè)時(shí)間,所以使用檢測(cè)速度較快的方法先進(jìn)行粗略檢測(cè)可以提高檢測(cè)速度。如圖4所示,B區(qū)為粗略檢測(cè)區(qū),使用類(lèi)包圍球方法,原點(diǎn)為恰好能夠把A區(qū)圍住的圓的圓心。A區(qū)為精細(xì)檢測(cè)區(qū),用一個(gè)多邊形把飛機(jī)模型圍起來(lái),多邊形形狀即飛機(jī)模型向外制動(dòng)一個(gè)安全距離所得,在頂點(diǎn)部分進(jìn)行圓滑處理,即以飛機(jī)模型頂點(diǎn)為圓心畫(huà)弧。由于飛機(jī)實(shí)體較大,若頂點(diǎn)不進(jìn)行圓滑處理,則會(huì)出現(xiàn)機(jī)翼頂點(diǎn)區(qū)域向外制動(dòng)的安全距離過(guò)長(zhǎng),會(huì)導(dǎo)致虛警。設(shè)飛機(jī)安全距離告警閾值為SPTP,飛機(jī)機(jī)頭到機(jī)尾距離為d,則有飛機(jī)模型對(duì)應(yīng)B區(qū)的半徑為rB=2×SPTP+d。

圖4 飛機(jī)安全區(qū)域及閾值設(shè)置

具體實(shí)現(xiàn)中,目標(biāo)的沖突檢測(cè)需先檢測(cè)B區(qū)是否碰撞,如果沒(méi)有則進(jìn)行下一個(gè)目標(biāo)模型檢測(cè),否則再進(jìn)行A區(qū)碰撞檢測(cè)。由于飛機(jī)A區(qū)檢測(cè)比較復(fù)雜,所以用B區(qū)包起來(lái)先進(jìn)行一次快速粗略檢測(cè),這樣可以降低檢測(cè)A區(qū)的次數(shù),從而很大程度減少程序時(shí)間復(fù)雜度,增快檢測(cè)速度。

2 檢測(cè)算法描述

凸多邊形碰撞檢測(cè)算法使用分離軸定理,若令K和L為兩個(gè)不相交的非空封閉凸集,其中一個(gè)是有界閉集,則存在一個(gè)非零向量v和實(shí)數(shù)r1

〈x1,v〉>r2(x1∈K),〈x2,v〉

(5)

若K、L集合都是開(kāi)放的,則存在一個(gè)非零向量v′和實(shí)數(shù)r使得:

〈x1,v′〉>r(x1∈K),〈x2,v′〉

(6)

如圖5所示,取飛機(jī)模型的兩個(gè)凸多邊形a與e為例,把多邊形的頂點(diǎn)都投影至一條軸線(xiàn)上。只要找到一條或多條軸(分離軸),使凸多邊在該軸的投影不相交,那就可以說(shuō)明這兩個(gè)或多個(gè)物體沒(méi)有發(fā)生碰撞。為了方便觀察,垂直于分離軸且可以把目標(biāo)分為左右兩邊的向量稱(chēng)為分離線(xiàn)。

圖5 分離軸定理示圖

分離軸定理所選擇的潛在分離軸通常都是凸多邊形的邊所在的軸線(xiàn),隨著邊數(shù)的增多,檢測(cè)的次數(shù)會(huì)不斷增加(如一直未找到潛在分離軸),只要找到一條不相交的分離軸,程序就會(huì)立馬停止檢測(cè),所以基于分離軸定理的碰撞檢測(cè)算法屬于高效的算法,不過(guò)弊端也非常明顯,當(dāng)找不到分離軸的時(shí)候,算法復(fù)雜度會(huì)增加。所以需要一個(gè)改進(jìn)的方案,降低程序?qū)ふ曳蛛x軸的次數(shù),從而提高計(jì)算效率。

由于應(yīng)用場(chǎng)景是場(chǎng)面飛機(jī),而對(duì)于精細(xì)檢測(cè)階段,把A區(qū)分解成5個(gè)有效凸邊形(此處凸邊形是指沒(méi)有進(jìn)行頂點(diǎn)圓弧處理的多邊形),則兩個(gè)飛機(jī)A區(qū)碰撞檢測(cè)算法最多會(huì)被調(diào)用25次,若飛機(jī)數(shù)量增加,碰撞算法時(shí)間復(fù)雜度也會(huì)增大,所以碰撞算法的選取顯得尤為重要,本文使用基于分離軸定理的碰撞檢測(cè)算法。

多架飛機(jī)之間碰撞如果用傳統(tǒng)的分離軸定理效率不夠高,由于每架飛機(jī)有5個(gè)凸邊形17條邊,逐個(gè)查找分離軸最多需要17×2次,兩架飛機(jī)總的查找次數(shù)為5!×17×2即4 080次,若有n架飛機(jī),則查找次數(shù)變?yōu)閚!×4 080次。所以傳統(tǒng)基于分離軸的碰撞檢測(cè)算法不適合邊數(shù)較多的凸多邊形。由于兩個(gè)目標(biāo)碰撞一定是點(diǎn)和點(diǎn)、點(diǎn)和線(xiàn)、線(xiàn)和線(xiàn)的其中一種情況,即一定包含一個(gè)頂點(diǎn),所以找到這個(gè)可能的頂點(diǎn)可以減少碰撞檢測(cè)次數(shù)。首先找到碰撞點(diǎn)序列,再利用折半搜索技術(shù)求取最初碰撞的頂點(diǎn)和邊。本文利用改進(jìn)的分離軸碰撞檢測(cè)算法即基于最近點(diǎn)的碰撞檢測(cè)。設(shè)ai(xi,yi)(i=0,1,…,16)為飛機(jī)的頂點(diǎn),Tj(j=a,b,c,d,e)為飛機(jī)模型里的5個(gè)凸多邊形,則有:

連接兩架飛機(jī)中線(xiàn)中點(diǎn)形成直線(xiàn)M,飛機(jī)中線(xiàn)中點(diǎn)坐標(biāo)dz(xz,yz)為:

兩架飛機(jī)的中點(diǎn)坐標(biāo)分別為dz1(xz1,yz1)、dz2(xz2,yz2)則直線(xiàn)M函數(shù)為:

其斜率和截距為:

把飛機(jī)頂點(diǎn)ai(xi,yi)(i=0,1,…,16)投影到直線(xiàn)M上,設(shè)投影點(diǎn)為aMi(xMi,yMi)(i=0,1,…,16),則有:

首先找到最近的兩個(gè)投影點(diǎn),記錄最近頂點(diǎn)所在凸邊形號(hào),若可以找到一條垂直直線(xiàn)把兩個(gè)凸邊形的投影點(diǎn)分隔開(kāi),即證明兩個(gè)凸邊形無(wú)重疊。否則查找兩個(gè)凸邊形的分離軸,具體地,只需要查找最近頂點(diǎn)對(duì)及其所在邊的法向量,若能找到分離向量把最近頂點(diǎn)對(duì)分隔開(kāi),則兩個(gè)凸邊形沒(méi)有碰撞即飛機(jī)沒(méi)有發(fā)生碰撞(無(wú)危險(xiǎn)接近)。否則繼續(xù)判斷最近點(diǎn)所在的四條潛在分離軸,只要找到一條分離軸,則說(shuō)明飛機(jī)無(wú)危險(xiǎn)接近,若找不到則說(shuō)明兩架飛機(jī)危險(xiǎn)接近需要告警。圖6所示為機(jī)翼碰撞情況的示例,其投影在直線(xiàn)M的兩個(gè)最近點(diǎn)都在Tb凸邊形里,即只需要檢測(cè)一次碰撞檢測(cè)算法即可,兩個(gè)Tb凸邊形則使用分離軸算法進(jìn)行檢測(cè)。

圖6 基于最近點(diǎn)的A區(qū)碰撞檢測(cè)示圖

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

為研究不同算法對(duì)于最終效率的影響,本文分別對(duì)傳統(tǒng)的包圍盒算法、傳統(tǒng)分離軸算法、基于最近點(diǎn)的檢測(cè)算法進(jìn)行對(duì)比實(shí)驗(yàn),觀測(cè)不同算法在整個(gè)飛機(jī)碰撞檢測(cè)實(shí)驗(yàn)中所使用的時(shí)間。并且通過(guò)對(duì)比不使用弧形檢測(cè)以及使用弧形檢測(cè)的算法誤警次數(shù)來(lái)研究頂點(diǎn)弧形檢測(cè)對(duì)降低虛警率的有效性。

本文使用Qt框架來(lái)模擬50架飛機(jī)危險(xiǎn)接近的仿真實(shí)驗(yàn)。首先生成飛機(jī)的關(guān)鍵尺寸如表1所示,關(guān)鍵尺寸根據(jù)普通客機(jī)輪廓模擬所得。設(shè)定初始位置與方向角度,設(shè)置危險(xiǎn)接近閾值SPTP為50 m。然后用定時(shí)器模擬飛機(jī)的運(yùn)動(dòng)狀態(tài)和軌跡,從而模擬飛機(jī)之間的危險(xiǎn)接近情形。實(shí)驗(yàn)?zāi)M了機(jī)場(chǎng)場(chǎng)面幾個(gè)重要區(qū)域,包括跑道、多個(gè)滑行道、若干停機(jī)坪等。

表1 飛機(jī)關(guān)鍵尺寸

圖7表示使用不同算法時(shí),算法運(yùn)行時(shí)間隨著場(chǎng)面飛機(jī)數(shù)量增加而變化的過(guò)程。其中圓形標(biāo)注折線(xiàn)表示傳統(tǒng)包圍盒算法,三角形標(biāo)注折線(xiàn)表示傳統(tǒng)分離軸算法,方形折線(xiàn)表示基于最近點(diǎn)的檢測(cè)算法。飛機(jī)數(shù)量從10架逐漸增長(zhǎng)至50架。由圖7可知,傳統(tǒng)包圍盒算法隨著檢測(cè)目標(biāo)的增加運(yùn)行時(shí)間增長(zhǎng)速度最快,表明此算法運(yùn)行效率最低。傳統(tǒng)分離軸算法檢測(cè)時(shí)間雖然低于包圍盒算法,但是波動(dòng)幅度最大,這是由于在有n個(gè)目標(biāo)情況下,B區(qū)碰撞前時(shí)間復(fù)雜度為((n2+n)/2)即O(n2),傳統(tǒng)分離軸算法由于最多要檢測(cè)8條分離軸,其時(shí)間復(fù)雜度增高為8×O(n2),A區(qū)需要檢測(cè)飛機(jī)模型的5個(gè)凸邊形即要查找17×5次分離軸,時(shí)間復(fù)雜度則增加到85×O(n2)。本文改進(jìn)的基于最近點(diǎn)的檢測(cè)算法相對(duì)最平穩(wěn),運(yùn)行時(shí)間也最低,而且隨著飛機(jī)數(shù)量的增加,運(yùn)行時(shí)間有趨近于穩(wěn)定的趨勢(shì),說(shuō)明基于最近點(diǎn)分離軸的算法可有效提高檢測(cè)速度。

圖7 不同算法的運(yùn)行時(shí)間對(duì)比

仿真實(shí)驗(yàn)部分截圖如圖8所示,分別代表機(jī)場(chǎng)場(chǎng)面飛機(jī)機(jī)翼、機(jī)頭、機(jī)尾之間可能的危險(xiǎn)接近情形。圖8(a)為兩飛機(jī)機(jī)翼危險(xiǎn)接近,一般會(huì)發(fā)生在停機(jī)坪飛機(jī)需要推出或者進(jìn)入停機(jī)位時(shí)產(chǎn)生的擦碰行為。圖8(b)也是可能會(huì)發(fā)生的擦碰事件,由于牽引車(chē)牽引飛機(jī)時(shí)很可能由于視線(xiàn)盲區(qū)等因素,沒(méi)注意到正在移動(dòng)的飛機(jī)而造成機(jī)身擦碰。若加入了沖突告警系統(tǒng),程序可以監(jiān)控飛機(jī)之間的安全距離,當(dāng)B區(qū)碰撞時(shí)發(fā)出B區(qū)危險(xiǎn)接近告警,緊接著進(jìn)入A區(qū)告警檢測(cè)程序,如繼續(xù)接近,則A區(qū)檢測(cè)到碰撞或者重合,則持續(xù)發(fā)出A區(qū)危險(xiǎn)接近告警。

圖8 飛機(jī)二級(jí)碰撞檢測(cè)告警

在進(jìn)行頂點(diǎn)檢測(cè)時(shí),對(duì)頂點(diǎn)進(jìn)行了弧形處理。為研究弧形檢測(cè)對(duì)虛警率的影響,模擬了30架飛機(jī)危險(xiǎn)接近的場(chǎng)景,對(duì)誤警進(jìn)行研究。通過(guò)計(jì)算誤警次數(shù)與總的告警次數(shù)比值得到誤警率如表2所示。可以看出,進(jìn)行了弧形檢測(cè)的碰撞算法誤警率更低,證明了本文算法的有效性。

表2 算法誤警率對(duì)比表

這種層層遞進(jìn)的檢測(cè)方法可以大大簡(jiǎn)化算法時(shí)間復(fù)雜度,但每次都對(duì)場(chǎng)面的所有飛機(jī)進(jìn)行B區(qū)碰撞檢測(cè)依然不夠優(yōu)化,所以實(shí)驗(yàn)當(dāng)中需要對(duì)場(chǎng)面再進(jìn)行區(qū)域的劃分,分為跑道、滑行道、停機(jī)坪等區(qū)域。每次得到目標(biāo)物體的新坐標(biāo)和運(yùn)動(dòng)方向時(shí),則還原出物體模型,然后記錄下其坐標(biāo)點(diǎn)當(dāng)前所在區(qū)域,并判斷其屬于運(yùn)動(dòng)目標(biāo)或是靜止目標(biāo),這里通過(guò)對(duì)比當(dāng)前坐標(biāo)與上一次坐標(biāo)可以判斷飛機(jī)是否有移動(dòng),當(dāng)前場(chǎng)面區(qū)域所有目標(biāo)更新完成后可依次對(duì)各區(qū)域進(jìn)行運(yùn)動(dòng)目標(biāo)掃描,所以每個(gè)運(yùn)動(dòng)目標(biāo)只需要和其所在區(qū)域的其他運(yùn)動(dòng)目標(biāo)做碰撞檢測(cè),避免進(jìn)行遠(yuǎn)距離檢測(cè),可更進(jìn)一步減少程序算法的時(shí)間復(fù)雜度。如果飛機(jī)坐標(biāo)恰好處在區(qū)域分界線(xiàn)上也不用進(jìn)行額外處理,因?yàn)槊總€(gè)區(qū)域檢測(cè)都會(huì)把其邊界處的目標(biāo)一起檢測(cè),所以邊界處的飛機(jī)會(huì)被檢測(cè)兩次。算法流程如圖9所示。

圖9 仿真實(shí)驗(yàn)算法流程

圖9中,系統(tǒng)的所有飛機(jī)信息原則上應(yīng)該接入類(lèi)似ADS-B、GPS技術(shù)、雷達(dá)等給出的機(jī)場(chǎng)場(chǎng)面上運(yùn)動(dòng)目標(biāo)的坐標(biāo)和航向信息,實(shí)現(xiàn)對(duì)機(jī)場(chǎng)場(chǎng)面上運(yùn)動(dòng)目標(biāo)的可靠和高精度監(jiān)視,并獲取目標(biāo)的其他屬性信息。

4 結(jié) 語(yǔ)

機(jī)場(chǎng)場(chǎng)面危險(xiǎn)接近主要包括航空器與航空器、航空器與機(jī)動(dòng)車(chē)、機(jī)動(dòng)車(chē)與機(jī)動(dòng)車(chē)和兩者與建筑物固定物的危險(xiǎn)接近。機(jī)動(dòng)車(chē)模型相對(duì)簡(jiǎn)單,所以,本文沒(méi)有對(duì)機(jī)動(dòng)車(chē)進(jìn)行模擬仿真,然而,由于航空器本身外觀形狀比較復(fù)雜,直接對(duì)其進(jìn)行沖突碰撞檢測(cè)實(shí)現(xiàn)難度較大。因此,本文使用QT框架構(gòu)建與還原航空器模型,建立告警區(qū),演示了飛機(jī)之間危險(xiǎn)接近情形。實(shí)驗(yàn)結(jié)果顯示,使用基于最近點(diǎn)分離軸的碰撞檢測(cè)算法可以有效減少檢測(cè)速度,降低程序時(shí)間復(fù)雜度。本文提出的最近點(diǎn)危險(xiǎn)接近算法可應(yīng)用集成于實(shí)時(shí)獲取飛機(jī)坐標(biāo)位置和其他信息的機(jī)場(chǎng)場(chǎng)面監(jiān)視系統(tǒng)中,為其進(jìn)行場(chǎng)面預(yù)警和告警提供理論支持。