跑道侵入與沖突檢測的共形幾何代數(shù)描述

焦衛(wèi)東，王瑞冬，姚軍強，龐艷麗

中國民航大學(xué) 天津市智能信號與圖像處理重點實驗室，天津 300300

隨著中國經(jīng)濟快速發(fā)展，民航飛行器數(shù)量越來越多，機場日漸繁忙，跑道侵入、沖突導(dǎo)致的危險事件發(fā)生的可能性增大，嚴(yán)重影響機場場面的安全運行。跑道侵入與沖突檢測成為空中交通管理的重要環(huán)節(jié)。

目前，跑道侵入與沖突檢測算法均基于歐氏空間研究。沈笑云等利用廣播式自動相關(guān)監(jiān)視(Automatic Dependent Surveillance-Broadcast, ADS-B)提供的實時位置數(shù)據(jù)和地理信息系統(tǒng)(Geographic Information System, GIS)，采用射線法及計算歐氏距離判斷的方式實現(xiàn)了實時跑道沖突檢測與告警功能。該方法在用射線法判斷飛行器和跑道保護區(qū)(Runway Protection Zone，RPZ)的位置關(guān)系時，需通過求解線性方程組確定射線和多面體的交點個數(shù)，且需要考慮邊界、邊界頂點及邊界延長面等特殊情況，邏輯復(fù)雜；在沖突檢測時需要分別判斷水平和垂直方向的距離，向高維擴展較困難，基于復(fù)雜場景的算法結(jié)構(gòu)較復(fù)雜。Cai等提出一種基于深度學(xué)習(xí)的跑道侵入檢測方法，具有更好的可靠性和準(zhǔn)確性。但該算法需要通過監(jiān)控獲取大量視頻圖像，經(jīng)大量學(xué)習(xí)和訓(xùn)練獲得可靠的網(wǎng)絡(luò)及參數(shù)，工作量較大，且由于視頻視角原因，很難檢測遮蔽情況下的目標(biāo)。Li等基于地面運動制導(dǎo)控制系統(tǒng)檢測跑道侵入，通過及早發(fā)現(xiàn)和警告跑道侵入來提高跑道安全性。該方法將保護區(qū)分成進(jìn)場區(qū)、排隊區(qū)、跑道區(qū)和離去區(qū)，需要將航跡點和各個區(qū)進(jìn)行比較，檢測沖突場景眾多。Wang等使用基于圖形處理器的高效算法檢測潛在的航路沖突，但由于航跡影響因素的不確定性，需要同時處理大量航跡，不適合用于跑道沖突檢測。王獻(xiàn)鋒等針對航路與終端區(qū)的防撞安全問題，提出一種基于蒙特卡羅法的飛行沖突檢測方法，能夠得到較為準(zhǔn)確的總體飛行沖突概率。Miao等提出一種基于多級網(wǎng)格時空索引的新型低空軌跡沖突檢測算法，提高了軌跡規(guī)劃和空域利用率。Yang等提出一種基于計算幾何的概率沖突檢測快速算法，取得了不錯的準(zhǔn)確率和效率。文獻(xiàn)[6-8]中的方法都是基于計算沖突概率的方法，在具有大量航跡數(shù)據(jù)的情況下，準(zhǔn)確率會有一定保證。但對于發(fā)生跑道侵入后的沖突檢測，屬于實時檢測的情況，不會有足夠數(shù)據(jù)用于沖突概率計算和比較，不利于已經(jīng)發(fā)生跑道侵入后的實時沖突檢測。

考慮到ADS-B已經(jīng)成為民航飛機的標(biāo)配，能夠提供實時位置及速度等數(shù)據(jù)，本文利用ADS-B數(shù)據(jù)，基于共形幾何代數(shù)優(yōu)越的幾何計算能力和統(tǒng)一維度的表達(dá)能力，對實時跑道侵入與沖突檢測進(jìn)行研究。首先，利用共形幾何代數(shù)進(jìn)行RPZ的模型描述，通過共形幾何的外積運算判斷飛行器與RPZ各面之間的位置關(guān)系，進(jìn)而判斷是否形成跑道侵入。然后，基于共形幾何代數(shù)的球面表示方法建立飛行器安全保護區(qū)的模型描述，通過共形幾何的內(nèi)積運算判斷飛行器的安全保護區(qū)是否相交，從而判斷飛行器是否沖突。

1 共形幾何代數(shù)

1.1 基本定義

共形幾何代數(shù)是建立在歐氏幾何模型之上的幾何代數(shù)，它將三維歐氏空間擴展成五維共形空間，其一組正交矢量基為、、、、，滿足

(1)

式中:,=1,2,…,。

引入矢量

(2)

=+

(3)

分別表示坐標(biāo)原點和無窮點，則

(4)

從而五維共形空間的基變?yōu)?span id="j5i0abt0b" class="emphasis_italic">、、、、，定義單位偽標(biāo)量為=。

1.2 基本運算

共形幾何代數(shù)的核心運算包括內(nèi)積、外積與幾何積，即

(5)

式中：和為矢量；為和的夾角；表示運算空間。

內(nèi)積是一種降維操作，其結(jié)果多用來表示距離與角度的運算。外積是將一個向量延伸到另一個向量的運算，是一種升維操作，其結(jié)果為二維子空間，也稱為二重向量(Bivector)。幾何積同時包含內(nèi)積和外積，類似于復(fù)數(shù)中的實部與虛部，符號“+”僅對不同維度的幾何對象進(jìn)行連接，并不進(jìn)行任何其他操作。

在共形幾何代數(shù)中，幾何實體有2種表示形式，如表1所示。其中，在表示法1中:=++為五維歐氏空間的點;球的表示中:為該球球心;為該球半徑;平面的表示中：為該面法向量，為坐標(biāo)原點到該面的距離；圓和點對的表示法中等變量為球；線的表示法中等變量為平面。表示法2中:“*”表示對偶運算符;、、、分別為歐氏空間中的點對應(yīng)的表示法1中的共形幾何代數(shù)形式。通常情況下用表示法1可以解決共形幾何代數(shù)中的問題，而當(dāng)只知道歐氏空間幾個點時，可以用表示法2快速表示共形幾何代數(shù)中幾何圖元的描述問題。

表1 共形幾何圖元列表Table 1 List of conformal geometric primitives

2 方法介紹

2.1 跑道保護區(qū)

國際民航組織(International Civil Aviation Organization，ICAO)對跑道侵入的定義：在機場中任何飛行器、車輛或人員誤入指定用于飛行器著陸和起飛的地面保護區(qū)。RPZ由《防止機場地面車輛和人員跑道侵入管理規(guī)定》定義，由地面保護區(qū)和空中保護區(qū)組成，如圖1所示。其中，地面保護區(qū)由機場跑道、滑行道、升降帶、跑道端安全區(qū)和電磁敏感區(qū)確定；空中保護區(qū)是從跑道升降帶起始端兩側(cè)開始，以3°角向上擴張，15°角向兩側(cè)擴張，直至達(dá)到距離跑道入口4 km處。這些線面圍成的區(qū)域及其地面部分共同組成RPZ。

以天津濱海國際機場為例，其經(jīng)緯度分別為E117°20.7′和N39°07.4′，16R/34L跑道長3 600 m，寬60 m。以跑道中心點為原點、平行跑道的方向為軸、垂直跑道的方向為軸，建立直角坐標(biāo)系，則RPZ的8個頂點坐標(biāo)如表2所示。

表2 RPZ的8個頂點坐標(biāo)Table 2 8 vertex coordinates of RPZ

根據(jù)表1中點的表示法1和面的表示法2，共形幾何代數(shù)中的平面可以由該面上3點和表示，如由點，，得到RPZ的一個面(如圖1 所示)的共形幾何代數(shù)表示為

圖1 跑道保護區(qū)Fig.1 Runway protection zone

+]∧

(6)

此時，應(yīng)注意共形幾何代數(shù)中的面具有方向性，如圖1中各平面上的箭頭所示，3點的順序不同，則生成面的方向也不同。同理可獲得RPZ的其他5個面的共形幾何代數(shù)表示的詳細(xì)形式。

(7)

以上6個面圍成RPZ，其內(nèi)部均在各面的后方，如圖1所示。

2.2 跑道侵入

飛行器大小遠(yuǎn)小于RPZ，其形狀大小可忽略不計，近似看成一點，而RPZ可看成一多面體，從而飛行器與RPZ的位置關(guān)系可看作點與多面體的位置關(guān)系。雖然共形幾何代數(shù)的Meet運算符可以以統(tǒng)一的方式確定不同尺寸的2個對象之間的相交關(guān)系，且可以直接處理無邊界的基本幾何對象，但只能進(jìn)行基本元素(點、線、面)的運算，而不能對“體”直接運算。為判斷點和多面體的位置關(guān)系，需要依次考慮點和形成該多面體邊界的幾個面的位置關(guān)系。

點面位置關(guān)系的問題，通常采用定性的方位描述方法，這類定性的空間描述在共形幾何代數(shù)空間一般只需要利用外積運算的方向性，直接判斷點面外積結(jié)果的正負(fù)號即可。本文引入共形幾何代數(shù)中外積的性質(zhì)來判斷點是否在多面體內(nèi)，從而判斷飛行器是否在RPZ內(nèi)。以圖1跑道保護區(qū)中的面為例，其在共形幾何代數(shù)空間的屬性如圖2所示。

圖2 點面位置關(guān)系Fig.2 Position relationship of point and surface

令

=(∧)

(8)

在共形幾何代數(shù)中，當(dāng)>0時，點位于平面順時針方向，即點位于平面前方；當(dāng)<0時，點位于平面逆時針方向，點位于平面后方；當(dāng)=0時，點位于平面上。

通過上述方法可以得到點與一個面的位置關(guān)系。RPZ是由6個面圍成的多面體，實際情況中飛行器始終在跑道所在面的上方，對

始終有≤0。因此只需依次判斷飛行器與其他5個面之間的位置關(guān)系：如果對某個面出現(xiàn)>0時，可以斷定飛行器不在RPZ內(nèi)；如果對這5個面都有≤0，則飛行器在RPZ內(nèi)。

這樣，通過共形幾何代數(shù)將有界的RPZ用無界的平面組合進(jìn)行表示，只需要通過外積運算考慮飛行器相對于RPZ各面的方向或點面位置關(guān)系，減少判定因素，而且不依賴坐標(biāo)系建立。避免了歐氏空間中需要將點代入多面體的邊界平面方程計算經(jīng)過點的有向射線與多面體的交點個數(shù)來判斷位置關(guān)系，以及處理RPZ邊界延長面等各種特殊情況的處理，邏輯相對簡單。

2.3 飛行器保護區(qū)

為防止飛行器與其他飛行器、障礙物相撞，確保飛行器安全運行，必須提供其在空間上的安全距離即最小安全間隔。對于RPZ中的飛行器，水平最小安全距離由飛行器的長寬決定，垂直最小安全距離為規(guī)定值：=60.96 m。因此以飛行器中心點為球心，=max{，}為半徑的球即為飛行器保護區(qū)(保護球)，其共形幾何代數(shù)形式為

(9)

實際應(yīng)用中，可根據(jù)應(yīng)用要求適當(dāng)調(diào)節(jié)半徑大小。

2.4 跑道沖突檢測

跑道沖突檢測中，為保證有充分的安全冗余，分別以2架正在作業(yè)的飛行器中心位置、為球心，不妨以作為飛行器1保護區(qū)(球)的半徑、作為飛行器2保護區(qū)(球)的半徑做球、，用表1中球的共形幾何代數(shù)表示法1表示為

(10)

幾何代數(shù)中，為定義2點之間的度量性質(zhì)，引入內(nèi)積運算，計算式(10)中2球、的內(nèi)積得

(11)

(12)

式(12)等號右邊等于2球半徑的平方和減去2球心之間距離的平方?？紤]兩球相切的充分必要條件為

(13)

可以得到：

1) 若·<-，則2球不相交，此時認(rèn)為2飛行器不發(fā)生沖突。

2) 若·≥-，則2球相交或相切，此時認(rèn)為2飛行器發(fā)生沖突，其中等號成立時為相切。

這種判斷方法利用共形幾何代數(shù)的多維統(tǒng)一表示將水平和垂直方向維度的屬性統(tǒng)一起來，只需要考慮2飛行器保護區(qū)(球)之間的內(nèi)積運算即可確定是否沖突，避免了歐氏空間中需要分別判斷水平和垂直方向的距離，實現(xiàn)了運算低維向高維的擴展，算法結(jié)構(gòu)簡單。

2.5 跑道侵入與沖突檢測步驟

對機場跑道定義保護區(qū)后，設(shè)飛行器1為跑道上當(dāng)前作業(yè)飛行器，飛行器2為后續(xù)作業(yè)飛行器，則基于共形幾何代數(shù)的跑道侵入與沖突檢測步驟為(流程圖如3所示)：

圖3 跑道侵入與沖突檢測流程圖Fig.3 Flow chart of runway incursion and conflict detection

輸入RPZ的各面的共形幾何代數(shù)表示。

對RPZ內(nèi)的當(dāng)前作業(yè)飛行器1(點)，計算及。

對飛行器2(點)，依次計算

=(∧)=2,3,…,6

如果某一>0，則飛行器2不夠成跑道侵入，繼續(xù)判斷下一時刻該飛行器或下一作業(yè)飛行器是否構(gòu)成跑道侵入或算法終止；如果所有≤0，則飛行器2侵入RPZ，轉(zhuǎn)步驟4進(jìn)入沖突檢測過程。

計算、、·。

如果·≥-，則飛行器2與飛行器1發(fā)生沖突，進(jìn)行報警或沖突解脫。如果·<-，則2機不發(fā)生沖突，繼續(xù)判斷下一時刻該飛行器或下一飛行器是否構(gòu)成跑道侵入或算法終止。

3 實驗結(jié)果

準(zhǔn)確的航跡預(yù)測是檢測飛行器是否發(fā)生沖突的基礎(chǔ)，由于Kalman濾波具有較強的魯棒性和工程應(yīng)用潛力，本文實驗過程中利用卡爾曼濾波進(jìn)行航跡預(yù)測。

利用2020年12月14日天津濱海國際機場的ADS-B航跡數(shù)據(jù)，在GIS中構(gòu)造沖突場景進(jìn)行實驗分析，并同歐氏空間算法比較驗證本文算法的有效性。實驗環(huán)境為macOS Catalian、2.6 GHz雙核處理器、8 GB內(nèi)存計算機、Python3.8平臺。共形幾何代數(shù)運算使用Python中基于Gaigen系統(tǒng)的Clifford模塊實現(xiàn)，該模塊可以將歐氏空間的點轉(zhuǎn)換為共形幾何代數(shù)空間形式，并進(jìn)行內(nèi)積、外積和幾何積等基本運算。

對圖4所示2架航班，在10∶49∶27前，計劃推入跑道的航班CCA8286(波音737機型，長度37.57 m)在RPZ內(nèi)，從西北方向準(zhǔn)備進(jìn)場的航班CCA8284(波音737機型)不在RPZ內(nèi)，此時經(jīng)本文跑道侵入算法檢測到CCA8284不發(fā)生跑道侵入，系統(tǒng)也不產(chǎn)生告警。

圖4 未發(fā)生跑道侵入Fig.4 No runway incursions

隨著飛行器繼續(xù)運行，在10∶49∶27時檢測出CCA8284和CCA8286同時處在RPZ內(nèi)，即CCA8284對CCA8286產(chǎn)生了跑道侵入，系統(tǒng)產(chǎn)生跑道侵入告警提示，如圖5和圖6所示。此時利用本文沖突檢測算法進(jìn)行沖突檢測，結(jié)果為CCA8284和CCA8286并不沖突，但此時仍然發(fā)出跑道侵入告警，隨著飛行器的繼續(xù)運行，需要繼續(xù)進(jìn)行沖突檢測。

圖5 未發(fā)生沖突的跑道侵入Fig.5 Runway incursion without conflict

圖6 告警記錄Fig.6 Alarm record

在10∶49∶45時檢測出2機發(fā)生沖突，如圖7所示，此時系統(tǒng)產(chǎn)生跑道沖突提示告警，需立即進(jìn)行沖突解脫。在10∶49∶51時，由于降落的飛行器操作優(yōu)先級大于穿越跑道的飛行器，所以CCA8286減速至停止，CCA8284正常降落，變成跑道侵入狀態(tài)，系統(tǒng)中產(chǎn)生跑道侵入提示告警，如圖8所示。

圖7 跑道侵入并發(fā)生沖突Fig.7 Runway incursion and conflict

圖8 沖突后解脫Fig.8 Liberation after conflict

本文方法本質(zhì)上是共形幾何代數(shù)空間中判斷點面關(guān)系及計算距離的檢測方法，因此，在相同條件及數(shù)據(jù)下通過實驗復(fù)現(xiàn)了文獻(xiàn)[1-2]中歐氏空間基于射線法和距離計算的跑道侵入和沖突檢測算法，和本文算法檢測結(jié)果一致。

實驗中對各時刻對應(yīng)的跑道侵入檢測過程占用CPU時間進(jìn)行了統(tǒng)計和對比。表3為在10∶49∶27 時刻發(fā)生跑道侵入以前，隨機選取5個時刻的跑道侵入檢測耗時結(jié)果。其中在10∶49∶27時刻，由于在該時刻發(fā)生了跑道侵入，需要完整判斷航班CCA8284與圍成跑道保護區(qū)的所有面之間的位置關(guān)系，故該時刻完成一次跑道侵入判斷的用時最長。而其他時刻只需要判斷航班與部分面之間的位置關(guān)系，耗時較短。結(jié)果表明：文獻(xiàn)[1-2]中歐氏空間的跑道侵入算法平均用時63 ms，而本文跑道侵入算法平均用時21 ms。即使是在跑道保護區(qū)所有面都參與運算的情況下，本文方法的運算速度也比傳統(tǒng)歐氏空間算法速度快近1.5倍。

表3 跑道侵入耗時對比Table 3 Time-consumption of runway incursion conflict

這是因為：① 文獻(xiàn)[1-2]中跑道侵入算法需建立坐標(biāo)系，確定RPZ邊界平面的方程，將點代入多面體的邊界平面方程計算經(jīng)過點的有向射線與多面體的交點個數(shù)來判斷位置關(guān)系，需要解線性方程。實際計算中還需要考慮點在多面體(RPZ)的邊界或所圍面上、點在多面體所圍面的延長面上、點的射線與多面體相交于多面體的頂點上等特殊情況，需要判斷的因素過多，較為復(fù)雜，減少工作效率。② 本文算法在共形幾何代數(shù)空間中將有界的保護區(qū)通過無界的平面組合進(jìn)行表示，只需要通過外積運算考慮各個點相對于保護區(qū)各面的方向就可以確定位置關(guān)系，無需建立坐標(biāo)系及求解線性方程組，減少了運算量。③ 本文實驗使用Python中基于Gaigen系統(tǒng)的Clifford模塊實現(xiàn)共形幾何代數(shù)運算，通過布爾運算和預(yù)編譯實現(xiàn)了高性能的計算，在內(nèi)積等算子運算上效率高于歐氏空間的線性代數(shù)運算效率。因此相對于歐氏空間跑道侵入計算方法，本文用時較短。

對于RPZ中的沖突檢測效率，實驗中發(fā)生跑道侵入后對各時刻對應(yīng)的沖突檢測過程占用CPU時間進(jìn)行了統(tǒng)計和對比。其中表4為在10∶49∶27發(fā)生跑道侵入以后，隨機選取5個時刻的沖突檢測耗時結(jié)果?？梢钥闯霰疚乃惴▽τ赗PZ中的沖突檢測效率也優(yōu)于文獻(xiàn)[1-2]中沖突檢測算法。這是因為本文算法利用共形幾何代數(shù)的多維統(tǒng)一表示將水平和垂直方向維度的屬性統(tǒng)一起來，只需要考慮2飛行器保護區(qū)(球)之間的內(nèi)積運算即可確定是否沖突。而歐氏空間需要分別判斷水平和垂直方向的距離，向高維擴展較困難，基于復(fù)雜場景的算法結(jié)構(gòu)復(fù)雜，從而計算效率低。共形幾何代數(shù)運算不需要建立坐標(biāo)系，在沖突檢測中減少計算量。

表4 沖突檢測耗時對比Table 4 Comparison of time-consumption of conflict detection

4 結(jié) 論

建立了機場跑道保護區(qū)和飛行器保護區(qū)模型的共形幾何代數(shù)描述方法，基于共形幾何代數(shù)的外積和內(nèi)積運算分別提出了共形幾何代數(shù)空間的跑道侵入和跑道沖突檢測算法。研究結(jié)果表明：

1) 基于共性幾何代數(shù)的跑道侵入算法，由于將有界的保護區(qū)通過無界的平面組合進(jìn)行表示，只需要通過外積運算考慮各個點相對于保護區(qū)各面的方向，減少了建立坐標(biāo)系對算法效率的影響，避免了歐氏空間中各種特殊情況的處理，邏輯簡單，用時較短。

2) 基于共形幾何代數(shù)的跑道沖突檢測算法，利用共形幾何代數(shù)的多維統(tǒng)一表示將水平和垂直方向維度的屬性統(tǒng)一起來，只需要考慮2飛行器保護區(qū)(球)之間的內(nèi)積運算即可確定是否沖突。避免了歐氏空間中低維向高維擴展這一難點，算法結(jié)構(gòu)簡單，計算效率高。

3) 實驗表明基于共形幾何代數(shù)的跑道侵入與沖突檢測方法能夠快速、準(zhǔn)確地判斷跑道侵入及沖突的發(fā)生，相比于歐氏空間方法在運算效率上有顯著提高。

4) 鑒于共性幾何代數(shù)優(yōu)越的空間表達(dá)能力和運算效率，民航中仍有許多應(yīng)用可以基于共形幾何代數(shù)方法進(jìn)行描述，如飛行程序驗證中的障礙物評估以及飛行器航跡預(yù)測等。