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

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

2.南京航空航天大學(xué) 民航學(xué)院，南京 210016

隨著國(guó)家低空空域管理改革的不斷推進(jìn)，民用無(wú)人機(jī)飛行需求呈現(xiàn)迅猛增長(zhǎng)趨勢(shì)，作為低空空域系統(tǒng)內(nèi)的新興用戶，無(wú)人機(jī)目前已在商業(yè)、公共、軍事、旅游、體育和防疫等領(lǐng)域得到廣泛應(yīng)用［1］。例如，在新冠肺炎疫情期間，無(wú)人機(jī)常被用于執(zhí)行疫苗運(yùn)輸、物資配送、安全巡邏等各類任務(wù)［2］。2021年，中共中央、國(guó)務(wù)院在《國(guó)家綜合立體交通網(wǎng)規(guī)劃綱要》中首次提出要大力發(fā)展以低空空域?yàn)橐劳小⒁詿o(wú)人機(jī)和通航產(chǎn)業(yè)為主導(dǎo)的“低空經(jīng)濟(jì)”，這為無(wú)人機(jī)在智慧城市中的規(guī)?；瘧?yīng)用帶來(lái)了前所未有的發(fā)展機(jī)遇。

未來(lái)，無(wú)人機(jī)將在管制空域和監(jiān)視、報(bào)告等非管制空域獲得更大的自由活動(dòng)權(quán)，而其高靈活和高機(jī)動(dòng)特性［3］將隨之帶來(lái)一系列安全問(wèn)題，并成為國(guó)內(nèi)外航空界的關(guān)注焦點(diǎn)。尤其是在無(wú)人機(jī)逐步融入整個(gè)國(guó)家空域系統(tǒng)的趨勢(shì)下，其運(yùn)行安全水平還將影響公共運(yùn)輸航空、軍事航空等傳統(tǒng)空域用戶。因此，研究復(fù)雜低空無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)建模與精細(xì)管理問(wèn)題，成為當(dāng)前及未來(lái)相當(dāng)長(zhǎng)一段時(shí)期內(nèi)國(guó)際空管領(lǐng)域的研究熱點(diǎn)和難點(diǎn)。

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

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

然而，當(dāng)前研究仍存在以下不足：① 無(wú)人機(jī)沖突分析主要聚焦特定場(chǎng)景中的無(wú)人機(jī)個(gè)體沖突特征，未充分考慮全局層面無(wú)人機(jī)群體沖突網(wǎng)絡(luò)的動(dòng)態(tài)構(gòu)建及其演化特性；② 無(wú)人機(jī)沖突探測(cè)主要基于預(yù)先設(shè)定的粗放式低空空域單元，未對(duì)無(wú)人機(jī)空間運(yùn)行環(huán)境進(jìn)行多層級(jí)分解建模，不能有效滿足無(wú)人機(jī)飛行沖突的精細(xì)探測(cè)需求；③ 無(wú)人機(jī)沖突解脫主要聚焦統(tǒng)一規(guī)則下的兩機(jī)或多機(jī)沖突場(chǎng)景，未充分考慮無(wú)人機(jī)個(gè)體調(diào)配優(yōu)先級(jí)的差異對(duì)無(wú)人機(jī)群體層面的間接性波及影響。

本文針對(duì)多元化空域、高密度流量和高動(dòng)態(tài)演化交織形成的復(fù)雜低空系統(tǒng)，通過(guò)構(gòu)建基于沖突連邊動(dòng)態(tài)識(shí)別的無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)模型及特征參數(shù)，提出基于數(shù)字柵格的無(wú)人機(jī)飛行沖突精細(xì)探測(cè)算法，建立考慮優(yōu)先級(jí)的無(wú)人機(jī)飛行沖突最優(yōu)解脫方法，旨在實(shí)現(xiàn)低空無(wú)人機(jī)飛行沖突的精細(xì)化管理，為低空空域安全管理與無(wú)人機(jī)運(yùn)行風(fēng)險(xiǎn)防控提供理論支撐和方法指導(dǎo)。

1 無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)建模及特征分析

本節(jié)采用GJK算法，構(gòu)建了基于沖突連邊動(dòng)態(tài)識(shí)別的無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)模型，以平均沖突數(shù)量、平均運(yùn)行風(fēng)險(xiǎn)和平均聚集系數(shù)等指標(biāo)表征無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)特征，分析了無(wú)人機(jī)飛行沖突的動(dòng)態(tài)演化特征。

1.1 模型構(gòu)建

1.1.1 GJK算法框架及流程

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

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

在此基礎(chǔ)上，進(jìn)一步引入2個(gè)相關(guān)概念。

1） 閔可夫斯基差集

閔可夫斯基差集是立方體A的所有點(diǎn)和立方體B的所有點(diǎn)的差值構(gòu)成的點(diǎn)集合，可表示為

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

則2個(gè)立方體之間的碰撞檢測(cè)可使用閔可夫斯基差判斷：當(dāng)且僅當(dāng)2個(gè)立方體的閔可夫斯基差集Mk(A，B)包含原點(diǎn)時(shí)，無(wú)人機(jī)A和B發(fā)生碰撞。

通過(guò)上述變化，可將立方體A和B之間的距離轉(zhuǎn)化為兩者的閔可夫斯基差與原點(diǎn)的距離，如圖1所示，通過(guò)判斷差集是否包含原點(diǎn)來(lái)確定2個(gè)無(wú)人機(jī)是否發(fā)生碰撞。

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

將3個(gè)相同類型的無(wú)人機(jī)A、B、C表示為3個(gè)相同大小的立方體A、B和C，如圖2所示，A和B接觸，C和A、B遠(yuǎn)離，將算法迭代次數(shù)設(shè)置A、B和C為5 000次，因此得到的閔可夫斯基差集中包含5 000個(gè)點(diǎn)，將這些元素點(diǎn)置于坐標(biāo)中顯示，A與B、A與C的閔可夫斯基差結(jié)果如圖3所示。

圖2 無(wú)人機(jī)的立方體表達(dá)Fig.2 Cube representation of UAVs

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

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

2） 支撐函數(shù)

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

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

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

由于閔可夫斯基差每次都得到相同的點(diǎn)，會(huì)大大增加算法復(fù)雜度。因此，構(gòu)造支撐函數(shù)的目的在于：通過(guò)支撐函數(shù)傳遞一個(gè)方向參數(shù)，方向不同，得到的點(diǎn)也不同，避免無(wú)效計(jì)算，同時(shí)使得算法迭代產(chǎn)生的單純形盡可能包含更大的空間區(qū)域，加快算法迭代進(jìn)程。

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

即找到CSO上距離原點(diǎn)最近的點(diǎn)，當(dāng)該點(diǎn)與原點(diǎn)的距離為所求最小距離d時(shí)，算法結(jié)束。

GJK算法迭代過(guò)程如下：

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

步驟1初始化單純形τk為CSO中的一個(gè)或多個(gè)頂點(diǎn)。

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

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

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

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

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

步驟7 將支撐點(diǎn)Pk加入單純形τk中，轉(zhuǎn)入步驟2，進(jìn)行迭代。

1.1.2 無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)模型

前文敘述了GJK算法應(yīng)用于2個(gè)立方體的碰撞檢測(cè)，由于低空空域內(nèi)無(wú)人機(jī)以連續(xù)狀態(tài)運(yùn)行，以GJK算法為基礎(chǔ)，將算法推廣到判斷一段連續(xù)時(shí)間內(nèi)兩架無(wú)人機(jī)是否會(huì)發(fā)生沖突，提出無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)模型動(dòng)態(tài)構(gòu)建算法，應(yīng)用于多無(wú)人機(jī)運(yùn)動(dòng)場(chǎng)景［22］。

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

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

以無(wú)人機(jī)A作為主動(dòng)沖突識(shí)別對(duì)象，設(shè)SM為立方體A和立方體B的CSO，在時(shí)段[t0，t0+Δt]內(nèi)，由式（8）和式（9）可得SM的頂點(diǎn)位置為

在一段時(shí)間內(nèi)SM移動(dòng)構(gòu)成了近似矩形的區(qū)域，如圖4所示，其運(yùn)動(dòng)軌跡為

圖4 [t0，t0+Δt]時(shí)間段CSO運(yùn)動(dòng)軌跡Fig.4 Trajectory of CSO at time [t0，t0+Δt]

每一個(gè)頂點(diǎn)ViMj(t)從t0到t0+Δt形成一條軌跡，在SM移動(dòng)過(guò)程掃描過(guò)的區(qū)域所有頂點(diǎn)的移動(dòng)軌跡都是等長(zhǎng)的，長(zhǎng)度為‖ traM(1)‖。

利用GJK算法進(jìn)行沖突網(wǎng)絡(luò)構(gòu)建的方法是判定一段時(shí)間內(nèi)CSO距離原點(diǎn)的最小距離，CSO的運(yùn)動(dòng)具有時(shí)空連續(xù)性，因此只需判定原點(diǎn)到CSO頂點(diǎn)軌跡的最小距離。若2架無(wú)人機(jī)未發(fā)生沖突，則原點(diǎn)在CSO外部，且與CSO最小距離為邊界軌跡到原點(diǎn)的距離；若發(fā)生沖突，則原點(diǎn)在CSO內(nèi)部，且在某2個(gè)頂點(diǎn)的運(yùn)動(dòng)軌跡之間。因此計(jì)算原點(diǎn)與CSO的距離可轉(zhuǎn)化為原點(diǎn)與CSO邊界軌跡的距離dO：

原點(diǎn)O與CSO邊界軌跡的距離是通過(guò)找到合適的^來(lái)確定，根據(jù)文獻(xiàn)［23］，通過(guò)割線法進(jìn)行實(shí)驗(yàn)=0.5左右時(shí)距離較小，最小距離為

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

算法1 基于GJK的沖突網(wǎng)絡(luò)構(gòu)建算法輸入：t0，SA(t0)，SB(t0)，Δt，traM(λ)輸出：（“未發(fā)生沖突” ，λc，dO）或（“發(fā)生沖突”）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 （“發(fā)生沖突”）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 （ “未發(fā)生沖突”， λc，dO）

1.1.3 實(shí)驗(yàn)驗(yàn)證

本節(jié)設(shè)計(jì)了2種不同的三維場(chǎng)景配置，分別采用相同大小的立方體和3種不同大小的立方體來(lái)表示無(wú)人機(jī)，來(lái)驗(yàn)證基于GJK的沖突網(wǎng)絡(luò)構(gòu)建算法的有效性與及時(shí)性。

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

圖5 2種不同場(chǎng)景下的沖突識(shí)別Fig.5 Conflict identification in two different scenarios

為了驗(yàn)證無(wú)人機(jī)沖突網(wǎng)絡(luò)構(gòu)建算法的有效性與識(shí)別效率，分別針對(duì)沖突識(shí)別準(zhǔn)確率和沖突識(shí)別時(shí)間2個(gè)指標(biāo)，與三維坐標(biāo)系下通過(guò)成對(duì)計(jì)算無(wú)人機(jī)之間的歐氏距離來(lái)識(shí)別沖突的傳統(tǒng)方法進(jìn)行比較。

在沖突識(shí)別準(zhǔn)確率比較實(shí)驗(yàn)中，無(wú)人機(jī)的數(shù)量從2架不斷增加到20架，不同數(shù)量無(wú)人機(jī)分別在三維環(huán)境中運(yùn)行30 s，在該時(shí)段內(nèi)實(shí)際發(fā)生的沖突數(shù)量為N0，算法識(shí)別到的沖突數(shù)量為N，假設(shè)不存在虛假?zèng)_突告警情況，定義沖突準(zhǔn)確率為Ec=N/N0。在傳統(tǒng)基于Reich模型［24］的沖突識(shí)別算法中，將無(wú)人機(jī)安全保護(hù)區(qū)設(shè)置為球形保護(hù)區(qū)，間隔半徑設(shè)置為D=0.02 km，但由于無(wú)人機(jī)種類大小不盡相同，此安全間隔半徑設(shè)置為滿足盡可能多的無(wú)人機(jī)類型，取各種類型無(wú)人機(jī)平均安全間隔作為閾值，當(dāng)無(wú)人機(jī)距離小于閾值時(shí)算法即判定為沖突。為了進(jìn)一步驗(yàn)證算法性能，對(duì)不同算法的準(zhǔn)確率進(jìn)行對(duì)比分析，以20架無(wú)人機(jī)為例，2個(gè)分別為相同種類和不同種類的無(wú)人機(jī)沖突識(shí)別場(chǎng)景，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 沖突識(shí)別準(zhǔn)確率對(duì)比Fig.6 Comparison of conflict identification accuracy

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

圖7所示為不同粒度場(chǎng)景下不同算法的沖突識(shí)別時(shí)間對(duì)比情況。隨著無(wú)人機(jī)數(shù)量的增加，傳統(tǒng)算法的沖突識(shí)別時(shí)間呈近指數(shù)增長(zhǎng)，本文提出的基于GJK的沖突網(wǎng)絡(luò)構(gòu)建算法增長(zhǎng)呈線性增長(zhǎng)，增長(zhǎng)趨勢(shì)較為緩慢，所提算法具有高效性。

圖7 沖突識(shí)別時(shí)間對(duì)比Fig.7 Comparison of conflict identification time

1.2 特征提取及分析

1.2.1 飛行沖突網(wǎng)絡(luò)特征提取

采用復(fù)雜網(wǎng)絡(luò)理論［25］，將無(wú)人機(jī)群體視作復(fù)雜網(wǎng)絡(luò)，其中無(wú)人機(jī)個(gè)體為網(wǎng)絡(luò)的“節(jié)點(diǎn)”，無(wú)人機(jī)之間存在的沖突為網(wǎng)絡(luò)的“邊”。運(yùn)用基于GJK的沖突網(wǎng)絡(luò)構(gòu)建算法，對(duì)復(fù)雜低空環(huán)境中的無(wú)人機(jī)沖突連邊進(jìn)行動(dòng)態(tài)識(shí)別，在此基礎(chǔ)上通過(guò)復(fù)雜網(wǎng)絡(luò)的相關(guān)概念分析低空空域運(yùn)行態(tài)勢(shì)。本文基于復(fù)雜網(wǎng)絡(luò)理論提出以下3個(gè)指標(biāo)，對(duì)空域無(wú)人機(jī)群體的沖突網(wǎng)絡(luò)特征進(jìn)行分析。

1） 沖突數(shù)量

根據(jù)復(fù)雜網(wǎng)絡(luò)中“度”的概念，將Ki定義為與無(wú)人機(jī)節(jié)點(diǎn)i存在沖突關(guān)系的無(wú)人機(jī)數(shù)量，表示為

式中：eij為0-1變量，若無(wú)人機(jī)節(jié)點(diǎn)j與i直接相連，則取值為1，否則為0。

2） 沖突風(fēng)險(xiǎn)等級(jí)

為了使復(fù)雜網(wǎng)絡(luò)更接近于無(wú)人機(jī)飛行場(chǎng)景，通過(guò)無(wú)人機(jī)之間的相對(duì)距離和相對(duì)速度來(lái)表達(dá)無(wú)人機(jī)的真實(shí)關(guān)系，即2架無(wú)人機(jī)接近彼此的速度越快，越容易發(fā)生沖突，無(wú)人機(jī)沖突等級(jí)便越高。定義無(wú)人機(jī)i與無(wú)人機(jī)j之間的沖突風(fēng)險(xiǎn)為

式中：rij為無(wú)人機(jī)i和j的相對(duì)速度；xij為無(wú)人機(jī)i和j之間的相對(duì)距離。

將無(wú)人機(jī)i的沖突風(fēng)險(xiǎn)等級(jí)Ei定義為

3） 聚集系數(shù)

復(fù)雜網(wǎng)絡(luò)中聚集系數(shù)表示某個(gè)節(jié)點(diǎn)相鄰的2個(gè)節(jié)點(diǎn)彼此也相鄰的概率，在無(wú)人機(jī)沖突場(chǎng)景中表示某架無(wú)人機(jī)周圍的無(wú)人機(jī)密集程度，在無(wú)人機(jī)群一個(gè)沖突數(shù)量為Ki的無(wú)人機(jī)節(jié)點(diǎn)i的聚集系數(shù)Ci定義為

式中：Ni表示無(wú)人機(jī)節(jié)點(diǎn)i的Ki個(gè)存在沖突的無(wú)人機(jī)之間實(shí)際存在的沖突的邊數(shù)，即無(wú)人機(jī)i的Ki個(gè)相鄰無(wú)人機(jī)之間實(shí)際存在的鄰居對(duì)的數(shù)目。聚集系數(shù)反映了無(wú)人機(jī)i附近的擁擠程度即沖突發(fā)生的可能性。

1.2.2 飛行沖突網(wǎng)絡(luò)特征分析

設(shè)置低空空域環(huán)境中共有50架無(wú)人機(jī)，采用沖突網(wǎng)絡(luò)構(gòu)建算法建立沖突節(jié)點(diǎn)連邊，對(duì)無(wú)人機(jī)運(yùn)行狀態(tài)構(gòu)成的復(fù)雜網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)演化，網(wǎng)絡(luò)每30 s演化一次，共演化30 min，即網(wǎng)絡(luò)共演化R=60次，每次演化完成時(shí)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量和無(wú)人機(jī)位置關(guān)系，獲得節(jié)點(diǎn)的連接關(guān)系構(gòu)建復(fù)雜網(wǎng)絡(luò)模型。演化第0、5、10、30 min的網(wǎng)絡(luò)如圖8所示。

圖8 空域中無(wú)人機(jī)網(wǎng)絡(luò)演化過(guò)程Fig.8 Evolution of UAV networks in airspace

低空空域內(nèi)的無(wú)人機(jī)群體每進(jìn)行一次演化，提取沖突網(wǎng)絡(luò)中各無(wú)人機(jī)節(jié)點(diǎn)的位置和速度，計(jì)算每一時(shí)刻空域內(nèi)所有無(wú)人機(jī)指標(biāo)的平均值，進(jìn)而度量飛行沖突網(wǎng)絡(luò)的各個(gè)特征指標(biāo)，便可得到各指標(biāo)的時(shí)間序列，如表1所示。通過(guò)仿真發(fā)現(xiàn)，網(wǎng)絡(luò)演化過(guò)程中每架無(wú)人機(jī)平均與2～4架無(wú)人機(jī)發(fā)生沖突，沖突風(fēng)險(xiǎn)等級(jí)集中分布在6～7范圍內(nèi)，聚集系數(shù)集中分布在0.5～0.6范圍內(nèi)，飛行沖突網(wǎng)絡(luò)特征演化過(guò)程如圖9所示。

表1 網(wǎng)絡(luò)演化特征指標(biāo)Table 1 Characteristic indicators of network

圖9 飛行沖突網(wǎng)絡(luò)特征演化Fig.9 Evolution of flight conflict network characteristics

2 基于數(shù)字柵格的無(wú)人機(jī)飛行沖突精細(xì)探測(cè)

無(wú)人機(jī)運(yùn)營(yíng)者可根據(jù)任務(wù)目的和飛行計(jì)劃等信息進(jìn)行無(wú)人機(jī)飛行路徑規(guī)劃，無(wú)人機(jī)則可按照預(yù)先設(shè)定的軌跡實(shí)施飛行活動(dòng)。在實(shí)際運(yùn)營(yíng)過(guò)程中，因存在潛在的飛行計(jì)劃沖突，導(dǎo)致預(yù)先設(shè)定的飛行航跡可能無(wú)法執(zhí)行，而無(wú)人機(jī)運(yùn)行安全與效率水平亦隨著潛在沖突的增加而降低。因此，本節(jié)采用數(shù)字柵格方法，將無(wú)人機(jī)的物理航跡點(diǎn)信息映射到以柵格編碼為索引的數(shù)字柵格中，對(duì)無(wú)人機(jī)潛在沖突進(jìn)行探測(cè)。

2.1 空域數(shù)字柵格剖分

空域柵格化是指基于柵格化思想，建立空域柵格單元剖分方法，構(gòu)建基于柵格索引的空域系統(tǒng)，從而支撐空域系統(tǒng)表征、規(guī)劃、管理與評(píng)估研究的一種空域離散化處理方法。本節(jié)面向低空空域無(wú)人機(jī)運(yùn)行管理需求，建立了離散柵格框架下的低空空域數(shù)字柵格剖分與編碼設(shè)計(jì)方法。

全球空域空間柵格編碼［26］以地球的南極點(diǎn)為基準(zhǔn)點(diǎn)，構(gòu)建了全球柵格系統(tǒng)參考位置，在空域空間柵格剖分的基礎(chǔ)上建立了柵格編碼規(guī)則。該方法采用基于經(jīng)緯度整數(shù)規(guī)則的地球橢球面剖分方法，即以經(jīng)緯度的“度-分-秒”整數(shù)形式進(jìn)行橢球面的空間分區(qū)劃分，這種劃分實(shí)質(zhì)是一種大地坐標(biāo)系的度量參數(shù)離散化描述方法。

定義空域柵格的基本原則：首先，要統(tǒng)一基準(zhǔn)，對(duì)尺度范圍內(nèi)的空域建立統(tǒng)一的標(biāo)準(zhǔn)；其次，要做到可以相互轉(zhuǎn)換，兼容地理位置柵格碼以及全球定位系統(tǒng)（Global Position System， GPS）和北斗等既有標(biāo)準(zhǔn)，實(shí)現(xiàn)位置與編碼的相互轉(zhuǎn)換；最后，要做到高效實(shí)用，以地理經(jīng)緯柵格為原型，劃設(shè)不同層級(jí)的空域，基于空域管理需求，在不同層級(jí)的柵格建立應(yīng)用規(guī)范。根據(jù)上述原則進(jìn)行低空空域離散建模，將連續(xù)空間離散為基本空域，用空域編碼取代經(jīng)緯度標(biāo)識(shí)空間位置，以低空空域編碼為索引，建立描述低空空域的數(shù)據(jù)結(jié)構(gòu)，管理低空空域內(nèi)活動(dòng)。

由于無(wú)人機(jī)多數(shù)在中低空空域內(nèi)運(yùn)行，機(jī)動(dòng)性較高，因此柵格編碼模型采用地球球面和高度分開處理的方法，平面編碼和高度編碼均采取“Z”形編碼，將柵格左下角位置點(diǎn)定義為柵格坐標(biāo)原點(diǎn)，分別在地理經(jīng)緯度空間和高度空間內(nèi)定義柵格?；诘乩砜臻g經(jīng)緯度，進(jìn)行球面柵格劃分，共劃分8個(gè)層級(jí)的遞歸柵格。針對(duì)不同的層級(jí)柵格，建立柵格劃分矩陣，n為柵格劃分層級(jí)，取值1～8，設(shè)定柵格所在劃分矩陣的行數(shù)和列數(shù)為(pn，qn)，劃分矩陣可表示為

在地球墨卡托投影坐標(biāo)系統(tǒng)上，首先以經(jīng)緯度15°為剖分粒度，將地球的橢圓面進(jìn)行完整劃分，具體情況如圖10所示。

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

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

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

以第8級(jí)柵格編碼生成5 km×5 km×0.2 km大小的低空空域柵格環(huán)境，實(shí)驗(yàn)結(jié)果如圖11所示。

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

2.2 空域數(shù)字柵格編碼

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

地理位置的經(jīng)緯度坐標(biāo)信息(Lng，Lat)通過(guò)式（21）～式（22）進(jìn)行編碼轉(zhuǎn)換：

式中：經(jīng)度編碼和緯度編碼分別用CodeLng和CodeLat表示；n表示編碼層級(jí)；gridsizen表示第n層級(jí)柵格粒度大??；Lngd、Lngm和Lngs分別表示經(jīng)度坐標(biāo)中的度、分和秒；Latd、Latm和Lats分別表示緯度坐標(biāo)中的度、分和秒。

針對(duì)不同的應(yīng)用場(chǎng)景，本文所構(gòu)建的柵格編碼可以與柵格劃分矩陣進(jìn)行相互轉(zhuǎn)換。

1） 由柵格編碼轉(zhuǎn)化為劃分矩陣。

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

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

2） 由劃分矩陣轉(zhuǎn)化為柵格編碼。

首先根據(jù)柵格編碼確定柵格劃分層級(jí)n，確定在該層級(jí)下柵格劃分的經(jīng)緯度粒度間隔ΔLng和ΔLat，根據(jù)式（25）和式（26）計(jì)算得到柵格原點(diǎn)的經(jīng)緯度坐標(biāo)。

然后，根據(jù)經(jīng)緯度坐標(biāo)，利用式（21）和式（22）計(jì)算得到柵格編碼。

空域柵格化為低空無(wú)人機(jī)空中交通管理提供了一種新的位置參考基準(zhǔn)，通過(guò)數(shù)學(xué)模型在計(jì)算機(jī)信息空間內(nèi)完成了對(duì)物理空間的數(shù)字化重構(gòu)，距離運(yùn)算可以轉(zhuǎn)化為編碼或者劃分矩陣之間的運(yùn)算，可以更加快速和準(zhǔn)確地判斷無(wú)人機(jī)之間的空間位置關(guān)系。

2.3 基于數(shù)字柵格的沖突探測(cè)模型

在空域柵格編碼的基礎(chǔ)上增加時(shí)間維度，構(gòu)造數(shù)字柵格單元，時(shí)間編碼采用數(shù)字編碼，以0為開始時(shí)間，運(yùn)行的最長(zhǎng)時(shí)間為最大時(shí)間上限，按照?qǐng)D10的柵格剖分方法，整體八級(jí)編碼呈現(xiàn)如圖12所示。

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

通過(guò)特定的空間區(qū)域和時(shí)間范圍的時(shí)空編碼來(lái)表示無(wú)人機(jī)的時(shí)空信息，每個(gè)空間內(nèi)的物體均可用一個(gè)或多個(gè)柵格表示，建立一定空域內(nèi)的多級(jí)時(shí)空索引。根據(jù)劃設(shè)的實(shí)驗(yàn)空域?qū)?shù)據(jù)表主鍵進(jìn)行初始化，進(jìn)行排序后的時(shí)空柵格編碼與具有特定時(shí)空屬性的柵格密切相關(guān)，因此將其設(shè)置為數(shù)據(jù)表中的主鍵。

當(dāng)一個(gè)空間柵格中存在一架無(wú)人機(jī)時(shí)，對(duì)應(yīng)代碼記錄為1；否則設(shè)置為0。時(shí)間信息將記錄在數(shù)據(jù)庫(kù)表中的每一行，并具有開始時(shí)間戳和結(jié)束時(shí)間戳，以此表示某無(wú)人機(jī)在特定時(shí)間段在該空間柵格內(nèi)。因此，通過(guò)數(shù)字柵格索引，可以將沖突探測(cè)的復(fù)雜成對(duì)計(jì)算問(wèn)題簡(jiǎn)化為空間數(shù)據(jù)庫(kù)查詢問(wèn)題。

為了滿足多級(jí)查詢的需要，建立圖13所示的多表查詢策略，通過(guò)多個(gè)數(shù)據(jù)庫(kù)表管理記錄特定空域內(nèi)的無(wú)人機(jī)信息。每個(gè)數(shù)據(jù)庫(kù)表中只存儲(chǔ)某一級(jí)別編碼對(duì)應(yīng)的數(shù)據(jù)，并且父代編碼具有指向子代編碼所在數(shù)據(jù)庫(kù)表的指針，以此保證當(dāng)查詢完本級(jí)編碼后，如需要進(jìn)一步詳細(xì)查詢，可以直接鏈接到下一級(jí)編碼所在的數(shù)據(jù)庫(kù)表。其中每行數(shù)據(jù)庫(kù)表記錄了所研究空域中的一個(gè)柵格單元，且數(shù)據(jù)庫(kù)表中的行數(shù)與空域中柵格單元的總數(shù)相同。

圖13 低空空域網(wǎng)絡(luò)多級(jí)數(shù)據(jù)庫(kù)表查詢策略Fig.13 Multi-level database table search strategy of low-altitude networks

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

2.4 算法流程

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

式中：UAVA表示無(wú)人機(jī)編號(hào)；[t1，t′1]表示無(wú)人機(jī)占用該柵格的時(shí)間。

根據(jù)空域柵格的時(shí)空屬性，若在同一空間柵格中有兩個(gè)或以上的賦值，則表明有多個(gè)無(wú)人機(jī)飛行計(jì)劃會(huì)占用此柵格區(qū)域，需要判定其時(shí)間上是否存在沖突，若時(shí)間上存在沖突，則可以判定在該柵格處存在飛行沖突，需重新調(diào)整飛行計(jì)劃。若無(wú)人機(jī)大小不同，則首先要判斷其空間編碼是否存父子代關(guān)系，再判斷時(shí)間上是否會(huì)發(fā)生沖突。算法步驟如下：

步驟1假定空域內(nèi)存在n架無(wú)人機(jī)，每一架無(wú)人機(jī)的飛行計(jì)劃軌跡被離散為M個(gè)時(shí)間片，因此空域內(nèi)無(wú)人機(jī)飛行軌跡可表示為n×M元素的矩陣A，同時(shí)構(gòu)建輔助矩陣B。

步驟2將無(wú)人機(jī)飛行空域離散為柵格。

步驟3通過(guò)式（21）和式（22）將每架無(wú)人機(jī)的飛行軌跡點(diǎn)由經(jīng)緯度轉(zhuǎn)換為柵格編碼集合。

步驟4將每一架無(wú)人機(jī)飛行計(jì)劃中預(yù)測(cè)軌跡點(diǎn)對(duì)應(yīng)的柵格單元存入矩陣A，并在輔助矩陣B中存入無(wú)人機(jī)編號(hào)信息。

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

步驟6讀取存在沖突的柵格信息，通過(guò)索引從矩陣B中確定存在沖突的無(wú)人機(jī)編號(hào)信息，對(duì)相關(guān)無(wú)人機(jī)進(jìn)行飛行計(jì)劃調(diào)整。

2.5 仿真驗(yàn)證

為探究數(shù)字柵格方法的沖突檢測(cè)效率，本節(jié)設(shè)計(jì)實(shí)驗(yàn)對(duì)傳統(tǒng)三維坐標(biāo)檢測(cè)方法與數(shù)字柵格數(shù)據(jù)檢索方法下的無(wú)人機(jī)飛行沖突探測(cè)總時(shí)間進(jìn)行了對(duì)比。將沖突探測(cè)總時(shí)間定義為探測(cè)到空域環(huán)境中第一次發(fā)生沖突至最后一次發(fā)生沖突之間的時(shí)間間隔。基于三維坐標(biāo)的沖突檢測(cè)方法通過(guò)成對(duì)計(jì)算任意2架無(wú)人機(jī)之間的歐幾里德距離，并將計(jì)算得到的距離與設(shè)定的閾值進(jìn)行比較來(lái)檢測(cè)沖突。本節(jié)針對(duì)100～1 000架逐漸遞增的無(wú)人機(jī)實(shí)驗(yàn)樣本，其四維航跡點(diǎn)根據(jù)飛行計(jì)劃仿真生成。將傳統(tǒng)方法下的無(wú)人機(jī)安全保護(hù)區(qū)設(shè)置為球形保護(hù)區(qū)，間隔半徑設(shè)置為D=0.02 km，時(shí)間步長(zhǎng)設(shè)置為Δt=0.1 s。上述2種方法下的無(wú)人機(jī)沖突探測(cè)時(shí)間對(duì)比情況如圖14所示。

圖14 不同方法下的無(wú)人機(jī)沖突探測(cè)效率對(duì)比Fig.14 Conflict detection efficiency of different methods

可以看出，隨著無(wú)人機(jī)數(shù)量的不斷增加，初始航跡存在的潛在沖突數(shù)量亦隨之增加，并且2種方法對(duì)應(yīng)的沖突探測(cè)總時(shí)間均呈現(xiàn)增長(zhǎng)趨勢(shì)。當(dāng)無(wú)人機(jī)數(shù)量＜200架時(shí)，2種方法沖突探測(cè)效率相當(dāng)；隨著無(wú)人機(jī)數(shù)量的繼續(xù)增加，傳統(tǒng)成對(duì)計(jì)算方法的沖突探測(cè)時(shí)間增長(zhǎng)趨勢(shì)更加明顯，而基于數(shù)字柵格檢索方法的沖突探測(cè)時(shí)間增長(zhǎng)則較為平緩，基本穩(wěn)定在2 s左右，本文方法相比傳統(tǒng)方法，可將探測(cè)總時(shí)間減少78.4%。顯然，基于數(shù)字柵格的方法明顯優(yōu)于傳統(tǒng)的成對(duì)計(jì)算方法，具有較高的無(wú)人機(jī)沖突探測(cè)效率與穩(wěn)定性。

為進(jìn)一步探究基于數(shù)字柵格的沖突探測(cè)算法效率，現(xiàn)針對(duì)300、500、1 000架的無(wú)人機(jī)飛行場(chǎng)景進(jìn)行算法對(duì)比，為減少仿真隨機(jī)性對(duì)結(jié)果的影響，實(shí)驗(yàn)采取3種固定場(chǎng)景，對(duì)預(yù)生成的固定航路進(jìn)行沖突探測(cè)。圖15所示為本文提出的基于數(shù)字柵格的算法與速度障礙法、傳統(tǒng)基于Reich模型的成對(duì)比較算法在沖突探測(cè)效率方面的對(duì)比情況。

圖15 固定場(chǎng)景下的不同算法沖突探測(cè)效率對(duì)比Fig.15 Conflict detection efficiency of different algorithms in fixed scenarios

由圖15可知，在無(wú)人機(jī)數(shù)量相對(duì)較少的場(chǎng)景中，3種算法的沖突探測(cè)效率差異不大，本文提出的基于數(shù)字柵格的算法時(shí)間略快。隨著無(wú)人機(jī)數(shù)量的不斷增加，本文所提算法的沖突探測(cè)時(shí)間明顯小于其他2種算法，速度障礙法雖略好于傳統(tǒng)成對(duì)比較的方法，但其探測(cè)時(shí)間仍然較長(zhǎng)。因此，本文提出的基于數(shù)字柵格的沖突探測(cè)算法效率較高，相比其他算法具有明顯的優(yōu)勢(shì)。

3 基于網(wǎng)絡(luò)演化的無(wú)人機(jī)飛行沖突最優(yōu)解脫

在基于數(shù)字柵格的無(wú)人機(jī)飛行沖突探測(cè)的基礎(chǔ)上，本節(jié)以無(wú)人機(jī)沖突數(shù)量最少和運(yùn)行成本最低為優(yōu)化目標(biāo)，構(gòu)建了考慮優(yōu)先級(jí)的無(wú)人機(jī)沖突解脫多目標(biāo)混合整數(shù)優(yōu)化模型，對(duì)無(wú)人機(jī)飛行沖突解脫策略進(jìn)行了最優(yōu)求解。

3.1 模型構(gòu)建

3.1.1 模型假設(shè)

1） 將無(wú)人機(jī)簡(jiǎn)化為質(zhì)點(diǎn)，忽略運(yùn)動(dòng)姿態(tài)和機(jī)動(dòng)性能對(duì)沖突管理的影響。

2） 不考慮無(wú)人機(jī)的懸停操作。

3） 在未探測(cè)到?jīng)_突風(fēng)險(xiǎn)和未接收到飛行調(diào)整指令之前，無(wú)人機(jī)始終沿直線飛行。

3.1.2 決策變量

采用3種機(jī)動(dòng)方式對(duì)存在潛在沖突的無(wú)人機(jī)航跡進(jìn)行調(diào)整，分別是航向調(diào)整、高度調(diào)整和速度調(diào)整，因此引入3個(gè)決策變量ωi、hi和υi分別表示對(duì)無(wú)人機(jī)i采取的航跡調(diào)整方式，將決策變量整合到一個(gè)決策向量κi=[w h υ]，κi表示對(duì)無(wú)人機(jī)i航跡進(jìn)行的調(diào)整。

1） 設(shè)定存在N條柵格離散無(wú)人機(jī)軌跡，允許設(shè)置的虛擬航路點(diǎn)數(shù)量即為時(shí)間片數(shù)量M，無(wú)人機(jī)i的初始航段的柵格數(shù)量為L(zhǎng)i，0，虛擬航路點(diǎn)位置的柵格編碼為，對(duì)于空域內(nèi)所有無(wú)人機(jī)航跡虛擬點(diǎn)構(gòu)成的柵格編碼集合為w=(ω1，ω2，…，ωN)。圖16為M=2時(shí)設(shè)置虛擬航路點(diǎn)生成的航跡。

圖16 M=2時(shí)設(shè)置虛擬航路點(diǎn)生成的航跡Fig.16 Trajectory generated by virtual waypoints at M=2

2） 在柵格化空域下，設(shè)定無(wú)人機(jī)i的初始飛行高度層為Hi，0，hi表示無(wú)人機(jī)進(jìn)行高度調(diào)整時(shí)高度改變的柵格數(shù)量，改變高度后飛行高度層變?yōu)镠i′=Hi，0+hi，所 有 無(wú) 人 機(jī) 高 度 調(diào) 整 柵 格 改 變數(shù)量構(gòu)成集合h=(h1，h2，…，hN)。

3） 設(shè)定無(wú)人機(jī)i的初始飛行速度為Vi，0，vi表示無(wú)人機(jī)進(jìn)行速度調(diào)整時(shí)的速度改變量，改變速度解決沖突后飛行速度變?yōu)閂′i=Vi，0+vi，空域內(nèi)所有無(wú)人機(jī)速度調(diào)整量構(gòu)成集合v=(v1，v2，…，vN)。

3.1.3 目標(biāo)函數(shù)

1） 沖突數(shù)量

根據(jù)前述構(gòu)建的基于數(shù)字柵格的沖突探測(cè)方法，通過(guò)離散化低空空域和四維坐標(biāo)將每架無(wú)人機(jī)i的航跡點(diǎn)集合Pi映射到相應(yīng)的編碼柵格結(jié)構(gòu)中，該方法只需判斷無(wú)人機(jī)航跡采樣點(diǎn)Pi，g對(duì)應(yīng)的數(shù)字柵格是否存在其他無(wú)人機(jī)的航跡采樣點(diǎn)。若存在，則判定無(wú)人機(jī)i在航跡采樣點(diǎn)Pi，g處存在一次沖突?？沼騼?nèi)所有航跡之間的沖突數(shù)量可表示為

式中：Φi，g表示無(wú)人機(jī)i在g點(diǎn)發(fā)生沖突。

2） 運(yùn)行成本

從低空空域運(yùn)行角度考慮，無(wú)人機(jī)按照計(jì)劃航跡點(diǎn)集合進(jìn)行飛行的成本應(yīng)盡可能小，輸入的無(wú)人機(jī)航跡點(diǎn)集合是針對(duì)單體最優(yōu)的航跡，若探測(cè)到無(wú)人機(jī)之間的沖突，則無(wú)人機(jī)會(huì)采取機(jī)動(dòng)策略導(dǎo)致飛行前計(jì)劃航跡改變，使無(wú)人機(jī)的飛行距離增加，或當(dāng)采取速度調(diào)整策略時(shí)雖不會(huì)增加額外的飛行距離，但無(wú)人機(jī)的飛行時(shí)間相較于飛行前的計(jì)劃航跡會(huì)有所增加。因此，從飛行時(shí)間、經(jīng)濟(jì)成本等方面考慮，優(yōu)化目標(biāo)為無(wú)人機(jī)實(shí)際飛行解脫的航跡相較于原飛行前無(wú)人機(jī)航跡的航跡成本增加最少，航跡成本包括解脫航跡與飛行前計(jì)劃航跡之間的偏差、解脫后航跡的到達(dá)起飛時(shí)間的改變量2個(gè)部分?？沼蛑兴袩o(wú)人機(jī)的總成本（標(biāo)準(zhǔn)化后的無(wú)量綱數(shù)值）為

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

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

航跡偏移量主要考慮由于解脫策略造成的航跡改變，使解脫后的航跡與飛行前的計(jì)劃航跡產(chǎn)生偏差，定義為每架無(wú)人機(jī)的航跡點(diǎn)集合從第一個(gè)至最后一個(gè)航跡點(diǎn)所有沖突解脫結(jié)束后，實(shí)際的沖突解脫航跡和原飛行前的無(wú)人機(jī)計(jì)劃航跡之間的柵格數(shù)量之差。每架無(wú)人機(jī)的航跡偏移成本可表示為

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

時(shí)間偏移成本主要考慮由于解脫航跡造成的總的運(yùn)行時(shí)間的偏移量，使解脫后的航跡運(yùn)行時(shí)間與飛行前的計(jì)劃航跡的運(yùn)行時(shí)間之間產(chǎn)生的偏差，定義為無(wú)人機(jī)i的解脫航跡運(yùn)行時(shí)間和原飛行前無(wú)人機(jī)計(jì)劃航跡運(yùn)行之間的偏差量，可表示為

式中：i=1，…，N表示無(wú)人機(jī)的數(shù)量；Δti表示無(wú)人機(jī)i的解脫航跡運(yùn)行時(shí)間和原飛行前無(wú)人機(jī)計(jì)劃航跡運(yùn)行之間的偏差值。

3.1.4 約束條件

1） 允許的最大水平路徑長(zhǎng)度

每架無(wú)人機(jī)i的初始航段長(zhǎng)度（占用柵格數(shù)量）Li，0，設(shè)?i為無(wú)人機(jī)i的最大允許航線長(zhǎng)度擴(kuò)展系數(shù)，0≤?i≤1，為了限制航線長(zhǎng)度的延長(zhǎng)，無(wú)人機(jī)i的備選航線水平剖面必須滿足：

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

2） 允許的水平航路點(diǎn)位置

為了限制搜索空間，防止大角度轉(zhuǎn)彎，控制路徑長(zhǎng)度的延長(zhǎng)，因此對(duì)每個(gè)虛擬航路點(diǎn)的可能位置進(jìn)行了限定。對(duì)于每個(gè)軌跡i和第m個(gè)虛擬航路點(diǎn)，無(wú)人機(jī)在x和y方向上的偏移分量Wmi，x和Wmi，y表示為

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

為了獲得規(guī)則的航跡，相鄰2個(gè)航跡點(diǎn)的x方向分量不能重疊，即

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

3） 允許的高度層改變

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

式中：hi，max為無(wú)人機(jī)i允許最大高度層改變量。

4） 允許的速度改變

由于受自身性能約束和飛行環(huán)境影響，無(wú)人機(jī)存在最大和最小飛行速度限制，無(wú)人機(jī)i受自身性能約束的速度限制表示為

綜上所述，本文考慮的動(dòng)態(tài)沖突解脫問(wèn)題可以表示為以下的多目標(biāo)混合整數(shù)優(yōu)化問(wèn)題：

3.2 算法設(shè)計(jì)

無(wú)人機(jī)沖突解脫問(wèn)題的復(fù)雜度隨決策變量數(shù)量的增加以幾何級(jí)數(shù)增長(zhǎng)，決策變量之間存在強(qiáng)耦合關(guān)系，且本文提出的沖突解脫模型是非線性不可微分的復(fù)雜模型，難以在短時(shí)間內(nèi)得到目標(biāo)解，因此本文采用元啟發(fā)式算法進(jìn)行求解。無(wú)人機(jī)沖突解脫是一個(gè)多目標(biāo)優(yōu)化問(wèn)題，鑒于非支配排序遺傳算 法（Non-Dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）在非支配排序、擁擠距離排序、運(yùn)行速度及解集收斂性等方面的諸多優(yōu)點(diǎn)，采用NSGA-Ⅱ算法對(duì)所建優(yōu)化模型進(jìn)行求解。

1） 編碼設(shè)計(jì)

染色體編碼對(duì)算法求解效率至關(guān)重要，本文采用整數(shù)編碼方式對(duì)染色體進(jìn)行編碼，每條染色體代表所有無(wú)人機(jī)航跡方案；染色體長(zhǎng)度表示所有無(wú)人機(jī)的總架數(shù)，染色體內(nèi)每個(gè)基因位置表示無(wú)人機(jī)各航跡點(diǎn)所做的航向、高度和速度調(diào)整。染色體基因編碼實(shí)例如圖17所示。

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

2） 快速非支配排序

快速非支配排序是依據(jù)種群個(gè)體的帕累托支配關(guān)系對(duì)種群分層，為了引導(dǎo)搜索向帕累托最優(yōu)解集方向進(jìn)行?？焖俜侵渑判虻乃枷胧墙o每個(gè)個(gè)體p都賦予3個(gè)參數(shù)：Sp、np和rankp，其中，Sp為種群中被個(gè)體p支配的個(gè)體集合；np為種群中支配個(gè)體p的數(shù)量；rankp為個(gè)體p的帕累托層級(jí)。快速非支配排序的操作過(guò)程如下所示。

步驟1遍歷種群計(jì)算每個(gè)個(gè)體的參數(shù)S和n。

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

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

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

3） 擁擠距離

為了保證種群的多樣性，通過(guò)優(yōu)先選擇擁擠距離較大的個(gè)體，可使計(jì)算結(jié)果較均勻分布，避免個(gè)體都集中于某一處導(dǎo)致無(wú)法得到帕累托最優(yōu)解集。計(jì)算個(gè)體i擁擠距離disi步驟為：

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

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

3.3 優(yōu)先解脫流程

在沖突解脫過(guò)程中，引入優(yōu)先級(jí)概念，優(yōu)先級(jí)高的無(wú)人機(jī)優(yōu)先采取機(jī)動(dòng)策略避讓優(yōu)先級(jí)低的無(wú)人機(jī)，通過(guò)復(fù)雜網(wǎng)絡(luò)的相關(guān)概念確定空域中運(yùn)行無(wú)人機(jī)的沖突解脫優(yōu)先級(jí)。基于1.2節(jié)提出的飛行沖突網(wǎng)絡(luò)特征，以式（42）～式（44）定義無(wú)人機(jī)在解脫順序時(shí)的優(yōu)先級(jí)原則，得到無(wú)人機(jī)解脫順序。

原則1無(wú)人機(jī)平均沖突數(shù)量，計(jì)算公式為

原則2無(wú)人機(jī)平均沖突風(fēng)險(xiǎn)等級(jí)，計(jì)算公式為

原則3無(wú)人機(jī)平均聚集系數(shù)。計(jì)算公式為

在本文全局沖突解脫場(chǎng)景中，優(yōu)先級(jí)高的無(wú)人機(jī)優(yōu)先計(jì)算解脫方案，優(yōu)先級(jí)低的無(wú)人機(jī)將已解脫的無(wú)人機(jī)視為移動(dòng)障礙物限制，保證已解脫的無(wú)人機(jī)不會(huì)與優(yōu)先級(jí)低的無(wú)人機(jī)發(fā)生沖突。定義障礙物集合Ω，障礙物優(yōu)先級(jí)SΩ=0；無(wú)人機(jī)i的優(yōu)先級(jí)Si=1，2，…，Smax；S越小表明無(wú)人機(jī)優(yōu)先級(jí)越高。沖突解脫流程具體如下所示

步驟1獲取無(wú)人機(jī)信息，提取空域內(nèi)所有無(wú)人機(jī)的水平位置、高度、速度以及航向，根據(jù)2.3節(jié)中的方法進(jìn)行沖突探測(cè)，得到所有存在潛在沖突的航跡集合G。

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

步驟3計(jì)算優(yōu)先級(jí)最高的無(wú)人機(jī)對(duì)應(yīng)的沖突解脫策略。

步驟4S=S+1，若S＞Smax，則已遍歷所有優(yōu)先級(jí)，沖突解脫算法結(jié)束。

步驟5將Si＜S的所有無(wú)人機(jī)視作障礙物，加入障礙物集合Ω，求解當(dāng)前優(yōu)先級(jí)無(wú)人機(jī)對(duì)應(yīng)的沖突解脫策略，返回步驟4。

3.4 仿真驗(yàn)證

3.4.1 實(shí)驗(yàn)設(shè)計(jì)

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

表3 無(wú)人機(jī)沖突解脫模型參數(shù)設(shè)置Table 3 Parameter of UAVs conflict resolution model

NSGA-Ⅱ算法參數(shù)設(shè)置如下：設(shè)定種群大小為200，最大進(jìn)化代數(shù)200代，交叉概率0.9，變異概率0.05。在上述基準(zhǔn)參數(shù)下，進(jìn)行仿真實(shí)驗(yàn)，所有實(shí)驗(yàn)結(jié)果皆基于10次獨(dú)立運(yùn)行。

根據(jù)飛行狀態(tài)網(wǎng)絡(luò)連邊的建立規(guī)則，采取數(shù)字柵格的沖突探測(cè)算法，根據(jù)設(shè)定的50架無(wú)人機(jī)初始飛行計(jì)劃，當(dāng)2架無(wú)人機(jī)之間存在潛在飛行沖突時(shí)，則認(rèn)定無(wú)人機(jī)之間存在聯(lián)系，并建立連邊，基于復(fù)雜網(wǎng)絡(luò)的無(wú)人機(jī)初始沖突分布如圖18所示。

圖18 無(wú)人機(jī)運(yùn)行狀態(tài)網(wǎng)絡(luò)Fig.18 Network of UAVs operation

3.4.2 結(jié)果分析

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

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

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

圖20 不同優(yōu)先級(jí)原則下沖突數(shù)量和運(yùn)行成本算法收斂變化Fig.20 Conflict number and operation cost algorithm convergence changes with different priority principles

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

對(duì)考慮優(yōu)先級(jí)和不考慮優(yōu)先級(jí)的沖突解脫仿真結(jié)果進(jìn)行對(duì)比分析，設(shè)定沖突風(fēng)險(xiǎn)等級(jí)為優(yōu)先級(jí)排序原則，選取沖突數(shù)量最小的非支配解與不考慮優(yōu)先級(jí)的沖突解脫策略，對(duì)高度改變、水平航跡偏移量和速度改變進(jìn)行成本比較分析，結(jié)果如圖21所示。圖中考慮優(yōu)先級(jí)是指采用平均沖突風(fēng)險(xiǎn)等級(jí)定義的無(wú)人機(jī)解脫優(yōu)先級(jí)，不考慮優(yōu)先級(jí)是指不設(shè)置無(wú)人機(jī)解脫順序?qū)沼騼?nèi)無(wú)人機(jī)進(jìn)行機(jī)動(dòng)調(diào)整。

圖21 考慮優(yōu)先級(jí)與直接解脫成本對(duì)比Fig.21 Cost comparison of priority and direct resolution

根據(jù)圖21可知，以沖突風(fēng)險(xiǎn)等級(jí)為優(yōu)先級(jí)排序原則進(jìn)行高度層調(diào)整相比不考慮優(yōu)先級(jí)可以少調(diào)整21個(gè)高度層，平均每架無(wú)人機(jī)高度層調(diào)整值減少了32.8%；水平航跡調(diào)整相比不考慮優(yōu)先級(jí)少調(diào)整991個(gè)柵格，平均每架無(wú)人機(jī)水平調(diào)整值減少了21.4%；速度調(diào)整相比不考慮優(yōu)先級(jí)少調(diào)整51.3 m/s，平均每架無(wú)人機(jī)水平調(diào)整值減少了14.6%。通過(guò)對(duì)比分析可知，本文提出的考慮優(yōu)先級(jí)的沖突解脫方法使得無(wú)人機(jī)的機(jī)動(dòng)解脫成本更低，結(jié)合高度調(diào)整、速度調(diào)整和航向調(diào)整3種不同的解脫方法，可以更好地利用低空空域資源，降低無(wú)人機(jī)運(yùn)行成本，提高沖突管理效率。

4 結(jié) 論

本文針對(duì)多元化空域、高密度流量和高動(dòng)態(tài)演化交織形成的復(fù)雜低空系統(tǒng)，構(gòu)建了基于沖突連邊動(dòng)態(tài)識(shí)別的無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)模型及特征度量方法，提出了基于數(shù)字柵格的無(wú)人機(jī)飛行沖突精細(xì)探測(cè)算法，建立了考慮優(yōu)先級(jí)的無(wú)人機(jī)飛行沖突最優(yōu)解脫方法，實(shí)現(xiàn)了低空空域內(nèi)無(wú)人機(jī)飛行沖突的精細(xì)化管理。主要結(jié)論如下：

1） 提出的基于GJK算法和復(fù)雜網(wǎng)絡(luò)理論的無(wú)人機(jī)飛行沖突網(wǎng)絡(luò)動(dòng)態(tài)構(gòu)建方法，可實(shí)現(xiàn)對(duì)任意低空空域系統(tǒng)內(nèi)無(wú)人機(jī)群體飛行沖突的動(dòng)態(tài)識(shí)別，以及沖突網(wǎng)絡(luò)特征的多維提取。

2） 與傳統(tǒng)的基于三維坐標(biāo)的沖突探測(cè)方法相比，基于數(shù)字柵格的沖突探測(cè)和基于GJK的沖突探測(cè)算法具有更高的沖突探測(cè)效率，可顯著降低沖突探測(cè)的時(shí)間成本。

3） 所提方法尤其適用于低空空域多機(jī)型混雜運(yùn)行場(chǎng)景，可將無(wú)人機(jī)沖突探測(cè)效率由“指數(shù)增長(zhǎng)級(jí)”降至“線性增長(zhǎng)級(jí)”。

4） 綜合考慮無(wú)人機(jī)的沖突數(shù)量與飛行狀態(tài)，將平均沖突風(fēng)險(xiǎn)等級(jí)作為解脫優(yōu)先級(jí)原則，可以得到最優(yōu)的沖突解脫策略非支配解，從而更好減少低空空域全局范圍的無(wú)人機(jī)沖突數(shù)量，有效降低沖突解脫成本。