基于復雜網絡的無人機飛行沖突解脫算法

黃洋，湯俊，老松楊

國防科技大學 系統工程學院，長沙 410000

近年來無人機系統被廣泛運用到戰爭環境和城市環境中。由于執行任務環境和任務本身逐漸變得復雜，多無人機的集群作業變得越來越有研究價值。無人機之間能夠實現自主防撞是無人機集群控制的前提，包括無人機群內部的防撞和無人機群之間的防撞，解決無人機群防撞問題對當前無人機集群作業具有重大意義。

無人機的動力學模型較為復雜，面臨的威脅也有高度不確定性。因此在無人機遇到威脅時依賴飛控計算機進行路徑生成，會影響無人機群執行任務的效率，同時也可能造成連鎖碰撞[1]。考慮到無人機的集群防撞面臨著空中威脅數量多、運動速度大等特點，通過對無人機群構建復雜網絡，分析在受威脅狀態下網絡的性質以確定合適的避撞策略，使得無人機群在性能約束的條件下具備防撞能力，可大大提高無人機集群防撞的實時性、準確性和適用性。無人機避撞有很多算法，文獻[2-3]對抽象的各種算法進行廣泛和細致地調查并且總結了用于避免無人機之間碰撞的原型系統的概念。蒙特卡羅算法[4]在傳統空中防撞系統(Traffic Collision Avoidance System，TCAS)算法上性能有所提升，但是主要解決一對無人機之間的防撞問題，沒有考慮到全局空域的無人機狀態。人工勢場法[5]的優勢在于應答時間很短、計算量小，因此具備實時性，但是通常不能準確到達目標而且產生的軌跡往往不適用于固定翼無人機，因此不能很好地解決大規模無人機防撞問題。蟻群算法[6]可以很好地解決多無人機的路徑規劃問題，但是考慮的防撞問題主要是固定的障礙物，在無人機集群防撞方面很難實現，并且需要大量迭代計算，所以不能滿足無人機集群飛行時的防撞問題。遺傳算法[7]也是仿生優化算法，與蟻群算法存在相似的問題，無法解決無人機群的實時防撞問題。共生模擬[8]本質上還是優化算法，優勢在于產生的全局路徑規劃更加平滑，但是仍舊存在計算耗時長的特點，無法實時解決無人機群沖突解脫問題。幾何優化算法[9]能解決無人機群的沖突解脫問題，但是由于仍然是優化問題，計算量比較大。概率算法[10]需要進行持續計算，很難滿足實時性的需求。著色Petri網[11]主要應用在民航領域，主要考慮4架以下飛機之間的沖突，對大規模的集群運算無能為力。共識算法[12]解決了多個無人機交匯的問題，無人機對其將要到達交匯點的預計到達時間達成共識來解決沖突，但是也沒能解決大規模條件下的無人機防撞問題。卡爾曼濾波算法[13]研究了射頻信號在無人機位置估計和碰撞避免中的應用，提出了一種有色噪聲模型，并將其應用于擴展卡爾曼濾波器中以進行距離估計，該算法解決了當全球定位系統不可用時的碰撞避免方案，但是沒能對全局的無人機進行協調控制，局限于最后時刻的防撞。馬爾科夫決策過程法[14]被創新地用于無人機追蹤目標上，其防撞的策略是提前告知威脅無人機的實時位置，以此控制無人機在安全距離范圍上。基于Dubins曲線算法[15]主要是通過判斷不同路徑的優劣來選擇出避撞的路徑，沒有辦法滿足無人機群之間的防撞問題。預測控制算法[16]可以解決基本的一對無人機之間的防撞，并且文章是對直升無人機做的仿真實驗。基于可達集的算法[17]對民航飛機防撞作了優化，可達集可以提升避撞的成功率，但是仍然無法解決無人機群的防撞問題。各種算法之間常常結合在一起使用。但這些算法主要是考慮成對無人機防撞，沒考慮復雜多機態勢下的集群防撞問題，同時存在迭代次數多、計算復雜、實時性不好等缺點，無法適用于無人機技術高速發展背景下的無人機集群防撞需求。當無人機數量增多時，需要適應于大規模的無人機防撞算法。文獻[18-19]提供了多無人機情況下的沖突解脫方案，但都存在效率較低的問題。文獻[20]設計了基于Skinner操作條件反射理論框架(GA-OCPA)的學習系統以達到對威脅的規避，這可以借鑒到多無人機條件下沖突解脫策略的算法中。

復雜網絡理論認為關鍵節點有十分重要的性質[21-23]，對整個復雜網絡系統的影響程度最大。本文提出的基于復雜網絡的無人機避撞算法具有簡潔、高效、實用等特點，最重要的是考慮了每一時刻無人機群系統的安全性指標使得整個飛行過程整體的安全性達到最大，這樣的特性對于無人機群而言是非常有利的。該防撞系統由2個關鍵步驟組成：關鍵節點選擇和避撞方向選擇。本文算法將無人機群之間的威脅用復雜網絡來表達，根據飛行速度、飛行角度、安全區域3個參數的變化建立無人機網絡模型，通過網絡的魯棒性迅速減小來達到網絡盡快潰散的目的，實現無人機群之間的威脅盡快消除。本文將全局空域分為很多小塊，無人機分布在不同的子空間中。假設兩群互相合作的無人機群朝著相反的方向飛行，在有實時通信的環境下所有的無人機朝著既定的目標進行飛行同時需要執行避撞操作。每一架無人機都配備有飛行軌跡控制單元，避撞系統計算出的避撞策略通過實時數據鏈接與周邊的無人機進行信息交互。

1 模型構建

本節描述的是無人機集群的模型構建。首先，對沖突進行檢測，定義了無人機的屬性用以刻畫無人機的各種狀態，構建了無人機的鄰域集以及沖突發生的條件。然后，說明了關鍵節點選擇以及避撞方向選擇策略，其中對一種意外入侵的特殊情況進行說明并提供解決方案。最后，對無人機的安全性定義了安全性分析指標。

1.1 沖突檢測

將無人機用節點表示，無人機的狀態被系統實時監控，其屬性表示為{UAV, Velocity, Position, Angle,t, State, Sense, Strength, Approaching time, Time cost, Key node}。其中：UAV表示無人機編號；Velocity表示無人機速度；Position表示無人機當前位置；Angle表示無人機飛行角度；t表示無人機當前所處時刻；State表示無人機飛行狀態(處于避撞路徑上或原路徑上)；Sense表示無人機避撞方向選擇；Strength表示無人機方向改變程度；Approaching time表示無人機到達最近接近點(Closest Point of Approach, CPA)剩余的時間；Time cost表示在整個飛行過程中無人機消耗的時間；Key node表示無人機是否被選擇為關鍵節點。

無人機有6種狀態，分別是：狀態1，正常的巡航狀態；狀態2，由防撞系統檢測到剛好遇到威脅的狀態；狀態3，防撞系統檢測到有威脅后開始執行避撞程序正在改變的軌跡上飛行的過程；狀態4，在執行避撞的時間達到預計的位置時，按照原有巡航狀態進行飛行的過程；狀態5，在狀態4結束后開始按照與防撞軌跡相反的角度進行返航回到原有軌道上；狀態6，在返航過程結束后按照原有巡航的角度進行巡航。

為了檢測沖突的目的，無人機在笛卡爾系統中被識別。每個無人機在相應時刻的位置表示為

(1)

定義最大爬升(俯仰)角，該角度由無人機的性能決定，其限制了無人機在執行避撞任務時的航跡在垂直平面內的上升和下滑的最大角度，設最大俯仰角為φmax，約束可以表達為

(2)

對無人機進行鄰域集的構建，無人機遇到威脅的坐標設為(x,y,z)，最小的鄰域距離為lmin，最大的鄰域距離為lmax，最低飛行高度為hmin，則無人機在飛行中的鄰域點s的集合為

S(i)={s∈V-{i}|lmin≤d(i,s)≤lmax;

(3)

式中：d(i,s)為i和s之間在一個仿真步長的歐式距離；V-{i}為除無人機i當前位置之外的所有可能到達位置的集合。

定義最大偏航角為Φmax，其到達目標的后向鄰域為A(i)，預計的到達角度為θgoal。

A(i)={s∈V∧s≠g|lmin≤d(i,g)≤lmax;

(4)

(5)

(6)

(7)

(8)

(9)

這表示左右兩個條件只要一個被滿足，TA事件即被觸發。用T1來表示第1對無人機觸發TA警報的時刻。從那一刻起，構建一個網絡，每個無人機都被表示為一個節點。如果一對節點發生沖突，則節點將建立連接。在時刻T1，系統中的所有節點將檢查無人機是否正在接近，如果無人機正在彼此接近，則連接兩個節點，判斷條件為

(10)

這表示左右兩個條件只要一個被滿足就代表2個節點在相互靠近。在一對無人機情況下，按照以下原則進行避撞。無人機防撞示意圖如圖1所示，UAV1從右側至左側進行巡航，UAV2和UAV3從左側向右側進行巡航，此時UAV1被選擇為關鍵節點，可以根據此時的場景進行避撞方向選擇，其中向上爬升和向下爬升預計CPA時刻的目標點與UAV2和UAV3需保持最小安全距離ALIM(Altitude LIMitation)。具體的關鍵節點選擇和方向選擇策略由后文論述。

圖1 無人機防撞示意圖Fig.1 Sketch of collision avoidance of UAVs

1.2 關鍵節點選擇策略

定義碰撞空間，在系統檢測到一對無人機有碰撞風險時，系統通過全域數據分析得到所有的未來可能撞擊的無人機編號并獲取對應無人機的狀態。由這些無人機組成的空域被稱作碰撞空間。其中對有碰撞風險的無人機之間進行連線，形成網絡進行分析。用鄰接矩陣記錄無人機之間的狀態。用節點N代表無人機，用邊E代表無人機之間的關系。定義一個集合Ω以包含滿足條件的節點。本文以2組無人機在2個不同的垂直平面上的情景為例闡述概念。如圖2所示，2組節點分布在相應的垂直平面上。圖中：紅色節點和藍色節點表示兩組相向而飛的無人機；節點之間的連線表示節點之間存在威脅關系；1 n mile=1 852 m，1 ft=0.304 8 m。網絡建成后，制定網絡描述規則來描述多無人機系統的內部特征。網絡中的節點在不同的無人機群中具有不同的屬性。

圖2 無人機群復雜網絡概念圖Fig.2 Conceptual framework of complex network for UAVs

為了使網絡更加接近于真實場景，只使用邊數是不夠的。邊應該有額外的屬性來監視無人機的真實關系。該關系包含無人機之間的相對距離和相對速度。一對無人機接近對方的速度越快，就越危險。所以每條邊的權重取決于無人機之間的相對距離和相對速度，從而定義無人機i與無人機j之間的邊緣權重ωij為

(11)

式中：υij為矢量方向的相對速度；dij為無人機i和無人機j之間的距離。這就意味著2架無人機接近的速度越快，無人機之間的邊的權重就越大。關鍵節點選擇的公式為

(12)

計算每架無人機的邊緣權重之和，邊緣權重之和最大的節點被定義為關鍵節點。即選出使得邊緣權重之和最大的無人機序號ikey。

1.3 避撞方向選擇策略

在這個新沖突模型情況下，盡可能地降低魯棒性和完整性至關重要。將網絡的魯棒性定義為

(13)

(14)

式中：I為網絡中被剔除的節點數量；M為網絡子圖中最大的鏈接數量。

這個新模型的目標是盡可能快地分解網絡。這意味著在關鍵節點被清除之后，網絡的魯棒性和網絡的組件數量應該盡可能低。也意味著無人機相互離開，墜毀的風險越來越小。在仿真步驟中，新模型找出關鍵節點并評估連接的魯棒性或連接的組件數目。關鍵節點將選擇變化的航向，在下一個仿真步驟中形成一個新的網絡，新的模型將再次選擇關鍵節點。該模型將監測多無人機系統，以確定是否發布TA警報，如果模型停止查找關鍵節點，多無人機系統將被認為是安全的。

如圖3所示，該場景描述的是在一個特殊的垂直面碰撞空間內的無人機關聯情況。每個節點代表不同的無人機，紅色節點和藍色節點分別表示2個飛行朝向的無人機群，虛線框表示系統認為的藍色節點受威脅區域，在受威脅區域內的紅色節點被認為是對藍色節點產生威脅的節點。由于在該場景下，紅色節點的受威脅區域內包含的藍色節點數最多為2個，而藍色節點的受威脅區域內包含的紅色節點個數都至少是2個，因此在該場景下，按照圖示順序先后由中間的藍色節點、左側藍色節點、右側藍色節點作為關鍵節點，由魯棒性最小原則可得這些節點的避撞方向均為下降的方向。

圖3 查找關鍵節點的過程示意圖Fig.3 Sketch of process of locating key nodes

由于無人機群防撞仍然不可避免地依賴基于一對無人機的沖突解脫過程，同時也需要考慮特殊情況，即在空域的邊界處如果出現新的入侵無人機可能會發生新的碰撞，因此構造相應模型解決這種特殊情況。假設首次觸發RA(Resolution Advisory)的時刻為t，并且關鍵節點對應的無人機和相應的入侵無人機m遵從同樣的避撞邏輯。在時刻t+Δt出現新的入侵無人機m，在這種情況下關鍵節點對應的飛機沒有改變其飛行軌跡，方向改變的規則將遵循優先級規則，此時能夠提供最大豎直方向分離距離的方案將被選擇，這與在既定空域內的避撞方向選擇的原則一致，即保證在威脅時刻安全性達到最大。

當選擇向上飛時：

(15)

當其方向不做改變時：

(16)

當選擇向下飛時：

(17)

在最近接近點處關鍵節點對應的無人機與入侵無人機m的豎直距離表示為

(18)

(19)

(20)

當關鍵節點對應的無人機在完成自己的方向計算之前就接收到入侵無人機m的方向選擇建議或者無人機i的優先級比入侵無人機m低，則無人機的方向選擇按照如下公式進行：

(21)

入侵無人機的RA方向選擇滿足

(22)

(23)

式中：

(24)

1.4 無人機的安全性分析

文獻[24]對沖突解脫的結果進行了安全性驗證。在本文中考慮某個時刻的無人機群的安全性，提出基于狀態的安全性指標。按照Q統計的方法可以對無人機群進行安全性分析。

(25)

式中：Xi表示第i架無人機撞毀的可能性，這里就用第i架無人機的魯棒性指標Ri表示Xi；N代表無人機群的無人機數目。由于Q衡量的是某個時刻的安全性，因此每一架無人機的安全率的提高能夠提高無人機群的安全性。

2 關鍵步驟分析

本節描述的是無人機集群防撞的算法，本文將該算法分為步驟1和步驟2，分別對應關鍵節點選擇步驟和避撞方向選擇步驟。2個步驟也分別對應無人機防撞過程的2個階段，即防撞系統選取避撞的無人機序號和該無人機避撞的方向。

2.1 關鍵節點選擇步驟

圖4 關鍵節點選擇步驟流程圖Fig.4 Flowchart step for key node selection

關鍵節點選擇步驟解決了避撞策略的第1步，即選擇關鍵節點并由關鍵節點對應的無人機繼續執行方向選擇步驟提供的方向策略。關鍵節點選擇流程圖如圖4所示，對仿真整個過程和每一架無人機進行檢測是否有TA事件觸發，一旦有TA事件觸發，對無人機群進行網絡構建，計算被包含無人機之間的相對速度和相對距離，然后通過計算受威脅程度值選擇出關鍵節點并執行步驟2，在為關鍵節點選擇好避撞方向后，更新關鍵節點的狀態。步驟1不斷執行，TA事件消除時進入下一個循環，更新全局無人機的狀態。如果所有無人機到達安全區域，則步驟1終止。

2.2 避撞方向選擇步驟

步驟2是對無人機避撞方向選取策略的描述，當防撞系統執行到步驟2中，如圖5所示，首先會為關鍵節點構建探測網絡從而對關鍵節點所處狀態進行分析。由于組建探測網絡時是對一定范圍內的空域進行探測，所以分為單機入侵和多機入侵2種場景。如果探測網絡中關鍵節點的入侵機數為一架，若探測與關鍵節點的垂直高度差小于1/(2ALIM)，構建全局分析網絡,分別計算關鍵節點選擇上升和下降的全局魯棒性并選擇魯棒性小的方向；若入侵機與關鍵節點的垂直高度差大于1/(2ALIM)，則直接選擇垂直方向上遠離入侵機的方向進行避撞。如果探測到多機入侵，則考察入侵機群中與關鍵節點對應無人機垂直方向高度的相對高度，若更多的無人機高于關鍵節點的高度，則關鍵節點選擇向下的方向進行避撞；若低于關鍵節點的入侵無人機數量更多，則關鍵節點選擇向上的方向進行避撞。

3 仿真實驗及結果分析

在本節中仿真計算出的結果能夠展示出在動態情況下的多無人機防撞操作效果。本文設置了了仿真場景1和場景2，分別對應復雜多機垂直平面相遇場景和復雜多機無規則集群場景。初始化參數如表1所示。其中：A和B指的是無人機避撞過程中俯仰角度改變的范圍區間。仿真步長設為1 s，即每1 s都會對全局空域的威脅進行分析并給出解決方案，系統也會實時更新無人機的飛行狀態。在后文的仿真中，如果遇到無人機群數量龐大的場景時，會對空域做均勻的劃分，然后每個仿真步長及時更新全局空域的無人機狀態，這樣相當于直接對全局無人機計算進行的一個簡化，以此提升計算效率。例如50架飛機的情況下，由于兩兩無人機間需要進行計算，這樣就要進行50×50次的威脅判斷，但是分成5個空域后(此時每個空域有10架無人機)就只需進行10×10×5次威脅判斷，大大減少了威脅判斷次數，從而提升計算效率。

圖5 避撞方向選擇步驟流程圖Fig.5 Flowchart step for sense selection

表1 無人機的假設參數Table 1 Hypothetical parameters of UAVs

參數探測距離/km預警范圍/m速度/(m·s-1)Δt/sA/radB/rad數值1.2100301-0.6120.612

3.1 復雜多機垂直平面相遇場景

在本場景中，UAV1與UAV6有相撞威脅，UAV2與UAV7有相撞威脅，UAV3與UAV8有相撞威脅。按照本文提出的避撞策略，UAV1、UAV7、UAV8先后成為關鍵節點，避撞的方向選擇與魯棒性最小原則相一致，整個避撞過程如圖6 所示，其中Tr1～Tr9分別代表UAV1～UAV9的飛行軌跡。在第1次的沖突中，UAV1與UAV6觸發了TA事件，在該時刻防撞系統檢測到UAV1面臨的威脅有2個，分別是UAV6和UAV9，UAV6只有1個威脅UAV1，因此此時選擇UAV1作為關鍵節點進行避撞處理，再按照魯棒性最小原則選擇下降方向進行避撞。第2次沖突的無人機對為UAV2與UAV7，此時UAV7面臨3個威脅，分別是UAV7、UAV4、UAV5，而UAV2只有UAV7一個威脅，因此選擇UAV7作為關鍵節點，該場景下無人機下降的方向符合魯棒性最小原則的方向，此時可以保證整體狀態安全性最高。同理在第3次沖突中，UAV3和UAV8觸發了TA事件，UAV8面臨的威脅為UAV3和UAV5，威脅個數為2，而UAV3只有UAV8威脅，因此選擇UAV8作為關鍵節點進行避撞，并且選擇上升的方向能保證魯棒性最小。

圖7描述的是在每一對存在沖突的無人機之間的相對距離，圖中展現的是UAV2與UAV7，UAV3與UAV8，UAV1與UAV6之間的相對距離(分別用d27、d38和d16表示)隨時間的變化情況。從圖7中可以發現在整個避撞過程中，無人機之間的最小垂直面相對距離為39.24 m，滿足無人機的安全距離限制。由于算法中實施的是單機改變方向的形式，在無人機未達到預設避撞高度時，無人機相對距離會略有縮小，但是能保證一定不會相撞，因為在預計的碰撞時刻無人機已經飛行至安全高度，所以雖然在避撞過程中可能會有接近的趨勢，但在隨后的飛行路徑中無人機能夠保持相對安全的相對距離。

圖8描述的是在避撞過程中的網絡連接，連線表示無人機之間存在的潛在威脅，其中連線的方式與構建網絡的邏輯相同，節點之間存在關聯不僅和節點之間的相對距離有關，同時與節點之間的相對速度有關。通過網絡算法可以識別關鍵節點，然后根據網絡屬性選擇最合適的避撞方向。

圖6 無人機群垂直平面避撞場景Fig.6 Scenario of UAV collision avoidance on vertical plane

圖7 場景1下無人機之間的相對距離Fig.7 Relevant distance of UAVs in scenario 1

圖8 場景1避撞過程中的網絡連接Fig.8 Network of collision process in scenario 1

3.2 復雜多機無規則集群場景

為了檢驗本文提出算法的可行性，進行仿真實驗得到考慮了包含9架無人機的人為設計的場景下,由該算法自動產生的避撞效果，如圖9所示。這個場景具備3個特點：① 場景相對復雜；② 多米諾效應；③ 同時考慮到了短時間內多次威脅的情況。

解決的策略就是通過分析在場景內各無人機的被威脅程度選擇執行避撞過程的無人機，然后再根據魯棒性最小原則選擇避撞的方向。

在該場景中，每一架無人機都在以直線的方式按初始方向進行巡航。在仿真的初始化階段為每一架無人機的初始位置和初始速度賦值。在有撞擊危險的區域，無人機利用本文提出的算法對該場景生成解決方案進行避撞。在局部空間內，無人機通過廣播的形式告知防撞系統實時的空域狀態，所有無人機的信息都能通過實時有效的通信設施進行狀態的記錄與更新，通過避撞系統為所有的無人機給出避撞方案。

表2總結了該場景下的無人機初始位置和飛行角度。在本場景中，第1次出現的TA是UAV1和UAV4觸發的。經過避撞系統分析后發現UAV1除了與UAV4即將發生碰撞外，還有潛在的和UAV2發生碰撞的可能，因此第1次發生TA事件時系統選擇了UAV1作為關鍵節點進行避撞方向的選擇，此時UAV1選擇了向下進行避撞。隨著仿真步長推進，系統檢測到在下一個階段在上UAV1與UAV2觸發了TA事件，由于UAV1已經在上一個階段成為了關鍵節點，因此在本次沖突中UAV2的潛在威脅雖然只有UAV2與UAV1之間的沖突，但是由于UAV1已經成為了一次關鍵節點，在這種情況下UAV2被系統選為關鍵節點，并為其分配了向上避撞的策略，這樣使得在原本將要撞擊的時刻，系統糾正了無人機航線后使得引起沖突的這幾架無人機形成分散規避撞擊的態勢，這可以解釋在這時該區域內的網絡魯棒性實現了最小化，直觀映像就是3架無人機散開了而并沒有出現交叉航線等會造成多米諾效應的后果。

圖9 無人機群隨機位置避撞場景Fig.9 Scenario of UAV collision avoidance at arbitrary locations

表2 無人機群的初始狀態Table 2 Original states of UAVs

無人機序號初始位置/(m,m,m)初始水平角/rad初始垂直角/radUAV1(0,700,700)-0.785 0-0.034 9UAV2(70,121,652)0.1.046 70.0UAV3(-56,325,736)-0.296 60.0.020 9UAV4(3,723,700)-0.348 9-0.016 9UAV5(-56,112,700)0.0.296 60.0

第3個出現連續TA事件觸發情況的是UAV1、UAV3和UAV5之間。下一個TA事件觸發是由UAV1和UAV3引起的，同理在這種情況下UAV3遇到的威脅和UAV1一樣多，但是UAV3之前不是關鍵節點，因此在這一次的關鍵節點選擇中UAV3成為了關鍵節點，并被系統分配了向上避撞的策略。緊接著UAV5檢測到即將與UAV1發生撞擊，而此時UAV1正處于避撞過程中，關鍵節點選擇優先級不如UAV5高，系統同時檢測到此時在UAV5未來的上空有正在執行避撞過程的UAV3，因此此時UAV5選擇向上避撞的優先級不如向下避撞的方向選擇優先級高，所以此時UAV5選擇了向下避撞的策略。這一次的連續TA事件觸發的情況和第1次有所不同，同時涉及到了關鍵節點的選擇時間，成為關鍵節點之后的節點在下一次評價是否成為關鍵節點時優先級會降低。

由于在算法的設計階段已經考慮到了連續TA事件觸發的情況，因此按照既定的關鍵節點選擇原則和避撞方向選擇原則能夠在這種連續TA事件觸發的情況下由防撞系統綜合分析態勢為每一架無人機分配有利于空域全局發展的安全性 較強的避撞策略。表3總結了UAV1和UAV2的路徑。

圖10描述的是在每一對存在沖突的無人機對的相對距離，圖中展現的分別是UAV1與UAV4、UAV1與UAV3、UAV1與UAV2、UAV1與UAV5之間的相對距離(分別用d14、d13、d12、d15表示)隨時間的變化。從該圖中可以發現在整個避撞過程中，無人機之間的最小相對距離為35.86 m，滿足無人機的安全距離限制。由于算法中實施的是單機改變方向的形式，在飛機未達到預設避撞高度時，無人機相對高度會在一小段區間內小于ALIM，所以雖然在避撞過程中可能會有接近的趨勢，在隨后的飛行路徑中無人機能夠保持相對安全的相對距離。

表3 UAV1和UAV2的路徑Table 3 Route of UAV1 and UAV2

圖11描述的是場景2避撞過程中的網絡連接，與圖8相同，網絡展現的拓撲形態描述了該場景此時的無人機之間的受威脅情況。

圖10 場景2下無人機之間的相對距離Fig.10 Relevant distance of UAVs in scenario 2

圖11 場景2避撞過程中的網絡連接Fig.11 Network of collision process in scenario 2

3.3 結果分析

由于在算法的設計階段已經考慮到了連續TA事件觸發的情況，因此按照既定的關鍵節點選擇原則和避撞方向選擇原則能夠在這種連續TA事件觸發的情況下由防撞系統綜合分析態勢，為每一架無人機分配有利于空域全局發展的安全性較強的避撞策略。

為了比較本文提出算法的優越性，將基于復雜網絡避撞算法和隨機選擇方向避撞算法做比較，表4對比了使用基于復雜網絡的避撞算法和隨機選擇方向避撞算法的Q值，也就是探測到威脅的原撞擊時刻的安全性。表4中展示了不同空域無人機密集度情況下(18架、32架、50架、72架、 100架)的Q值結果，其中Q值為30次仿真實驗結果的平均值。在不同的無人機密度的情況下基于復雜網絡避撞算法的Q值始終比隨機選擇方向避撞算法要小，意味著基于復雜網絡避撞算法能夠使得在探測到威脅的原撞擊時刻的空域無人機群的安全性可以達到最大。同時隨著密度的增加效果并沒有明顯減退，表明算法本身的穩定性很好，適用于大規模無人機群的避撞。

表5為復雜網絡算法與其他算法的計算效率比較。為了驗證算法的可適用性，本文用計算時間消耗作為衡量本防撞算法在不同無人機密度下的效果，并將其與其他算法進行比較，用2個經典的被驗證對于高密度環境有效的SGTA(Satisficing Game Theory-based Algorithm)和RIPNA(Reactive Inverse PN Algorithm)作為比較。如表5所示，低密度(20架無人機)、中密度(40架無人機)以及高密度(60架無人機)條件下的平均計算時間(基于100次隨機場景仿真測試)隨著空域無人機密度的增加不會呈現指數增長的形式，并且在不同密度下計算效率與其他算法相比有顯著提升。算法的可適用性是可以保障的，因為即使在高密度無人機場景下仍然能在相對合理的時間范圍內計算出沖突解決方案。

表4 2種算法的Q值比較Table 4 Comparison of Q-value of two algorithm

表5 不同無人機密度下的計算時間消耗Table 5 Time consumption in different UAV densities

4 總 結

提出了在局部空域內的無人機群的基于復雜網絡防撞算法，該算法通過復雜網絡理論將無人機的軌跡在全局范圍內盡可能迅速地進行同步修改以達到避撞的效果。

進行了2個經典場景的仿真實驗和大規模無人機群的仿真實驗。通過2個經典無人機相遇場景下的仿真實驗可以表明基于復雜網絡的無人機群避撞算法是可行有效的，大規模無人機群的仿真實驗表明對于不同規模的威脅密度都有很好的效果。

實驗表明算法給出的避撞策略能使得原本受威脅的無人機群的安全性達到最高，從安全性的意義上看這使得無人機群的安全性和魯棒性增強了。通過大規模無人機群的仿真驗證了算法的可適用性，時間效率較其他經典算法有顯著提升。未來的研究將會集中在以下方面：

1) 運用適合的啟發性算法提高算法的執行效率和計算速度。

2) 對無人機群的安全性指標做更加全面的研究，將其融入現有防撞系統以提升系統給無人機群帶來的安全性。

3) 考慮更加復雜的其他擾動的情況(比如強風等)以應對更加密集復雜的情況。

4) 將無人機整合到通用航空在非隔離空域內運行。