復雜低空無人機飛行沖突網絡建模與精細管理

謝華，蘇方正，尹嘉男，*，韓斯特，張新玨

1.南京航空航天大學 通用航空與飛行學院，南京 210016

2.南京航空航天大學 民航學院，南京 210016

隨著國家低空空域管理改革的不斷推進，民用無人機飛行需求呈現迅猛增長趨勢，作為低空空域系統內的新興用戶，無人機目前已在商業、公共、軍事、旅游、體育和防疫等領域得到廣泛應用［1］。例如，在新冠肺炎疫情期間，無人機常被用于執行疫苗運輸、物資配送、安全巡邏等各類任務［2］。2021年，中共中央、國務院在《國家綜合立體交通網規劃綱要》中首次提出要大力發展以低空空域為依托、以無人機和通航產業為主導的“低空經濟”，這為無人機在智慧城市中的規模化應用帶來了前所未有的發展機遇。

未來，無人機將在管制空域和監視、報告等非管制空域獲得更大的自由活動權，而其高靈活和高機動特性［3］將隨之帶來一系列安全問題，并成為國內外航空界的關注焦點。尤其是在無人機逐步融入整個國家空域系統的趨勢下，其運行安全水平還將影響公共運輸航空、軍事航空等傳統空域用戶。因此，研究復雜低空無人機飛行沖突網絡建模與精細管理問題，成為當前及未來相當長一段時期內國際空管領域的研究熱點和難點。

國內外在空域運行沖突管理領域已取得一系列研究成果，相關學者圍繞沖突探測與解脫提出了諸多模型和算法。例如，Weinert等［4］針對低空作業場景，提出了一種基于空中碰撞風險的沖突管理方法，并對低空安全風險閾值進行了定義與度量；Mullins等［5］考慮入侵無人機的速度和性能，采用時間閾值代替空間距離閾值，提出了動態分離閾值的無人機沖突探測避碰模型。目前，使用最為廣泛的航空器沖突探測方法大多基于幾何計算，即通過每架航空器的飛行計劃所需空域進行交叉判定是否有存在沖突［6-7］，該方法雖可準確計算無人機飛行計劃沖突以及航跡沖突點，但是對于大規模的空域沖突檢測效率較低。

為此，空域柵格化為無人機沖突檢測提供了一種新的視角，該方法通過對空域進行柵格化處理，將其離散分解成一系列柵格單元，以此構建空域數據結構，進而可通過查詢數據庫表的方式進行沖突探測。Pongsakornsathien等［8］采用空域離散化方法，提出了一種新型的無人機系統交通管理（Unmanned Aircraft System Traffic Management， UTM）空域模型，實現了低空空域資源的動態管理。Zhai等［9］構建了基于空域柵格的空間數據庫，建立了無人機碰撞檢測模型。顧俊偉［10］提出基于4D網格的飛行沖突初篩算法，對多航空器間的飛行沖突進行探測。謝華等［11］提出了基于改進速度障礙法的無人機飛行沖突探測方法，設計了無人機飛行沖突解脫策略及其適用條件，構建了以最小化沖突解脫時間成本為導向的無人機飛行沖突解脫策略最優配置規則及實施流程。付其喜等［12］基于數學優化理論，提出了多機沖突解脫的雙層優化算法。Virágh等［13］通過設定安全間隔，基于幾何方法對二維和三維空間內交通密集場景下的飛行沖突進行研究。Innocenti等［14］引入了一種基于概率函數域的空中交通管制無沖突航跡生成方法，并開展了不同初始條件下的仿真。Alonso-Ayuso等［15］針對不同場景下的無人機運行情況建立非線性混合整數規劃模型，判斷無人機在特定約束條件下是否會發生沖突。Tang等［16］基于經典蟻群算法，提出了一種基于速度調整策略和航向調整策略的多無人機沖突解脫方法，提高了計算效率。Cecen等［17］采用兩階段優化方法，建立了自由航路空域航空器沖突解脫模型，并應用元啟發式算法進行了求解。Pang等［18］提出了多機沖突解脫的雙層優化自適應決策框架，改進了一種新的元啟發式隨機分形搜索算法，顯著優化了航空器的四維航跡。張宏宏等［19］將“核仁解”的概念應用于沖突解脫領域，提出了基于優先級與公平性的沖突解脫算法。管祥民和呂人力［20］采用滿意博弈論方法，研究了基于改變航向角策略的多無人機沖突解脫問題，通過解脫順序優化實現了全局沖突解脫。

然而，當前研究仍存在以下不足：① 無人機沖突分析主要聚焦特定場景中的無人機個體沖突特征，未充分考慮全局層面無人機群體沖突網絡的動態構建及其演化特性；② 無人機沖突探測主要基于預先設定的粗放式低空空域單元，未對無人機空間運行環境進行多層級分解建模，不能有效滿足無人機飛行沖突的精細探測需求；③ 無人機沖突解脫主要聚焦統一規則下的兩機或多機沖突場景，未充分考慮無人機個體調配優先級的差異對無人機群體層面的間接性波及影響。

本文針對多元化空域、高密度流量和高動態演化交織形成的復雜低空系統，通過構建基于沖突連邊動態識別的無人機飛行沖突網絡模型及特征參數，提出基于數字柵格的無人機飛行沖突精細探測算法，建立考慮優先級的無人機飛行沖突最優解脫方法，旨在實現低空無人機飛行沖突的精細化管理，為低空空域安全管理與無人機運行風險防控提供理論支撐和方法指導。

1 無人機飛行沖突網絡建模及特征分析

本節采用GJK算法，構建了基于沖突連邊動態識別的無人機飛行沖突網絡模型，以平均沖突數量、平均運行風險和平均聚集系數等指標表征無人機飛行沖突網絡特征，分析了無人機飛行沖突的動態演化特征。

1.1 模型構建

1.1.1 GJK算法框架及流程

GJK算法［21］是一種計算凸體之間距離的迭代方法，該方法通過向量映射構成閔可夫斯基差集（Minkowski Difference）。每架無人機可表示為一個立方體，滿足GJK算法中的凸體計算。GJK算法計算2個立方體之間的距離，無人機A和無人機B之間的距離可表示為立方體A和立方體B之間的距離d(A，B)，定義為

式中：x和y分別表示立方體A和立方體B中的點；立方體A和B之間距離最近的2個點a∈A和b∈B滿足‖ ‖a-b=d(A，B)。

在此基礎上，進一步引入2個相關概念。

1） 閔可夫斯基差集

閔可夫斯基差集是立方體A的所有點和立方體B的所有點的差值構成的點集合，可表示為

2個立方體的閔可夫斯基差集所構成的凸包稱為配置空間障礙（Configuration Space Obstacle，CSO）。立方體A和B之間的距離可用閔可夫斯基差集表示為

則2個立方體之間的碰撞檢測可使用閔可夫斯基差判斷：當且僅當2個立方體的閔可夫斯基差集Mk(A，B)包含原點時，無人機A和B發生碰撞。

通過上述變化，可將立方體A和B之間的距離轉化為兩者的閔可夫斯基差與原點的距離，如圖1所示，通過判斷差集是否包含原點來確定2個無人機是否發生碰撞。

圖1 閔可夫斯基差集距離轉換示意圖Fig.1 Schematic of Minkowski difference set conversion

將3個相同類型的無人機A、B、C表示為3個相同大小的立方體A、B和C，如圖2所示，A和B接觸，C和A、B遠離，將算法迭代次數設置A、B和C為5 000次，因此得到的閔可夫斯基差集中包含5 000個點，將這些元素點置于坐標中顯示，A與B、A與C的閔可夫斯基差結果如圖3所示。

圖2 無人機的立方體表達Fig.2 Cube representation of UAVs

圖3 閔可夫斯基差集結果Fig.3 Result of Minkowski difference set

圖3直觀展示出了閔可夫斯基差集與原點的關系，如圖3（a）所示，原點位于立方體A與B生成的閔可夫斯基差集內部，為了直觀表現同時給出了二維側視圖，原點位于差集內部則表明二者發生沖突；而立方體A與C不存在沖突，則原點位于兩者的閔可夫斯基差集外部，如圖3（b）所示。

2） 支撐函數

對于給定的立方體，沿著特定方向d且距離該立方體最遠的一點P，稱作該立方體的支撐點。即對于立方體C中的任意一點x，存在d·P=max{d·x：x∈C}，則P為 立方體C的支撐點。算法利用支撐函數建立一個單純形，對于給定的2個立方體，支撐函數返回這2個立方體閔可夫斯基差形狀中的一個點。構造函數h：

該函數的含義是在閔可夫斯基差集Mk中尋得一點x，使得點x在方向d上的有向投影值h最大，使得函數取最大值的x記作SMk(d)，將SMk(d)定義為立方體的支撐函數，其含義為對于閔可夫斯基差集Mk，將方向d映射到Mk的支撐點。SMk(d)和hMk(d)關系表示為

因此，算法本身并不需要直接計算閔可夫斯基差，而是通過計算SMk(d)函數反映CSO與原點的位置關系，利用立方體A和B可以計算得到：

由于閔可夫斯基差每次都得到相同的點，會大大增加算法復雜度。因此，構造支撐函數的目的在于：通過支撐函數傳遞一個方向參數，方向不同，得到的點也不同，避免無效計算，同時使得算法迭代產生的單純形盡可能包含更大的空間區域，加快算法迭代進程。

GJK算法本質是通過在CSO邊界上降序迭代，在單純形上逐步尋找距原點最近的點。在每次迭代過程中會在CSO內部生成一個單純形，并且保證下一次生成的單純形的頂點更靠近原點，將第k次迭代中生成的單純形定義為τk。若將P(τk)定義為單純形τk上距離原點最近的一個點，該點可以通過Johnson算法計算得到，當P(τk)=P(CSO)時，存在唯一向量χ(CSO)滿足：

即找到CSO上距離原點最近的點，當該點與原點的距離為所求最小距離d時，算法結束。

GJK算法迭代過程如下：

初始設置τ0=?，P(τ0)為CSO中任意一點。

步驟1初始化單純形τk為CSO中的一個或多個頂點。

步驟2利用Johnson算法計算得到P(τk)。

步驟3若P(τk)為原點O，則表明原點O位于CSO中，即立方體A和立方體B發生碰撞，算法結束并返回“立方體A與B發生碰撞”。否則，轉入步驟4。

步驟4對于τk中不包含頂點P(τk)的子單純形，將其頂點從單純形中移除；

步驟5令Pk=SMk(-d(τk))為-χ(τk)方向-d(τk)上的支撐點。

步驟6將支撐點與頂點P(τk)進行比較，若支撐點Pk在-d(τk)方向上投影值并非極值點，即‖χ(τk)‖2+SMk(-d(τk)) · (-d(τk))=0，則算法結束并返回“立方體A與B無碰撞”，立方體A和立方體B之間的距離為原點O指向頂點P(τk)的向量長度‖ ‖χ(τk)。否則，轉入步驟7。

步驟7 將支撐點Pk加入單純形τk中，轉入步驟2，進行迭代。

1.1.2 無人機飛行沖突網絡模型

前文敘述了GJK算法應用于2個立方體的碰撞檢測，由于低空空域內無人機以連續狀態運行，以GJK算法為基礎，將算法推廣到判斷一段連續時間內兩架無人機是否會發生沖突，提出無人機飛行沖突網絡模型動態構建算法，應用于多無人機運動場景［22］。

假設低空空域內有多架無人機進行勻速直線隨機飛行，選取2架無人機A和無人機B，設定時間區間為[t0，t0+Δt]，其速度分別為vA和vB。Vi表示立方體A和立方體B的頂點，在初始時刻t0，立方體A各頂點位置為SA(t0)=立方 體B各 頂 點 位置 為SB(t0)={VB0(t0)，VB1(t0)，…，VBn-1(t0)}，m和n表示立方體A和立方體B的頂點數。在[t0，t0+Δt]時間內，立方體A和立方體B的頂點位置在時刻t可表示為

式中：?t：t=t0+λ·Δt，t∈[t0，t0+Δt]；λ∈[0，1]；i∈{0，1，…，m-1}；j∈{0，1，…，n-1}。

以無人機A作為主動沖突識別對象，設SM為立方體A和立方體B的CSO，在時段[t0，t0+Δt]內，由式（8）和式（9）可得SM的頂點位置為

在一段時間內SM移動構成了近似矩形的區域，如圖4所示，其運動軌跡為

圖4 [t0，t0+Δt]時間段CSO運動軌跡Fig.4 Trajectory of CSO at time [t0，t0+Δt]

每一個頂點ViMj(t)從t0到t0+Δt形成一條軌跡，在SM移動過程掃描過的區域所有頂點的移動軌跡都是等長的，長度為‖ traM(1)‖。

利用GJK算法進行沖突網絡構建的方法是判定一段時間內CSO距離原點的最小距離，CSO的運動具有時空連續性，因此只需判定原點到CSO頂點軌跡的最小距離。若2架無人機未發生沖突，則原點在CSO外部，且與CSO最小距離為邊界軌跡到原點的距離；若發生沖突，則原點在CSO內部，且在某2個頂點的運動軌跡之間。因此計算原點與CSO的距離可轉化為原點與CSO邊界軌跡的距離dO：

原點O與CSO邊界軌跡的距離是通過找到合適的^來確定，根據文獻［23］，通過割線法進行實驗=0.5左右時距離較小，最小距離為

因此，解決問題分成2個步驟：首先找到距離原點最近的CSO頂點軌跡，其次計算原點與最近軌跡點的最短距離。算法偽代碼如算法1所示。

算法1 基于GJK的沖突網絡構建算法輸入：t0，SA(t0)，SB(t0)，Δt，traM(λ)輸出：（“未發生沖突” ，λc，dO）或（“發生沖突”）1.k=0， V~k={VA0(t0)-VB0(t0)}2.do 3.（λ^，dO，OM，V~k′，Oin）←Johnson algorithm 4.if Oin then 5.return （“發生沖突”）6.caculate SM(-OM)，S′M(-OM，λ^)7.if SM(-OM)=S′M(-OM，λ^) then 8.V~k+1=V~′k∪{SM(-OM)}9.else V~k+1=V~′k∪{SM(-OM，λ^)}10.end if 11.k=k+1 12.while true 13.λc=λ^； dO=d^O 14.return （ “未發生沖突”， λc，dO）

1.1.3 實驗驗證

本節設計了2種不同的三維場景配置，分別采用相同大小的立方體和3種不同大小的立方體來表示無人機，來驗證基于GJK的沖突網絡構建算法的有效性與及時性。

如圖5所示，圖5（a）展示了20架相同大小的無人機，選取30 m立方體作為無人機表征，以1 km×1 km×0.6 km的空域大小作為實驗環境，無人機在空域內進行隨機勻速直線飛行，當碰到空域邊界或與其他無人機發生沖突時，會隨機改變飛行方向，每個立方體的速度方向隨機生成，無人機在此空域環境中運行30 s。當2個立方體接觸發生沖突時，立方體顏色由藍色變成紅色，當2個立方體分開后，恢復為藍色。圖5（b）展示了3種不同大小的無人機，選取邊長200、100、30 m立方體作為3種不同類型的無人機表征，實驗選取了3架中型無人機，3架小型無人機，14架微型無人機共20架無人機進行實驗。

圖5 2種不同場景下的沖突識別Fig.5 Conflict identification in two different scenarios

為了驗證無人機沖突網絡構建算法的有效性與識別效率，分別針對沖突識別準確率和沖突識別時間2個指標，與三維坐標系下通過成對計算無人機之間的歐氏距離來識別沖突的傳統方法進行比較。

在沖突識別準確率比較實驗中，無人機的數量從2架不斷增加到20架，不同數量無人機分別在三維環境中運行30 s，在該時段內實際發生的沖突數量為N0，算法識別到的沖突數量為N，假設不存在虛假沖突告警情況，定義沖突準確率為Ec=N/N0。在傳統基于Reich模型［24］的沖突識別算法中，將無人機安全保護區設置為球形保護區，間隔半徑設置為D=0.02 km，但由于無人機種類大小不盡相同，此安全間隔半徑設置為滿足盡可能多的無人機類型，取各種類型無人機平均安全間隔作為閾值，當無人機距離小于閾值時算法即判定為沖突。為了進一步驗證算法性能，對不同算法的準確率進行對比分析，以20架無人機為例，2個分別為相同種類和不同種類的無人機沖突識別場景，實驗結果如圖6所示。

圖6 沖突識別準確率對比Fig.6 Comparison of conflict identification accuracy

在相同粒度場景中，當無人機數量較少時，2種算法的準確率均能夠達到100%，隨著無人機數量增加，2種沖突識別算法準確率均稍有下降，并趨于穩定在96%以上的較高水平。在相同識別時間基準下，傳統算法的準確率與本文算法幾乎持平，但由圖6（b）可知，在相同識別時間基準，本文算法的準確率遠高于傳統算法，具有更高的沖突識別效率，在實際應用中具有更快的響應速度。在不同識別時間基準中，由于設定了3種不同大小的無人機，無人機性能不盡相同，其安全間隔距離也不固定，體積較大的無人機安全間隔的需求更大，在體積較大的無人機之間識別沖突時，傳統算法設定的安全閾值并不能滿足要求，無法有效識別到真實沖突的發生，本文算法由于不需要設定閾值，適用于多種無人機類型，沖突識別準確率穩定在95%以上，而傳統算法在不同種類的無人機沖突識別場景中的準確率顯著降低。在實際應用場景中，無人機的種類往往不止一種，是多種不同大小性能的無人機在空域中進行飛行，本文提出的基于GJK的沖突網絡構建算法可在多種不同類型的無人機運動場景中進行更為有效的探測。

圖7所示為不同粒度場景下不同算法的沖突識別時間對比情況。隨著無人機數量的增加，傳統算法的沖突識別時間呈近指數增長，本文提出的基于GJK的沖突網絡構建算法增長呈線性增長，增長趨勢較為緩慢，所提算法具有高效性。

圖7 沖突識別時間對比Fig.7 Comparison of conflict identification time

1.2 特征提取及分析

1.2.1 飛行沖突網絡特征提取

采用復雜網絡理論［25］，將無人機群體視作復雜網絡，其中無人機個體為網絡的“節點”，無人機之間存在的沖突為網絡的“邊”。運用基于GJK的沖突網絡構建算法，對復雜低空環境中的無人機沖突連邊進行動態識別，在此基礎上通過復雜網絡的相關概念分析低空空域運行態勢。本文基于復雜網絡理論提出以下3個指標，對空域無人機群體的沖突網絡特征進行分析。

1） 沖突數量

根據復雜網絡中“度”的概念，將Ki定義為與無人機節點i存在沖突關系的無人機數量，表示為

式中：eij為0-1變量，若無人機節點j與i直接相連，則取值為1，否則為0。

2） 沖突風險等級

為了使復雜網絡更接近于無人機飛行場景，通過無人機之間的相對距離和相對速度來表達無人機的真實關系，即2架無人機接近彼此的速度越快，越容易發生沖突，無人機沖突等級便越高。定義無人機i與無人機j之間的沖突風險為

式中：rij為無人機i和j的相對速度；xij為無人機i和j之間的相對距離。

將無人機i的沖突風險等級Ei定義為

3） 聚集系數

復雜網絡中聚集系數表示某個節點相鄰的2個節點彼此也相鄰的概率，在無人機沖突場景中表示某架無人機周圍的無人機密集程度，在無人機群一個沖突數量為Ki的無人機節點i的聚集系數Ci定義為

式中：Ni表示無人機節點i的Ki個存在沖突的無人機之間實際存在的沖突的邊數，即無人機i的Ki個相鄰無人機之間實際存在的鄰居對的數目。聚集系數反映了無人機i附近的擁擠程度即沖突發生的可能性。

1.2.2 飛行沖突網絡特征分析

設置低空空域環境中共有50架無人機，采用沖突網絡構建算法建立沖突節點連邊，對無人機運行狀態構成的復雜網絡進行網絡演化，網絡每30 s演化一次，共演化30 min，即網絡共演化R=60次，每次演化完成時根據網絡中節點的數量和無人機位置關系，獲得節點的連接關系構建復雜網絡模型。演化第0、5、10、30 min的網絡如圖8所示。

圖8 空域中無人機網絡演化過程Fig.8 Evolution of UAV networks in airspace

低空空域內的無人機群體每進行一次演化，提取沖突網絡中各無人機節點的位置和速度，計算每一時刻空域內所有無人機指標的平均值，進而度量飛行沖突網絡的各個特征指標，便可得到各指標的時間序列，如表1所示。通過仿真發現，網絡演化過程中每架無人機平均與2～4架無人機發生沖突，沖突風險等級集中分布在6～7范圍內，聚集系數集中分布在0.5～0.6范圍內，飛行沖突網絡特征演化過程如圖9所示。

表1 網絡演化特征指標Table 1 Characteristic indicators of network

圖9 飛行沖突網絡特征演化Fig.9 Evolution of flight conflict network characteristics

2 基于數字柵格的無人機飛行沖突精細探測

無人機運營者可根據任務目的和飛行計劃等信息進行無人機飛行路徑規劃，無人機則可按照預先設定的軌跡實施飛行活動。在實際運營過程中，因存在潛在的飛行計劃沖突，導致預先設定的飛行航跡可能無法執行，而無人機運行安全與效率水平亦隨著潛在沖突的增加而降低。因此，本節采用數字柵格方法，將無人機的物理航跡點信息映射到以柵格編碼為索引的數字柵格中，對無人機潛在沖突進行探測。

2.1 空域數字柵格剖分

空域柵格化是指基于柵格化思想，建立空域柵格單元剖分方法，構建基于柵格索引的空域系統，從而支撐空域系統表征、規劃、管理與評估研究的一種空域離散化處理方法。本節面向低空空域無人機運行管理需求，建立了離散柵格框架下的低空空域數字柵格剖分與編碼設計方法。

全球空域空間柵格編碼［26］以地球的南極點為基準點，構建了全球柵格系統參考位置，在空域空間柵格剖分的基礎上建立了柵格編碼規則。該方法采用基于經緯度整數規則的地球橢球面剖分方法，即以經緯度的“度-分-秒”整數形式進行橢球面的空間分區劃分，這種劃分實質是一種大地坐標系的度量參數離散化描述方法。

定義空域柵格的基本原則：首先，要統一基準，對尺度范圍內的空域建立統一的標準；其次，要做到可以相互轉換，兼容地理位置柵格碼以及全球定位系統（Global Position System， GPS）和北斗等既有標準，實現位置與編碼的相互轉換；最后，要做到高效實用，以地理經緯柵格為原型，劃設不同層級的空域，基于空域管理需求，在不同層級的柵格建立應用規范。根據上述原則進行低空空域離散建模，將連續空間離散為基本空域，用空域編碼取代經緯度標識空間位置，以低空空域編碼為索引，建立描述低空空域的數據結構，管理低空空域內活動。

由于無人機多數在中低空空域內運行，機動性較高，因此柵格編碼模型采用地球球面和高度分開處理的方法，平面編碼和高度編碼均采取“Z”形編碼，將柵格左下角位置點定義為柵格坐標原點，分別在地理經緯度空間和高度空間內定義柵格。基于地理空間經緯度，進行球面柵格劃分，共劃分8個層級的遞歸柵格。針對不同的層級柵格，建立柵格劃分矩陣，n為柵格劃分層級，取值1～8，設定柵格所在劃分矩陣的行數和列數為(pn，qn)，劃分矩陣可表示為

在地球墨卡托投影坐標系統上，首先以經緯度15°為剖分粒度，將地球的橢圓面進行完整劃分，具體情況如圖10所示。

圖10 柵格剖分方法Fig.10 Grid splitting method

采用字母進行柵格單元編碼，由于數字0和1容易與字母O和I混淆，因此不采用O和I進行編碼。在15°大小的第1級柵格單元基礎上，按照1°剖分間隔進行剖分，形成1°大小的第2級柵格單元，對1°大小柵格單元采用二分法進行剖分，形成經緯度30′大小的第3級柵格單元。在經緯度30′大小柵格單元基礎上，進行第4級和第5級柵格單元的剖分，第4級柵格采用鍵區標識剖分至10′大小單元，第5級柵格采用象限標識剖分至1′大小單元。在經緯度1′大小柵格單元基礎上，再進行第6級、第7級、第8級柵格單元的剖分。根據低空無人機運行特點，將低空空域剖分至柵格大小為6″、3″和1″。具體劃分層級如表2所示。

表2 低空空域柵格劃分層級Table 2 Airspace grid classification hierarchy

以第8級柵格編碼生成5 km×5 km×0.2 km大小的低空空域柵格環境，實驗結果如圖11所示。

圖11 空域柵格化及路徑柵格表征Fig.11 Airspace gridding and path raster representation

2.2 空域數字柵格編碼

水平位置編碼依托經緯度，采用2.1節提出的剖分方法進行編碼。對于高度編碼，基于單個柵格進行編碼，本文以30 m為粒度向上拓展，生成符合空域最高高度的柵格大小。整體八級編碼呈現形式為“ab-cd-e-f-gh-ij-k-l”。其中，前2位代表第1級編碼，第3位和第4位代表第2級編碼，第5位代表第3級編碼，第6位代表第4級編碼，第7位和第8位代表第5級編碼，第9位和第10位代表第6級編碼，第11位和第12位分別代表第7級和第8級編碼。采用二進制方法，對高度進行單獨編碼。“度”級體塊編碼用d表示；“分”級體塊編碼用m表示；“秒”級體塊編碼用s表示，編碼組成單元層級可以表示為“dd-mmmsss”。

地理位置的經緯度坐標信息(Lng，Lat)通過式（21）～式（22）進行編碼轉換：

式中：經度編碼和緯度編碼分別用CodeLng和CodeLat表示；n表示編碼層級；gridsizen表示第n層級柵格粒度大小；Lngd、Lngm和Lngs分別表示經度坐標中的度、分和秒；Latd、Latm和Lats分別表示緯度坐標中的度、分和秒。

針對不同的應用場景，本文所構建的柵格編碼可以與柵格劃分矩陣進行相互轉換。

1） 由柵格編碼轉化為劃分矩陣。

首先根據柵格編碼確定柵格劃分層級n，根據柵格編碼計算出柵格坐標原點的經緯度坐標(Lngn，Latn)，確定在該層級下柵格劃分的經緯度粒度間隔ΔLng和ΔLat，根據式（23）和式（24）進行轉換，得到目標柵格所在的劃分矩陣位置。

式中：pn和qn表示第n層級下柵格所在劃分矩陣的行數和列數，與式（20）中的內涵一致。

2） 由劃分矩陣轉化為柵格編碼。

首先根據柵格編碼確定柵格劃分層級n，確定在該層級下柵格劃分的經緯度粒度間隔ΔLng和ΔLat，根據式（25）和式（26）計算得到柵格原點的經緯度坐標。

然后，根據經緯度坐標，利用式（21）和式（22）計算得到柵格編碼。

空域柵格化為低空無人機空中交通管理提供了一種新的位置參考基準，通過數學模型在計算機信息空間內完成了對物理空間的數字化重構，距離運算可以轉化為編碼或者劃分矩陣之間的運算，可以更加快速和準確地判斷無人機之間的空間位置關系。

2.3 基于數字柵格的沖突探測模型

在空域柵格編碼的基礎上增加時間維度，構造數字柵格單元，時間編碼采用數字編碼，以0為開始時間，運行的最長時間為最大時間上限，按照圖10的柵格剖分方法，整體八級編碼呈現如圖12所示。

圖12 低空空域數字柵格編碼格式Fig.12 Digital grid coding format in low altitude airspace

通過特定的空間區域和時間范圍的時空編碼來表示無人機的時空信息，每個空間內的物體均可用一個或多個柵格表示，建立一定空域內的多級時空索引。根據劃設的實驗空域對數據表主鍵進行初始化，進行排序后的時空柵格編碼與具有特定時空屬性的柵格密切相關，因此將其設置為數據表中的主鍵。

當一個空間柵格中存在一架無人機時，對應代碼記錄為1；否則設置為0。時間信息將記錄在數據庫表中的每一行，并具有開始時間戳和結束時間戳，以此表示某無人機在特定時間段在該空間柵格內。因此，通過數字柵格索引，可以將沖突探測的復雜成對計算問題簡化為空間數據庫查詢問題。

為了滿足多級查詢的需要，建立圖13所示的多表查詢策略，通過多個數據庫表管理記錄特定空域內的無人機信息。每個數據庫表中只存儲某一級別編碼對應的數據，并且父代編碼具有指向子代編碼所在數據庫表的指針，以此保證當查詢完本級編碼后，如需要進一步詳細查詢，可以直接鏈接到下一級編碼所在的數據庫表。其中每行數據庫表記錄了所研究空域中的一個柵格單元，且數據庫表中的行數與空域中柵格單元的總數相同。

圖13 低空空域網絡多級數據庫表查詢策略Fig.13 Multi-level database table search strategy of low-altitude networks

基于數字柵格結構建立多層級查詢，可使沖突檢測不再拘束于同一層級的判斷，當2架無人機在同一柵格內即可判斷為存在沖突；除此之外，在沖突檢測過程中，每一級編碼均具有各自的子代編碼與父代編碼，很好解決了不同大小柵格的沖突檢測問題，同時無人機軌跡數據作為新增數據進行柵格編碼后插入至數據庫表中，以此減少冗余計算。當用較大粒度柵格表示的中型無人機與用較小粒度柵格表示的微型無人機發生沖突時，由于兩者所在柵格層級不同，故兩者編碼也不會相同，此時通過父代與子代編碼的關系進行判斷，根據兩者是否是包含關系判斷兩架無人機是否發生沖突。

2.4 算法流程

假設無人機在某段時間[t1，t′1]內通過一系列編碼柵格表征飛行路徑，N為最低層級，其中每個柵格對應一個空間編碼Code，則每個柵格的時空信息可以表示為{Code，[t1，t′1]}，無人機的飛行路徑可以記錄為一系列柵格集合。對于每個柵格，在同一級別上可以記錄多個空間柵格編碼，并且在同一柵格上可以記錄多個對應的時間間隔，編碼層級變量i開始從1到N-1進行遍歷，對于每個層級i均需獲得編碼Code的父代編碼F(Code)i。對于具有時間屬性的所有i級空間柵格編碼，若對應的數據庫表為空，則不存在沖突；否則應根據父代與子代編碼進行沖突判斷，當層級為n時，可根據該層級的編碼直接進行比較，來判斷柵格的位置關系，編碼相同則判定為沖突。每架無人機的飛行軌跡柵格可賦值為

式中：UAVA表示無人機編號；[t1，t′1]表示無人機占用該柵格的時間。

根據空域柵格的時空屬性，若在同一空間柵格中有兩個或以上的賦值，則表明有多個無人機飛行計劃會占用此柵格區域，需要判定其時間上是否存在沖突，若時間上存在沖突，則可以判定在該柵格處存在飛行沖突，需重新調整飛行計劃。若無人機大小不同，則首先要判斷其空間編碼是否存父子代關系，再判斷時間上是否會發生沖突。算法步驟如下：

步驟1假定空域內存在n架無人機，每一架無人機的飛行計劃軌跡被離散為M個時間片，因此空域內無人機飛行軌跡可表示為n×M元素的矩陣A，同時構建輔助矩陣B。

步驟2將無人機飛行空域離散為柵格。

步驟3通過式（21）和式（22）將每架無人機的飛行軌跡點由經緯度轉換為柵格編碼集合。

步驟4將每一架無人機飛行計劃中預測軌跡點對應的柵格單元存入矩陣A，并在輔助矩陣B中存入無人機編號信息。

步驟5掃描檢索矩陣A中的各個元素，若發現存在相同編碼或存在父子代關系的編碼，則判定在該柵格處發生沖突。

步驟6讀取存在沖突的柵格信息，通過索引從矩陣B中確定存在沖突的無人機編號信息，對相關無人機進行飛行計劃調整。

2.5 仿真驗證

為探究數字柵格方法的沖突檢測效率，本節設計實驗對傳統三維坐標檢測方法與數字柵格數據檢索方法下的無人機飛行沖突探測總時間進行了對比。將沖突探測總時間定義為探測到空域環境中第一次發生沖突至最后一次發生沖突之間的時間間隔。基于三維坐標的沖突檢測方法通過成對計算任意2架無人機之間的歐幾里德距離，并將計算得到的距離與設定的閾值進行比較來檢測沖突。本節針對100～1 000架逐漸遞增的無人機實驗樣本，其四維航跡點根據飛行計劃仿真生成。將傳統方法下的無人機安全保護區設置為球形保護區，間隔半徑設置為D=0.02 km，時間步長設置為Δt=0.1 s。上述2種方法下的無人機沖突探測時間對比情況如圖14所示。

圖14 不同方法下的無人機沖突探測效率對比Fig.14 Conflict detection efficiency of different methods

可以看出，隨著無人機數量的不斷增加，初始航跡存在的潛在沖突數量亦隨之增加，并且2種方法對應的沖突探測總時間均呈現增長趨勢。當無人機數量＜200架時，2種方法沖突探測效率相當；隨著無人機數量的繼續增加，傳統成對計算方法的沖突探測時間增長趨勢更加明顯，而基于數字柵格檢索方法的沖突探測時間增長則較為平緩，基本穩定在2 s左右，本文方法相比傳統方法，可將探測總時間減少78.4%。顯然，基于數字柵格的方法明顯優于傳統的成對計算方法，具有較高的無人機沖突探測效率與穩定性。

為進一步探究基于數字柵格的沖突探測算法效率，現針對300、500、1 000架的無人機飛行場景進行算法對比，為減少仿真隨機性對結果的影響，實驗采取3種固定場景，對預生成的固定航路進行沖突探測。圖15所示為本文提出的基于數字柵格的算法與速度障礙法、傳統基于Reich模型的成對比較算法在沖突探測效率方面的對比情況。

圖15 固定場景下的不同算法沖突探測效率對比Fig.15 Conflict detection efficiency of different algorithms in fixed scenarios

由圖15可知，在無人機數量相對較少的場景中，3種算法的沖突探測效率差異不大，本文提出的基于數字柵格的算法時間略快。隨著無人機數量的不斷增加，本文所提算法的沖突探測時間明顯小于其他2種算法，速度障礙法雖略好于傳統成對比較的方法，但其探測時間仍然較長。因此，本文提出的基于數字柵格的沖突探測算法效率較高，相比其他算法具有明顯的優勢。

3 基于網絡演化的無人機飛行沖突最優解脫

在基于數字柵格的無人機飛行沖突探測的基礎上，本節以無人機沖突數量最少和運行成本最低為優化目標，構建了考慮優先級的無人機沖突解脫多目標混合整數優化模型，對無人機飛行沖突解脫策略進行了最優求解。

3.1 模型構建

3.1.1 模型假設

1） 將無人機簡化為質點，忽略運動姿態和機動性能對沖突管理的影響。

2） 不考慮無人機的懸停操作。

3） 在未探測到沖突風險和未接收到飛行調整指令之前，無人機始終沿直線飛行。

3.1.2 決策變量

采用3種機動方式對存在潛在沖突的無人機航跡進行調整，分別是航向調整、高度調整和速度調整，因此引入3個決策變量ωi、hi和υi分別表示對無人機i采取的航跡調整方式，將決策變量整合到一個決策向量κi=[w h υ]，κi表示對無人機i航跡進行的調整。

1） 設定存在N條柵格離散無人機軌跡，允許設置的虛擬航路點數量即為時間片數量M，無人機i的初始航段的柵格數量為Li，0，虛擬航路點位置的柵格編碼為，對于空域內所有無人機航跡虛擬點構成的柵格編碼集合為w=(ω1，ω2，…，ωN)。圖16為M=2時設置虛擬航路點生成的航跡。

圖16 M=2時設置虛擬航路點生成的航跡Fig.16 Trajectory generated by virtual waypoints at M=2

2） 在柵格化空域下，設定無人機i的初始飛行高度層為Hi，0，hi表示無人機進行高度調整時高度改變的柵格數量，改變高度后飛行高度層變為Hi′=Hi，0+hi，所 有 無 人 機 高 度 調 整 柵 格 改 變數量構成集合h=(h1，h2，…，hN)。

3） 設定無人機i的初始飛行速度為Vi，0，vi表示無人機進行速度調整時的速度改變量，改變速度解決沖突后飛行速度變為V′i=Vi，0+vi，空域內所有無人機速度調整量構成集合v=(v1，v2，…，vN)。

3.1.3 目標函數

1） 沖突數量

根據前述構建的基于數字柵格的沖突探測方法，通過離散化低空空域和四維坐標將每架無人機i的航跡點集合Pi映射到相應的編碼柵格結構中，該方法只需判斷無人機航跡采樣點Pi，g對應的數字柵格是否存在其他無人機的航跡采樣點。若存在，則判定無人機i在航跡采樣點Pi，g處存在一次沖突。空域內所有航跡之間的沖突數量可表示為

式中：Φi，g表示無人機i在g點發生沖突。

2） 運行成本

從低空空域運行角度考慮，無人機按照計劃航跡點集合進行飛行的成本應盡可能小，輸入的無人機航跡點集合是針對單體最優的航跡，若探測到無人機之間的沖突，則無人機會采取機動策略導致飛行前計劃航跡改變，使無人機的飛行距離增加，或當采取速度調整策略時雖不會增加額外的飛行距離，但無人機的飛行時間相較于飛行前的計劃航跡會有所增加。因此，從飛行時間、經濟成本等方面考慮，優化目標為無人機實際飛行解脫的航跡相較于原飛行前無人機航跡的航跡成本增加最少，航跡成本包括解脫航跡與飛行前計劃航跡之間的偏差、解脫后航跡的到達起飛時間的改變量2個部分。空域中所有無人機的總成本（標準化后的無量綱數值）為

式中：R(κi)和T(κi)分別表示無人機i航跡和時間偏移成本。

本文考慮沖突解脫優先級，設置權重系數η∈(0，1]，將所有無人機根據優先級排序設置不同權重大小，對于解脫優先級高的無人機，設置較低權重盡可能減少其飛行成本，進行優先解脫；對于優先級較低的無人機，盡可能減少其航跡改變，設置較大權重系數，權重差設置為1/N，故優先級從高到低成本系數為η=1/N，2/N，…，N/N=1。本文基于優先級對所有無人機飛行成本進行加權求和，得到考慮優先級的空域中所有無人機總成本為

航跡偏移量主要考慮由于解脫策略造成的航跡改變，使解脫后的航跡與飛行前的計劃航跡產生偏差，定義為每架無人機的航跡點集合從第一個至最后一個航跡點所有沖突解脫結束后，實際的沖突解脫航跡和原飛行前的無人機計劃航跡之間的柵格數量之差。每架無人機的航跡偏移成本可表示為

式 中：i=1，2，…，N表 示 無 人 機 的 數 量；j=1，2，…，Mk表示無人機i航跡集合中第j個航跡點；Mk為無人機i航跡集合中虛擬航跡點數量；di，j表示無人機i在第j個航跡點時，實際沖突解脫航跡點與原飛行前無人機計劃航跡采樣點的柵格數量差。

時間偏移成本主要考慮由于解脫航跡造成的總的運行時間的偏移量，使解脫后的航跡運行時間與飛行前的計劃航跡的運行時間之間產生的偏差，定義為無人機i的解脫航跡運行時間和原飛行前無人機計劃航跡運行之間的偏差量，可表示為

式中：i=1，…，N表示無人機的數量；Δti表示無人機i的解脫航跡運行時間和原飛行前無人機計劃航跡運行之間的偏差值。

3.1.4 約束條件

1） 允許的最大水平路徑長度

每架無人機i的初始航段長度（占用柵格數量）Li，0，設?i為無人機i的最大允許航線長度擴展系數，0≤?i≤1，為了限制航線長度的延長，無人機i的備選航線水平剖面必須滿足：

式中：Li(ωi)是由ωi確定的替代航跡的長度（占用柵格數量），因此該約束可通過限制航路點位置來滿足。

2） 允許的水平航路點位置

為了限制搜索空間，防止大角度轉彎，控制路徑長度的延長，因此對每個虛擬航路點的可能位置進行了限定。對于每個軌跡i和第m個虛擬航路點，無人機在x和y方向上的偏移分量Wmi，x和Wmi，y表示為

式中：0≤α≤1，0≤β≤1為用戶自定義參數；表示向下取整運算。

為了獲得規則的航跡，相鄰2個航跡點的x方向分量不能重疊，即

由 式（36）可 得 出，選 取 的βi應 滿 足βi＜1/[2(M+1])。因此為了限制無人機的最大拓展航路，應滿足：

3） 允許的高度層改變

由于偏離偏好航跡的飛行高度可能會導致額外的運行成本，同時考慮無人機自身性能約束，因此需要限制無人機i的高度改變量。引入低空空域高度層的概念，將高度離散處理，無人機i所有可行的高度層改變量集合ΔHi表示為

式中：hi，max為無人機i允許最大高度層改變量。

4） 允許的速度改變

由于受自身性能約束和飛行環境影響，無人機存在最大和最小飛行速度限制，無人機i受自身性能約束的速度限制表示為

綜上所述，本文考慮的動態沖突解脫問題可以表示為以下的多目標混合整數優化問題：

3.2 算法設計

無人機沖突解脫問題的復雜度隨決策變量數量的增加以幾何級數增長，決策變量之間存在強耦合關系，且本文提出的沖突解脫模型是非線性不可微分的復雜模型，難以在短時間內得到目標解，因此本文采用元啟發式算法進行求解。無人機沖突解脫是一個多目標優化問題，鑒于非支配排序遺傳算 法（Non-Dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）在非支配排序、擁擠距離排序、運行速度及解集收斂性等方面的諸多優點，采用NSGA-Ⅱ算法對所建優化模型進行求解。

1） 編碼設計

染色體編碼對算法求解效率至關重要，本文采用整數編碼方式對染色體進行編碼，每條染色體代表所有無人機航跡方案；染色體長度表示所有無人機的總架數，染色體內每個基因位置表示無人機各航跡點所做的航向、高度和速度調整。染色體基因編碼實例如圖17所示。

圖17 染色體基因編碼示意圖Fig.17 Diagram of chromosomal gene coding

2） 快速非支配排序

快速非支配排序是依據種群個體的帕累托支配關系對種群分層，為了引導搜索向帕累托最優解集方向進行。快速非支配排序的思想是給每個個體p都賦予3個參數：Sp、np和rankp，其中，Sp為種群中被個體p支配的個體集合；np為種群中支配個體p的數量；rankp為個體p的帕累托層級。快速非支配排序的操作過程如下所示。

步驟1遍歷種群計算每個個體的參數S和n。

步驟2初始化非支配序，即帕累托層級，令rank=1。

步驟3根據帕累托支配關系，找到種群中所有不被其他個體支配的個體，組成非支配解集并將其所有個體帕累托層級賦值為rank，并從整個種群中剔除。

步驟4判斷種群個體數量，若數量為零，則非支配排序結束；否則，rank=rank+1，返回步驟3。

3） 擁擠距離

為了保證種群的多樣性，通過優先選擇擁擠距離較大的個體，可使計算結果較均勻分布，避免個體都集中于某一處導致無法得到帕累托最優解集。計算個體i擁擠距離disi步驟為：

步驟1為帕累托層級中的每個個體增加擁擠度屬性，初始化disi=0。

步驟2遍歷每個rank中的個體i，將處于邊緣位置的個體的擁擠距離賦值為+∞，處于中間位置的個體擁擠距離計算公式為

3.3 優先解脫流程

在沖突解脫過程中，引入優先級概念，優先級高的無人機優先采取機動策略避讓優先級低的無人機，通過復雜網絡的相關概念確定空域中運行無人機的沖突解脫優先級。基于1.2節提出的飛行沖突網絡特征，以式（42）～式（44）定義無人機在解脫順序時的優先級原則，得到無人機解脫順序。

原則1無人機平均沖突數量，計算公式為

原則2無人機平均沖突風險等級，計算公式為

原則3無人機平均聚集系數。計算公式為

在本文全局沖突解脫場景中，優先級高的無人機優先計算解脫方案，優先級低的無人機將已解脫的無人機視為移動障礙物限制，保證已解脫的無人機不會與優先級低的無人機發生沖突。定義障礙物集合Ω，障礙物優先級SΩ=0；無人機i的優先級Si=1，2，…，Smax；S越小表明無人機優先級越高。沖突解脫流程具體如下所示

步驟1獲取無人機信息，提取空域內所有無人機的水平位置、高度、速度以及航向，根據2.3節中的方法進行沖突探測，得到所有存在潛在沖突的航跡集合G。

步驟2令S=1，生成障礙物集合Ω。

步驟3計算優先級最高的無人機對應的沖突解脫策略。

步驟4S=S+1，若S＞Smax，則已遍歷所有優先級，沖突解脫算法結束。

步驟5將Si＜S的所有無人機視作障礙物，加入障礙物集合Ω，求解當前優先級無人機對應的沖突解脫策略，返回步驟4。

3.4 仿真驗證

3.4.1 實驗設計

基于Python 3.8環境，對多無人機沖突解脫過程進行仿真分析，根據前述實驗場景，基于數字柵格的沖突探測模型，對空域中50架無人機進行沖突探測，結果表明初始航跡存在的沖突數量為93，空域內所有無人機的運行成本為5 916。根據上述算法對其中存在沖突的無人機航跡進行沖突解脫，以驗證本節提出的沖突解脫算法的有效性。本小節采用NSGA-Ⅱ算法對模型進行求解，隨機產生規模為200的初始種群，進行進化迭代求解。根據常見的無人機型號，以大疆經緯M100性能參數作為參考，多無人機沖突解脫模型參數設置如表3所示。

表3 無人機沖突解脫模型參數設置Table 3 Parameter of UAVs conflict resolution model

NSGA-Ⅱ算法參數設置如下：設定種群大小為200，最大進化代數200代，交叉概率0.9，變異概率0.05。在上述基準參數下，進行仿真實驗，所有實驗結果皆基于10次獨立運行。

根據飛行狀態網絡連邊的建立規則，采取數字柵格的沖突探測算法，根據設定的50架無人機初始飛行計劃，當2架無人機之間存在潛在飛行沖突時，則認定無人機之間存在聯系，并建立連邊，基于復雜網絡的無人機初始沖突分布如圖18所示。

圖18 無人機運行狀態網絡Fig.18 Network of UAVs operation

3.4.2 結果分析

設置50架無人機，初始航跡存在的沖突數量為93個。在3種不同優先級排序下，經過10次獨立運行，算法分別得到26、23、20個非支配解，如圖19所示。對于本節提出的多目標沖突解脫問題，算法得到的總運行成本和總沖突數量最小的非支配解對應的優化性能均高于初始解，由此可知NSGA-Ⅱ算法能夠有效解決本仿真案例中的初始航跡潛在飛行沖突并降低無人機運行成本。

圖19 不同優先級原則所得到的非支配解Fig.19 Non-dominated solutions resulting from different priority principles

為了驗證不同優先級原則在解決航跡沖突時的效率，對比了3種不同原則下沖突數量和運行成本的收斂情況，如圖20所示。結果表明，采取原則2和原則3均可有效解脫沖突且原則2收斂更快，原則1則不能完全實現的無沖突解脫。另外，基于原則2的解脫策略可以更好地降低運行成本。綜上，原則2在沖突管理算法求解效率方面優于原則1和原則3，能夠更好地實現多無人機全局無沖突解脫和低成本運行。

圖20 不同優先級原則下沖突數量和運行成本算法收斂變化Fig.20 Conflict number and operation cost algorithm convergence changes with different priority principles

表4所示為NSGA-Ⅱ算法的優化結果。比較分析3種不同的優先解脫原則在相同初始條件下解的質量，原則2和原則3在設定的實驗環境中可以獲得全局無沖突解，同時基于原則2進行算法設計可以更好地降低全局無人機運行成本。在算法求解時間方面，三者比較相近，但由于原則1基于每架無人機的沖突數量進行優先級排序，對初始解的質量要求較高，算法收斂較慢，因此花費的時間最長，原則2和原則3時間相近，但原則2進行優先級排序時計算復雜度較低，因此算法求解時間略快于原則3。

對考慮優先級和不考慮優先級的沖突解脫仿真結果進行對比分析，設定沖突風險等級為優先級排序原則，選取沖突數量最小的非支配解與不考慮優先級的沖突解脫策略，對高度改變、水平航跡偏移量和速度改變進行成本比較分析，結果如圖21所示。圖中考慮優先級是指采用平均沖突風險等級定義的無人機解脫優先級，不考慮優先級是指不設置無人機解脫順序對空域內無人機進行機動調整。

圖21 考慮優先級與直接解脫成本對比Fig.21 Cost comparison of priority and direct resolution

根據圖21可知，以沖突風險等級為優先級排序原則進行高度層調整相比不考慮優先級可以少調整21個高度層，平均每架無人機高度層調整值減少了32.8%；水平航跡調整相比不考慮優先級少調整991個柵格，平均每架無人機水平調整值減少了21.4%；速度調整相比不考慮優先級少調整51.3 m/s，平均每架無人機水平調整值減少了14.6%。通過對比分析可知，本文提出的考慮優先級的沖突解脫方法使得無人機的機動解脫成本更低，結合高度調整、速度調整和航向調整3種不同的解脫方法，可以更好地利用低空空域資源，降低無人機運行成本，提高沖突管理效率。

4 結 論

本文針對多元化空域、高密度流量和高動態演化交織形成的復雜低空系統，構建了基于沖突連邊動態識別的無人機飛行沖突網絡模型及特征度量方法，提出了基于數字柵格的無人機飛行沖突精細探測算法，建立了考慮優先級的無人機飛行沖突最優解脫方法，實現了低空空域內無人機飛行沖突的精細化管理。主要結論如下：

1） 提出的基于GJK算法和復雜網絡理論的無人機飛行沖突網絡動態構建方法，可實現對任意低空空域系統內無人機群體飛行沖突的動態識別，以及沖突網絡特征的多維提取。

2） 與傳統的基于三維坐標的沖突探測方法相比，基于數字柵格的沖突探測和基于GJK的沖突探測算法具有更高的沖突探測效率，可顯著降低沖突探測的時間成本。

3） 所提方法尤其適用于低空空域多機型混雜運行場景，可將無人機沖突探測效率由“指數增長級”降至“線性增長級”。

4） 綜合考慮無人機的沖突數量與飛行狀態，將平均沖突風險等級作為解脫優先級原則，可以得到最優的沖突解脫策略非支配解，從而更好減少低空空域全局范圍的無人機沖突數量，有效降低沖突解脫成本。