基于復(fù)雜網(wǎng)絡(luò)的無(wú)人機(jī)飛行沖突解脫算法

黃洋，湯俊，老松楊

國(guó)防科技大學(xué) 系統(tǒng)工程學(xué)院，長(zhǎng)沙 410000

近年來(lái)無(wú)人機(jī)系統(tǒng)被廣泛運(yùn)用到戰(zhàn)爭(zhēng)環(huán)境和城市環(huán)境中。由于執(zhí)行任務(wù)環(huán)境和任務(wù)本身逐漸變得復(fù)雜，多無(wú)人機(jī)的集群作業(yè)變得越來(lái)越有研究?jī)r(jià)值。無(wú)人機(jī)之間能夠?qū)崿F(xiàn)自主防撞是無(wú)人機(jī)集群控制的前提，包括無(wú)人機(jī)群內(nèi)部的防撞和無(wú)人機(jī)群之間的防撞，解決無(wú)人機(jī)群防撞問題對(duì)當(dāng)前無(wú)人機(jī)集群作業(yè)具有重大意義。

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

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

1 模型構(gòu)建

本節(jié)描述的是無(wú)人機(jī)集群的模型構(gòu)建。首先，對(duì)沖突進(jìn)行檢測(cè)，定義了無(wú)人機(jī)的屬性用以刻畫無(wú)人機(jī)的各種狀態(tài)，構(gòu)建了無(wú)人機(jī)的鄰域集以及沖突發(fā)生的條件。然后，說(shuō)明了關(guān)鍵節(jié)點(diǎn)選擇以及避撞方向選擇策略，其中對(duì)一種意外入侵的特殊情況進(jìn)行說(shuō)明并提供解決方案。最后，對(duì)無(wú)人機(jī)的安全性定義了安全性分析指標(biāo)。

1.1 沖突檢測(cè)

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

無(wú)人機(jī)有6種狀態(tài)，分別是：狀態(tài)1，正常的巡航狀態(tài)；狀態(tài)2，由防撞系統(tǒng)檢測(cè)到剛好遇到威脅的狀態(tài)；狀態(tài)3，防撞系統(tǒng)檢測(cè)到有威脅后開始執(zhí)行避撞程序正在改變的軌跡上飛行的過程；狀態(tài)4，在執(zhí)行避撞的時(shí)間達(dá)到預(yù)計(jì)的位置時(shí)，按照原有巡航狀態(tài)進(jìn)行飛行的過程；狀態(tài)5，在狀態(tài)4結(jié)束后開始按照與防撞軌跡相反的角度進(jìn)行返航回到原有軌道上；狀態(tài)6，在返航過程結(jié)束后按照原有巡航的角度進(jìn)行巡航。

為了檢測(cè)沖突的目的，無(wú)人機(jī)在笛卡爾系統(tǒng)中被識(shí)別。每個(gè)無(wú)人機(jī)在相應(yīng)時(shí)刻的位置表示為

(1)

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

(2)

對(duì)無(wú)人機(jī)進(jìn)行鄰域集的構(gòu)建，無(wú)人機(jī)遇到威脅的坐標(biāo)設(shè)為(x,y,z)，最小的鄰域距離為lmin，最大的鄰域距離為lmax，最低飛行高度為hmin，則無(wú)人機(jī)在飛行中的鄰域點(diǎn)s的集合為

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

(3)

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

定義最大偏航角為Φmax，其到達(dá)目標(biāo)的后向鄰域?yàn)锳(i)，預(yù)計(jì)的到達(dá)角度為θgoal。

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

(4)

(5)

(6)

(7)

(8)

(9)

這表示左右兩個(gè)條件只要一個(gè)被滿足，TA事件即被觸發(fā)。用T1來(lái)表示第1對(duì)無(wú)人機(jī)觸發(fā)TA警報(bào)的時(shí)刻。從那一刻起，構(gòu)建一個(gè)網(wǎng)絡(luò)，每個(gè)無(wú)人機(jī)都被表示為一個(gè)節(jié)點(diǎn)。如果一對(duì)節(jié)點(diǎn)發(fā)生沖突，則節(jié)點(diǎn)將建立連接。在時(shí)刻T1，系統(tǒng)中的所有節(jié)點(diǎn)將檢查無(wú)人機(jī)是否正在接近，如果無(wú)人機(jī)正在彼此接近，則連接兩個(gè)節(jié)點(diǎn)，判斷條件為

(10)

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

圖1 無(wú)人機(jī)防撞示意圖Fig.1 Sketch of collision avoidance of UAVs

1.2 關(guān)鍵節(jié)點(diǎn)選擇策略

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

圖2 無(wú)人機(jī)群復(fù)雜網(wǎng)絡(luò)概念圖Fig.2 Conceptual framework of complex network for UAVs

為了使網(wǎng)絡(luò)更加接近于真實(shí)場(chǎng)景，只使用邊數(shù)是不夠的。邊應(yīng)該有額外的屬性來(lái)監(jiān)視無(wú)人機(jī)的真實(shí)關(guān)系。該關(guān)系包含無(wú)人機(jī)之間的相對(duì)距離和相對(duì)速度。一對(duì)無(wú)人機(jī)接近對(duì)方的速度越快，就越危險(xiǎn)。所以每條邊的權(quán)重取決于無(wú)人機(jī)之間的相對(duì)距離和相對(duì)速度，從而定義無(wú)人機(jī)i與無(wú)人機(jī)j之間的邊緣權(quán)重ωij為

(11)

式中：υij為矢量方向的相對(duì)速度；dij為無(wú)人機(jī)i和無(wú)人機(jī)j之間的距離。這就意味著2架無(wú)人機(jī)接近的速度越快，無(wú)人機(jī)之間的邊的權(quán)重就越大。關(guān)鍵節(jié)點(diǎn)選擇的公式為

(12)

計(jì)算每架無(wú)人機(jī)的邊緣權(quán)重之和，邊緣權(quán)重之和最大的節(jié)點(diǎn)被定義為關(guān)鍵節(jié)點(diǎn)。即選出使得邊緣權(quán)重之和最大的無(wú)人機(jī)序號(hào)ikey。

1.3 避撞方向選擇策略

在這個(gè)新沖突模型情況下，盡可能地降低魯棒性和完整性至關(guān)重要。將網(wǎng)絡(luò)的魯棒性定義為

(13)

(14)

式中：I為網(wǎng)絡(luò)中被剔除的節(jié)點(diǎn)數(shù)量；M為網(wǎng)絡(luò)子圖中最大的鏈接數(shù)量。

這個(gè)新模型的目標(biāo)是盡可能快地分解網(wǎng)絡(luò)。這意味著在關(guān)鍵節(jié)點(diǎn)被清除之后，網(wǎng)絡(luò)的魯棒性和網(wǎng)絡(luò)的組件數(shù)量應(yīng)該盡可能低。也意味著無(wú)人機(jī)相互離開，墜毀的風(fēng)險(xiǎn)越來(lái)越小。在仿真步驟中，新模型找出關(guān)鍵節(jié)點(diǎn)并評(píng)估連接的魯棒性或連接的組件數(shù)目。關(guān)鍵節(jié)點(diǎn)將選擇變化的航向，在下一個(gè)仿真步驟中形成一個(gè)新的網(wǎng)絡(luò)，新的模型將再次選擇關(guān)鍵節(jié)點(diǎn)。該模型將監(jiān)測(cè)多無(wú)人機(jī)系統(tǒng)，以確定是否發(fā)布TA警報(bào)，如果模型停止查找關(guān)鍵節(jié)點(diǎn)，多無(wú)人機(jī)系統(tǒng)將被認(rèn)為是安全的。

如圖3所示，該場(chǎng)景描述的是在一個(gè)特殊的垂直面碰撞空間內(nèi)的無(wú)人機(jī)關(guān)聯(lián)情況。每個(gè)節(jié)點(diǎn)代表不同的無(wú)人機(jī)，紅色節(jié)點(diǎn)和藍(lán)色節(jié)點(diǎn)分別表示2個(gè)飛行朝向的無(wú)人機(jī)群，虛線框表示系統(tǒng)認(rèn)為的藍(lán)色節(jié)點(diǎn)受威脅區(qū)域，在受威脅區(qū)域內(nèi)的紅色節(jié)點(diǎn)被認(rèn)為是對(duì)藍(lán)色節(jié)點(diǎn)產(chǎn)生威脅的節(jié)點(diǎn)。由于在該場(chǎng)景下，紅色節(jié)點(diǎn)的受威脅區(qū)域內(nèi)包含的藍(lán)色節(jié)點(diǎn)數(shù)最多為2個(gè)，而藍(lán)色節(jié)點(diǎn)的受威脅區(qū)域內(nèi)包含的紅色節(jié)點(diǎn)個(gè)數(shù)都至少是2個(gè)，因此在該場(chǎng)景下，按照?qǐng)D示順序先后由中間的藍(lán)色節(jié)點(diǎn)、左側(cè)藍(lán)色節(jié)點(diǎn)、右側(cè)藍(lán)色節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)，由魯棒性最小原則可得這些節(jié)點(diǎn)的避撞方向均為下降的方向。

圖3 查找關(guān)鍵節(jié)點(diǎn)的過程示意圖Fig.3 Sketch of process of locating key nodes

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

當(dāng)選擇向上飛時(shí)：

(15)

當(dāng)其方向不做改變時(shí)：

(16)

當(dāng)選擇向下飛時(shí)：

(17)

在最近接近點(diǎn)處關(guān)鍵節(jié)點(diǎn)對(duì)應(yīng)的無(wú)人機(jī)與入侵無(wú)人機(jī)m的豎直距離表示為

(18)

(19)

(20)

當(dāng)關(guān)鍵節(jié)點(diǎn)對(duì)應(yīng)的無(wú)人機(jī)在完成自己的方向計(jì)算之前就接收到入侵無(wú)人機(jī)m的方向選擇建議或者無(wú)人機(jī)i的優(yōu)先級(jí)比入侵無(wú)人機(jī)m低，則無(wú)人機(jī)的方向選擇按照如下公式進(jìn)行：

(21)

入侵無(wú)人機(jī)的RA方向選擇滿足

(22)

(23)

式中：

(24)

1.4 無(wú)人機(jī)的安全性分析

文獻(xiàn)[24]對(duì)沖突解脫的結(jié)果進(jìn)行了安全性驗(yàn)證。在本文中考慮某個(gè)時(shí)刻的無(wú)人機(jī)群的安全性，提出基于狀態(tài)的安全性指標(biāo)。按照Q統(tǒng)計(jì)的方法可以對(duì)無(wú)人機(jī)群進(jìn)行安全性分析。

(25)

式中：Xi表示第i架無(wú)人機(jī)撞毀的可能性，這里就用第i架無(wú)人機(jī)的魯棒性指標(biāo)Ri表示Xi；N代表無(wú)人機(jī)群的無(wú)人機(jī)數(shù)目。由于Q衡量的是某個(gè)時(shí)刻的安全性，因此每一架無(wú)人機(jī)的安全率的提高能夠提高無(wú)人機(jī)群的安全性。

2 關(guān)鍵步驟分析

本節(jié)描述的是無(wú)人機(jī)集群防撞的算法，本文將該算法分為步驟1和步驟2，分別對(duì)應(yīng)關(guān)鍵節(jié)點(diǎn)選擇步驟和避撞方向選擇步驟。2個(gè)步驟也分別對(duì)應(yīng)無(wú)人機(jī)防撞過程的2個(gè)階段，即防撞系統(tǒng)選取避撞的無(wú)人機(jī)序號(hào)和該無(wú)人機(jī)避撞的方向。

2.1 關(guān)鍵節(jié)點(diǎn)選擇步驟

圖4 關(guān)鍵節(jié)點(diǎn)選擇步驟流程圖Fig.4 Flowchart step for key node selection

關(guān)鍵節(jié)點(diǎn)選擇步驟解決了避撞策略的第1步，即選擇關(guān)鍵節(jié)點(diǎn)并由關(guān)鍵節(jié)點(diǎn)對(duì)應(yīng)的無(wú)人機(jī)繼續(xù)執(zhí)行方向選擇步驟提供的方向策略。關(guān)鍵節(jié)點(diǎn)選擇流程圖如圖4所示，對(duì)仿真整個(gè)過程和每一架無(wú)人機(jī)進(jìn)行檢測(cè)是否有TA事件觸發(fā)，一旦有TA事件觸發(fā)，對(duì)無(wú)人機(jī)群進(jìn)行網(wǎng)絡(luò)構(gòu)建，計(jì)算被包含無(wú)人機(jī)之間的相對(duì)速度和相對(duì)距離，然后通過計(jì)算受威脅程度值選擇出關(guān)鍵節(jié)點(diǎn)并執(zhí)行步驟2，在為關(guān)鍵節(jié)點(diǎn)選擇好避撞方向后，更新關(guān)鍵節(jié)點(diǎn)的狀態(tài)。步驟1不斷執(zhí)行，TA事件消除時(shí)進(jìn)入下一個(gè)循環(huán)，更新全局無(wú)人機(jī)的狀態(tài)。如果所有無(wú)人機(jī)到達(dá)安全區(qū)域，則步驟1終止。

2.2 避撞方向選擇步驟

步驟2是對(duì)無(wú)人機(jī)避撞方向選取策略的描述，當(dāng)防撞系統(tǒng)執(zhí)行到步驟2中，如圖5所示，首先會(huì)為關(guān)鍵節(jié)點(diǎn)構(gòu)建探測(cè)網(wǎng)絡(luò)從而對(duì)關(guān)鍵節(jié)點(diǎn)所處狀態(tài)進(jìn)行分析。由于組建探測(cè)網(wǎng)絡(luò)時(shí)是對(duì)一定范圍內(nèi)的空域進(jìn)行探測(cè)，所以分為單機(jī)入侵和多機(jī)入侵2種場(chǎng)景。如果探測(cè)網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的入侵機(jī)數(shù)為一架，若探測(cè)與關(guān)鍵節(jié)點(diǎn)的垂直高度差小于1/(2ALIM)，構(gòu)建全局分析網(wǎng)絡(luò),分別計(jì)算關(guān)鍵節(jié)點(diǎn)選擇上升和下降的全局魯棒性并選擇魯棒性小的方向；若入侵機(jī)與關(guān)鍵節(jié)點(diǎn)的垂直高度差大于1/(2ALIM)，則直接選擇垂直方向上遠(yuǎn)離入侵機(jī)的方向進(jìn)行避撞。如果探測(cè)到多機(jī)入侵，則考察入侵機(jī)群中與關(guān)鍵節(jié)點(diǎn)對(duì)應(yīng)無(wú)人機(jī)垂直方向高度的相對(duì)高度，若更多的無(wú)人機(jī)高于關(guān)鍵節(jié)點(diǎn)的高度，則關(guān)鍵節(jié)點(diǎn)選擇向下的方向進(jìn)行避撞；若低于關(guān)鍵節(jié)點(diǎn)的入侵無(wú)人機(jī)數(shù)量更多，則關(guān)鍵節(jié)點(diǎn)選擇向上的方向進(jìn)行避撞。

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

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

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

表1 無(wú)人機(jī)的假設(shè)參數(shù)Table 1 Hypothetical parameters of UAVs

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

3.1 復(fù)雜多機(jī)垂直平面相遇場(chǎng)景

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

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

圖8描述的是在避撞過程中的網(wǎng)絡(luò)連接，連線表示無(wú)人機(jī)之間存在的潛在威脅，其中連線的方式與構(gòu)建網(wǎng)絡(luò)的邏輯相同，節(jié)點(diǎn)之間存在關(guān)聯(lián)不僅和節(jié)點(diǎn)之間的相對(duì)距離有關(guān)，同時(shí)與節(jié)點(diǎn)之間的相對(duì)速度有關(guān)。通過網(wǎng)絡(luò)算法可以識(shí)別關(guān)鍵節(jié)點(diǎn)，然后根據(jù)網(wǎng)絡(luò)屬性選擇最合適的避撞方向。

圖6 無(wú)人機(jī)群垂直平面避撞場(chǎng)景Fig.6 Scenario of UAV collision avoidance on vertical plane

圖7 場(chǎng)景1下無(wú)人機(jī)之間的相對(duì)距離Fig.7 Relevant distance of UAVs in scenario 1

圖8 場(chǎng)景1避撞過程中的網(wǎng)絡(luò)連接Fig.8 Network of collision process in scenario 1

3.2 復(fù)雜多機(jī)無(wú)規(guī)則集群場(chǎng)景

為了檢驗(yàn)本文提出算法的可行性，進(jìn)行仿真實(shí)驗(yàn)得到考慮了包含9架無(wú)人機(jī)的人為設(shè)計(jì)的場(chǎng)景下,由該算法自動(dòng)產(chǎn)生的避撞效果，如圖9所示。這個(gè)場(chǎng)景具備3個(gè)特點(diǎn)：① 場(chǎng)景相對(duì)復(fù)雜；② 多米諾效應(yīng)；③ 同時(shí)考慮到了短時(shí)間內(nèi)多次威脅的情況。

解決的策略就是通過分析在場(chǎng)景內(nèi)各無(wú)人機(jī)的被威脅程度選擇執(zhí)行避撞過程的無(wú)人機(jī)，然后再根據(jù)魯棒性最小原則選擇避撞的方向。

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

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

圖9 無(wú)人機(jī)群隨機(jī)位置避撞場(chǎng)景Fig.9 Scenario of UAV collision avoidance at arbitrary locations

表2 無(wú)人機(jī)群的初始狀態(tài)Table 2 Original states of UAVs

無(wú)人機(jī)序號(hào)初始位置/(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個(gè)出現(xiàn)連續(xù)TA事件觸發(fā)情況的是UAV1、UAV3和UAV5之間。下一個(gè)TA事件觸發(fā)是由UAV1和UAV3引起的，同理在這種情況下UAV3遇到的威脅和UAV1一樣多，但是UAV3之前不是關(guān)鍵節(jié)點(diǎn)，因此在這一次的關(guān)鍵節(jié)點(diǎn)選擇中UAV3成為了關(guān)鍵節(jié)點(diǎn)，并被系統(tǒng)分配了向上避撞的策略。緊接著UAV5檢測(cè)到即將與UAV1發(fā)生撞擊，而此時(shí)UAV1正處于避撞過程中，關(guān)鍵節(jié)點(diǎn)選擇優(yōu)先級(jí)不如UAV5高，系統(tǒng)同時(shí)檢測(cè)到此時(shí)在UAV5未來(lái)的上空有正在執(zhí)行避撞過程的UAV3，因此此時(shí)UAV5選擇向上避撞的優(yōu)先級(jí)不如向下避撞的方向選擇優(yōu)先級(jí)高，所以此時(shí)UAV5選擇了向下避撞的策略。這一次的連續(xù)TA事件觸發(fā)的情況和第1次有所不同，同時(shí)涉及到了關(guān)鍵節(jié)點(diǎn)的選擇時(shí)間，成為關(guān)鍵節(jié)點(diǎn)之后的節(jié)點(diǎn)在下一次評(píng)價(jià)是否成為關(guān)鍵節(jié)點(diǎn)時(shí)優(yōu)先級(jí)會(huì)降低。

由于在算法的設(shè)計(jì)階段已經(jīng)考慮到了連續(xù)TA事件觸發(fā)的情況，因此按照既定的關(guān)鍵節(jié)點(diǎn)選擇原則和避撞方向選擇原則能夠在這種連續(xù)TA事件觸發(fā)的情況下由防撞系統(tǒng)綜合分析態(tài)勢(shì)為每一架無(wú)人機(jī)分配有利于空域全局發(fā)展的安全性 較強(qiáng)的避撞策略。表3總結(jié)了UAV1和UAV2的路徑。

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

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

圖11描述的是場(chǎng)景2避撞過程中的網(wǎng)絡(luò)連接，與圖8相同，網(wǎng)絡(luò)展現(xiàn)的拓?fù)湫螒B(tài)描述了該場(chǎng)景此時(shí)的無(wú)人機(jī)之間的受威脅情況。

圖10 場(chǎng)景2下無(wú)人機(jī)之間的相對(duì)距離Fig.10 Relevant distance of UAVs in scenario 2

圖11 場(chǎng)景2避撞過程中的網(wǎng)絡(luò)連接Fig.11 Network of collision process in scenario 2

3.3 結(jié)果分析

由于在算法的設(shè)計(jì)階段已經(jīng)考慮到了連續(xù)TA事件觸發(fā)的情況，因此按照既定的關(guān)鍵節(jié)點(diǎn)選擇原則和避撞方向選擇原則能夠在這種連續(xù)TA事件觸發(fā)的情況下由防撞系統(tǒng)綜合分析態(tài)勢(shì)，為每一架無(wú)人機(jī)分配有利于空域全局發(fā)展的安全性較強(qiáng)的避撞策略。

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

表5為復(fù)雜網(wǎng)絡(luò)算法與其他算法的計(jì)算效率比較。為了驗(yàn)證算法的可適用性，本文用計(jì)算時(shí)間消耗作為衡量本防撞算法在不同無(wú)人機(jī)密度下的效果，并將其與其他算法進(jìn)行比較，用2個(gè)經(jīng)典的被驗(yàn)證對(duì)于高密度環(huán)境有效的SGTA(Satisficing Game Theory-based Algorithm)和RIPNA(Reactive Inverse PN Algorithm)作為比較。如表5所示，低密度(20架無(wú)人機(jī))、中密度(40架無(wú)人機(jī))以及高密度(60架無(wú)人機(jī))條件下的平均計(jì)算時(shí)間(基于100次隨機(jī)場(chǎng)景仿真測(cè)試)隨著空域無(wú)人機(jī)密度的增加不會(huì)呈現(xiàn)指數(shù)增長(zhǎng)的形式，并且在不同密度下計(jì)算效率與其他算法相比有顯著提升。算法的可適用性是可以保障的，因?yàn)榧词乖诟呙芏葻o(wú)人機(jī)場(chǎng)景下仍然能在相對(duì)合理的時(shí)間范圍內(nèi)計(jì)算出沖突解決方案。

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

表5 不同無(wú)人機(jī)密度下的計(jì)算時(shí)間消耗Table 5 Time consumption in different UAV densities

4 總 結(jié)

提出了在局部空域內(nèi)的無(wú)人機(jī)群的基于復(fù)雜網(wǎng)絡(luò)防撞算法，該算法通過復(fù)雜網(wǎng)絡(luò)理論將無(wú)人機(jī)的軌跡在全局范圍內(nèi)盡可能迅速地進(jìn)行同步修改以達(dá)到避撞的效果。

進(jìn)行了2個(gè)經(jīng)典場(chǎng)景的仿真實(shí)驗(yàn)和大規(guī)模無(wú)人機(jī)群的仿真實(shí)驗(yàn)。通過2個(gè)經(jīng)典無(wú)人機(jī)相遇場(chǎng)景下的仿真實(shí)驗(yàn)可以表明基于復(fù)雜網(wǎng)絡(luò)的無(wú)人機(jī)群避撞算法是可行有效的，大規(guī)模無(wú)人機(jī)群的仿真實(shí)驗(yàn)表明對(duì)于不同規(guī)模的威脅密度都有很好的效果。

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

1) 運(yùn)用適合的啟發(fā)性算法提高算法的執(zhí)行效率和計(jì)算速度。

2) 對(duì)無(wú)人機(jī)群的安全性指標(biāo)做更加全面的研究，將其融入現(xiàn)有防撞系統(tǒng)以提升系統(tǒng)給無(wú)人機(jī)群帶來(lái)的安全性。

3) 考慮更加復(fù)雜的其他擾動(dòng)的情況(比如強(qiáng)風(fēng)等)以應(yīng)對(duì)更加密集復(fù)雜的情況。

4) 將無(wú)人機(jī)整合到通用航空在非隔離空域內(nèi)運(yùn)行。