空間網(wǎng)格體系下基于GJK的空域沖突檢測(cè)算法

蔡 明，萬(wàn)路軍，高志周，徐鑫宇

（空軍工程大學(xué)空管領(lǐng)航學(xué)院,陜西 西安 710051）

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

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

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

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

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

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

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

表1 GeoSOT 各層級(jí)與尺度對(duì)應(yīng)關(guān)系

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

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

圖1 天安門城樓位于第16 層級(jí)網(wǎng)格下的編碼

2 GJK 算法

GJK 算 法（Gilbert-Johnson-Keerthi 算 法）由Gilbert、Johnson、Keerthi 三位學(xué)者提出的。該算法通過(guò)計(jì)算兩個(gè)物體之間的距離來(lái)進(jìn)行多面體碰撞檢測(cè)，本質(zhì)上是在單純形上逐步尋找距原點(diǎn)最近點(diǎn)的漸降方法[5]。

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

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

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

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

通過(guò)引入閔可夫斯基差集的概念，可將兩多面體之間的沖突檢測(cè)問(wèn)題轉(zhuǎn)化為判斷兩多面體之間構(gòu)成的閔可夫斯基差集是否包含原點(diǎn)的問(wèn)題。通過(guò)轉(zhuǎn)化，大大簡(jiǎn)化了求解難度，也使計(jì)算結(jié)果更加直觀清晰，如圖2 所示。

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

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

3 空域沖突檢測(cè)模型的建立

3.1 構(gòu)建安全包圍盒

在進(jìn)行空域沖突檢測(cè)時(shí)，不僅要計(jì)算空域間是否發(fā)生重疊，還要考慮空域間隔是否滿足安全間隔標(biāo)準(zhǔn)。當(dāng)兩個(gè)空域發(fā)生重疊或者間隔小于最小安全間隔D 時(shí)，則判定兩個(gè)空域之間存在沖突。

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

3.2 網(wǎng)格體系下空域沖突檢測(cè)

步驟1：建立網(wǎng)格剖分體系和編碼規(guī)則，建立經(jīng)緯度坐標(biāo)與網(wǎng)格編碼之間的轉(zhuǎn)換關(guān)系。

步驟2：對(duì)空域進(jìn)行網(wǎng)格化表達(dá)。將空域范圍分割為第13 級(jí)網(wǎng)格（8km×8km）的集合，并通過(guò)有序的網(wǎng)格編碼建立數(shù)據(jù)結(jié)構(gòu)，對(duì)空域進(jìn)行記錄和組織。

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

步驟4：建立坐標(biāo)系，將包圍盒的網(wǎng)格編碼轉(zhuǎn)化為坐標(biāo)。

步驟5：利用GJK 算法，兩兩逐對(duì)計(jì)算空域間的閔可夫斯基差集，判斷其與原點(diǎn)的包含關(guān)系，檢驗(yàn)兩兩空域間是否存在沖突。

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

4 仿真實(shí)驗(yàn)及結(jié)果

假設(shè)某一區(qū)域內(nèi)同時(shí)存在3 個(gè)空域，3 個(gè)空域的參數(shù)為如下。

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

2）空域2的中心點(diǎn)經(jīng)緯度為（31°32′34″N，119°24′20″E）。空域形狀為正方體，長(zhǎng)度為48 km，寬度為48 km，高度上限為8 km，高度下限為5 km。

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

將3 個(gè)空域進(jìn)行網(wǎng)格化表達(dá)之后如圖3 所示。對(duì)上述3 個(gè)空域，兩兩進(jìn)行沖突檢測(cè)。

圖3 目標(biāo)空域的網(wǎng)格化表達(dá)

綜合考慮時(shí)間成本和檢測(cè)準(zhǔn)確度，將算法的迭代次數(shù)設(shè)定為10 000，得到的閔可夫斯基差集中有10 000 個(gè)元素，再將這些元素點(diǎn)在坐標(biāo)系中生成，結(jié)果如圖4 所示。

圖4 空域沖突檢測(cè)結(jié)果

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

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

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

在日?？沼騽澰O(shè)中，空域大小長(zhǎng)度一般在30～100 km 之間。通過(guò)經(jīng)緯度度量值可以粗略將空域1、空域2 和空域3的邊界點(diǎn)的經(jīng)緯度值的集合表示出來(lái)（為方便表示取4 個(gè)頂點(diǎn)為特征點(diǎn)）。

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

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

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

5 結(jié)論

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