蔡 明，萬路軍，高志周，徐鑫宇

（空軍工程大學空管領航學院,陜西 西安 710051）

聯(lián)合作戰(zhàn)涉空力量多元、涉空行動多樣，無論是地對地、地對空、空對地，還是艦對空、艦對艦等作戰(zhàn)行動，都要涉空用空，戰(zhàn)場空域變得越來越擁擠，如何對戰(zhàn)場空域沖突進行高效檢測，是制約聯(lián)合作戰(zhàn)水平提升的重點、難點問題[1]。軍航的各類航空器的高機動、高速度等特性，決定了與民航航空器沖突檢測存在顯著的差異。例如地空導彈和殲擊機的飛行速度和機動性能要比民航飛機強得多，導致航向諸元變化極快，飛行狀態(tài)及位置極難預測；同時，現(xiàn)代戰(zhàn)爭的高烈度導致成千上萬件武器裝備在同一時間單元、有限的戰(zhàn)場空域內協(xié)同作戰(zhàn)，故無法使用現(xiàn)有的民航飛機之間的飛行沖突檢測方法對其進行一一檢測。因此，可行的做法是諸軍兵種向空域管理部門申請所需空域。這些申請的空域通常會發(fā)生相互交織，空域沖突檢測即檢測不同空域之間的間隔是否滿足安全間隔規(guī)定，通過安全間隔將各類型飛行器所在的活動空域隔離開。對于檢測無沖突的空域，空域內的飛行器活動軌跡必須遵守該空域的使用規(guī)則，以防止飛行沖突，提升空域使用效率。

空域之間的沖突檢測問題，核心目標是確定空域之間是否滿足安全間隔標準，可以抽象為兩個多面體之間的碰撞檢測問題。為此，國內外學者進行了大量的探索，目前比較常用的有基于掃描實體的算法[2]、應用閔可夫斯基和集與球面高斯映射相結合的方法[3]、保守前進算法及其改進算法以及線性連續(xù)碰撞檢測（Linear continuous collision detection）算法[4]。上述方法只能檢測出空域間有無重疊，對于無重疊的空域即認為無沖突。實際上，在無重疊的基礎上還應滿足空域間的最小安全間隔，才能確定空域無沖突。

Gilbert-Johnson-Keerthi 算法(簡稱GJK 算法)是一種通過向量映射構成閔可夫斯基差集（Minkowski Difference），可以較快計算得到兩物體間的最小距離并檢測碰撞的漸進算法[5]，也是目前多面體間相交檢測問題和距離計算問題最為有效的幾何算法之一[6]。該算法在物理仿真、機器人碰撞檢測和虛擬現(xiàn)實等領域有著十分廣泛的應用。

針對高效空域沖突檢測的現(xiàn)實需求，本文以北京大學程承旗教授等[7]提出的2n一維整型數組全球經緯剖分網格（Geographic Coordinate Subdividing Grid with One Dimension Integral Coding on 2n-Tree，GeoSOT）為基礎，將空域表達為多層級、多尺度的網格集合，為了提高空域沖突檢測算法的準確性與高效性，建立了在GeoSOT 剖分網格系統(tǒng)下基于GJK 算法的空域沖突檢測模型。

1 GeoSOT 剖分網格系統(tǒng)

GeoSOT 剖分網格系統(tǒng)由北京大學程承旗教授[8?9]所帶領的團隊提出，屬于等經緯度的四叉樹剖分網格體系。其核心思想是將整數“度”及整數“分”級網格進行邏輯上的外延，使得網格具有整數特征；同時，較完備地實現(xiàn)了大到整個地球、小到厘米級面片的全球四叉樹格網結構。格網上下級別之間的父子面片、面積之比大致都為4∶1，并且與我國及世界各國主要的規(guī)格地理格網之間都具有一致性聚合特性[10]。

在網格的剖分方式上，為確保下一級面片能在上一級面片的基礎上進行四叉劃分，生成的網格編碼為整數，將地球表面進行了3 次擴展[11]。第1次擴展將180°×360°地球表面空間擴展為512°×512°；同時，為了保證經緯線上嚴格整型二分，進一步對1°和1′的面片進行擴展，即從1°等于60′擴展到1°等于64′；從1′等于60″擴展到1′等于64″，建立起全球空間GeoSOT 剖分框架網格基礎[12]。GeoSOT各層級面片與尺度對應關系見表1。

表1 GeoSOT 各層級與尺度對應關系

GeoSOT 網格編碼具有四進制一維、二進制一維、二進制二維以及十進制二維4 種形式[13]。這種編碼方式使得得到編碼能夠與計算機處理模式以及經緯度語義形成一致，各種進制編碼之間能夠快速轉換。

以我國北京市天安門城樓的經緯度坐標（39°54′20″N，116°25′29″E）為例，說明經緯度坐標與網格編碼之間的轉化方法。由于經度值116°25′29″小于256°和128°，故網格編碼的前兩位均為0；同時116°25′29″/64°=1 余52°25′29″，則第3 位編碼為1；再將網格剖分到大小為32°的第4 層級，52°25′29″/32°=1 余20°25′29″，則第4 位編碼也為1，以此類推，最后得到在第16 層級（32″×32″）網格精度下，二進制經度編碼為0011101000110010。同理，得到二進制緯度編碼為0001001111101100。將緯度編碼與經度編碼交叉得到天安門城樓所在的第16 層級網格的一維二進制編碼為G00000 111010011101010110110100100，轉化為一維四進制編碼為G001310322-2 312 210，如圖1 所示。

圖1 天安門城樓位于第16 層級網格下的編碼

2 GJK 算法

GJK 算 法（Gilbert-Johnson-Keerthi 算 法）由Gilbert、Johnson、Keerthi 三位學者提出的。該算法通過計算兩個物體之間的距離來進行多面體碰撞檢測，本質上是在單純形上逐步尋找距原點最近點的漸降方法[5]。

假設有兩多面體A 和B，A 與B 之間的距離d(A,B)可用式（1）來表示：

若取到物體A 和B 上的相鄰最近的兩點a和b時，一定滿足式（2）：

同時引入閔可夫斯基差集的概念。閔可夫斯基差集用多面體A的所有點減去多面體B 中所有的點得到的一個點集合，可用式（3）表示：

閔可夫斯基差集的意義在于，得到兩個多邊形頂點間的坐標分布關系，如果兩個多邊形相交，那么差集中點會分布在坐標原點四周，也就是說差集會包含原點。差集有一些特殊的性質，差集構成的多邊形的形狀與兩個多邊形之間的距離沒有直接關系。兩個多邊形距離越大，則差集的中心位置離原點越遠，反之離原點越近。如果相交，則差集多邊形會包含原點。那么多面體A 與多面體B 之間的距離就可以用|minm(A,B)|表示，描述為式（4）：

通過引入閔可夫斯基差集的概念，可將兩多面體之間的沖突檢測問題轉化為判斷兩多面體之間構成的閔可夫斯基差集是否包含原點的問題。通過轉化，大大簡化了求解難度，也使計算結果更加直觀清晰，如圖2 所示。

圖2 (b) 閔可夫斯基差集與原點之間的距離

圖2 (a) 多面體A 與B 之間的距離

3 空域沖突檢測模型的建立

3.1 構建安全包圍盒

在進行空域沖突檢測時，不僅要計算空域間是否發(fā)生重疊，還要考慮空域間隔是否滿足安全間隔標準。當兩個空域發(fā)生重疊或者間隔小于最小安全間隔D 時，則判定兩個空域之間存在沖突。

首先根據文獻[14]所介紹的空域網格化表達方法，將空域表達為某一層級網格的集合，然后為了在沖突檢測模型中充分考慮到最小安全間隔D，考慮構建空域的安全包圍盒。構建安全包圍盒的方法有兩種，第一種方法是將其中一個空域向四周擴大距離D，構建安全包圍盒，另一個空域保持不變。第二種方法是將兩個空域空間各外擴大D/2，分別構建安全包圍盒。本文將空域間最小安全間隔D設定為16 km。當面對大量待檢測空域時，第一種方法的局限性就比較明顯。因為僅僅對一個空域進行外擴構建安全包圍盒，不能保證任意選擇的兩個空域都已構建安全包圍盒，導致檢測結果存在大量誤差。

3.2 網格體系下空域沖突檢測

步驟1：建立網格剖分體系和編碼規(guī)則，建立經緯度坐標與網格編碼之間的轉換關系。

步驟2：對空域進行網格化表達。將空域范圍分割為第13 級網格（8km×8km）的集合，并通過有序的網格編碼建立數據結構，對空域進行記錄和組織。

步驟3：建立空域的安全包圍盒。由于空域間最小安全間隔為D/2，故將各個空域范圍向外膨脹D/2。本文中，將空域向外膨脹一個網格即為安全包圍盒。

步驟4：建立坐標系，將包圍盒的網格編碼轉化為坐標。

步驟5：利用GJK 算法，兩兩逐對計算空域間的閔可夫斯基差集，判斷其與原點的包含關系，檢驗兩兩空域間是否存在沖突。

步驟5 中，設要檢測兩個空域1 和2，構建兩空域間的閔可夫斯基差集的方法為：在空域1的包圍盒上隨機抽取一個坐標A，在空域2的包圍盒上隨機抽取一個坐標B作矢量差，并將得到的結果儲存至數組中。多次迭代循環(huán)，就構成了所求的閔可夫斯基差集。最后，再將閔可夫斯基差集中的點在坐標系中生成圖像點集，并與原點（0,0）的位置進行比較，通過判別生成的閔可夫斯基圖像點集是否包含原點，進而判斷兩空域是否發(fā)生沖突。

4 仿真實驗及結果

假設某一區(qū)域內同時存在3 個空域，3 個空域的參數為如下。

1）空域1的中心點經緯度為（31°12′26″N，119°12′26″E）?？沼蛐螤顬殚L方體，長度為64 km，寬度為32 km，高度上限為7 km，高度下限為3 km。

2）空域2的中心點經緯度為（31°32′34″N，119°24′20″E）?？沼蛐螤顬檎襟w，長度為48 km，寬度為48 km，高度上限為8 km，高度下限為5 km。

3）空域3的中心點經緯度為（31°48′15″N，120°00′30″E）?？沼蛐螤顬榍蝮w，空域半徑為24 km，高度上限為9 km，高度下限為4 km。

將3 個空域進行網格化表達之后如圖3 所示。對上述3 個空域，兩兩進行沖突檢測。

圖3 目標空域的網格化表達

綜合考慮時間成本和檢測準確度，將算法的迭代次數設定為10 000，得到的閔可夫斯基差集中有10 000 個元素，再將這些元素點在坐標系中生成，結果如圖4 所示。

圖4 空域沖突檢測結果

圖4（a）直觀清晰地展現(xiàn)出了閔可夫斯基差集點群與坐標原點（0,0）的關系，可以確定坐標原點在生成的閔可夫斯基差集點群內部，即空域1 和空域2 存在沖突威脅。通過圖4（b）和圖4（c），可以確定坐標原點在生成的閔可夫斯基差集點群之外，即空域1 和空域3 之間，以及空域2 和空域3 之間均不存在沖突。

目前，傳統(tǒng)的空域沖突檢測都是在經緯度坐標體系下，采用幾何解析或智能算法進行求解，將空域看成各類幾何體，通過幾何體之間有無相交，判定空域之間是否產生沖突。根據預期劃設空域的數據參數（中心點位置、長度、寬度和高度等），將空域邊界點轉換為經緯度值并在計算機里表示為編碼的集合。通過查詢編碼集合之間有無交集，確定空域之間是否發(fā)生重疊，并判定空域之間的距離是否滿足安全間隔規(guī)定，最終進行沖突判定。

傳統(tǒng)的空域沖突檢測方法雖然便于理解操作簡單，但是具有局限性較多、易導致誤差的缺點。導致誤差的原因主要在于經緯度坐標體系下單位度量差值距離固定，不夠靈活。在傳統(tǒng)經緯度坐標體系下，單位緯度長度分別為1″≈30.8 m，1′≈1.85 km，1°≈111 km。單位經度長度的計算方法為該地區(qū)單位緯度的距離×該地區(qū)緯度的余弦值。

在日?？沼騽澰O中，空域大小長度一般在30～100 km 之間。通過經緯度度量值可以粗略將空域1、空域2 和空域3的邊界點的經緯度值的集合表示出來（為方便表示取4 個頂點為特征點）。

利用傳統(tǒng)空域沖突檢測方法通過將各個空域的邊界點的經緯度值集合表示出來后，并不能直接對空域是否發(fā)生沖突進行判斷。若想通過計算機對集合之間進行運算，則需要將空域邊界點的經緯度值的集合盡可能多地列舉出來，工作量較大，并且受經緯度單位差值距離固定的影響，仍然可能存在兩片空域存在沖突，但是集合中未能列舉出兩片空域的沖突點的情況。

同時，由于經緯度單位差值固定不靈活，且經緯度值計算時同時涉及度、分、秒三級數值對的計算與變化，所以計算較為復雜，工作量較大。

與傳統(tǒng)空域沖突檢測方法相比，利用GJK 算法將兩空域包圍盒之間的相交檢測轉化為對閔可夫斯基差集與坐標原點的包含關系的判斷，簡化了沖突檢測模型，降低了工作量，同時使實驗結果表示得更加清晰直觀。

5 結論

高效準確地對多個單位在同一區(qū)域同一時間段內的空域申請進行高效的沖突檢測，對于保障飛行活動的正常有序開展，保證飛行安全至關重要。為此，本文提出了一種在GeoSOT 網格體系下結合GJK 算法的空域沖突檢測算法。該算法以GeoSOT 網格為工具，利用空域網格表征和時空二值計算上的優(yōu)勢，將空域之間的相交檢測轉化為閔可夫斯基差集與坐標原點的包含關系，對問題進行了抽象和簡化，實驗結果以較為清晰明確的圖形關系顯現(xiàn)出來，易于論證與檢驗。本文只研究了網格體系下的空域沖突檢測，對于如何將存在的空域沖突進行一體化消解，將是下一步研究的重點。