基于分離軸算法的機場場面飛行器沖突告警研究

吳壽英 李 煒

1(四川大學視覺合成圖形圖像技術國防重點學科實驗室 四川 成都 610065) 2(四川大學空天科學與工程學院 四川 成都 610065)

0 引 言

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

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

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

1 重建飛機模型

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

圖1 飛機模型編號

過頂點A0作一條中線平分模型,直線與x軸夾角為飛機的朝向θ。設飛機關鍵尺寸為hi、wi,當i<7時,分別為Ai到A0頂點的θ-π/2方向和θ方向的兩個分量,如圖2所示。當i≥7時,分別為θ+π/2方向和θ方向的兩個分量,如圖3所示。

圖2 飛機模型頂點坐標計算(i<7)

圖3 飛機模型頂點坐標計算 (i≥7)

當i<7情況下,飛機朝向和關鍵尺寸已知,由圖2可知Ai(xi,yi)頂點的坐標為:

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

則有:

同理,當i≥7時,則有:

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

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

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

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

2 檢測算法描述

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

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

(5)

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

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

(6)

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

圖5 分離軸定理示圖

分離軸定理所選擇的潛在分離軸通常都是凸多邊形的邊所在的軸線,隨著邊數(shù)的增多,檢測的次數(shù)會不斷增加(如一直未找到潛在分離軸),只要找到一條不相交的分離軸,程序就會立馬停止檢測,所以基于分離軸定理的碰撞檢測算法屬于高效的算法,不過弊端也非常明顯,當找不到分離軸的時候,算法復雜度會增加。所以需要一個改進的方案,降低程序尋找分離軸的次數(shù),從而提高計算效率。

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

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

連接兩架飛機中線中點形成直線M,飛機中線中點坐標dz(xz,yz)為:

兩架飛機的中點坐標分別為dz1(xz1,yz1)、dz2(xz2,yz2)則直線M函數(shù)為:

其斜率和截距為:

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

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

圖6 基于最近點的A區(qū)碰撞檢測示圖

3 仿真實驗及分析

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

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

表1 飛機關鍵尺寸

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

圖7 不同算法的運行時間對比

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

圖8 飛機二級碰撞檢測告警

在進行頂點檢測時,對頂點進行了弧形處理。為研究弧形檢測對虛警率的影響,模擬了30架飛機危險接近的場景,對誤警進行研究。通過計算誤警次數(shù)與總的告警次數(shù)比值得到誤警率如表2所示?？梢钥闯?進行了弧形檢測的碰撞算法誤警率更低,證明了本文算法的有效性。

表2 算法誤警率對比表

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

圖9 仿真實驗算法流程

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

4 結 語

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