雙層優化的多無人機合作式沖突探測與解脫

付其喜，梁曉龍，張佳強，侯岳奇

(1.陜西省電子信息系統綜合集成重點實驗室(空軍工程大學),西安 710051; 2.中國人民解放軍94582部隊，河南 駐馬店 463200)

無人機(unmanned aerial vehicle，UAV)在基礎設施監測、貨物運輸、精準農業和搜索營救等方面得到了廣泛應用[1].隨著應用的不斷拓展，無人機在非隔離空域中運行的需求日益增加[2].無人機在非隔離空域中一旦發生空中相撞事故將釀成災難性的后果，所以沖突解脫問題成為亟待研究的重點[3].

無人機的短期沖突解脫在未來的無人機交通管理系統(unmanned aircraft systems traffic management,UTM)中具有重要地位.文獻[4]提出了導航函數法，既考慮了安全間隔又兼顧了預先規劃的航路點，但是會產生過多額外的飛行距離.文獻[5-9]提出并完善了一種雙向的分布式優化沖突解脫算法.它的基本思想是沖突雙方在解脫過程中處于平等的地位，共同負責完成沖突解脫機動.文獻[10]提出了一種選擇性速度障礙法，在速度障礙法中借鑒了有人機的目視飛行規則.該方法能夠實現有人機/無人機空域飛行規則的兼容，但由于在某些空中態勢下沖突雙方只有一方負責機動，所以容易產生兜圈的情況，造成了額外的解脫機動消耗.文獻[11]提出了一種將集中式優化和雙向沖突解脫結合的方法.文獻[12-13]拓展和改進了改變速度策略解脫模型，在沖突解脫過程中將非線性航跡考慮在內，并可以通過線性方程來完成解脫方案求解.但方法采用集中式優化，無人機通常采用分布式在線沖突探測與解脫.

本文在無人機雙向分布式優化的基礎上，提出了一種雙層優化的合作式分布沖突解脫的方法.首先分析了無人機的沖突解脫模型，提出了一種基于采樣的沖突探測算法，然后考慮了無人機的運動約束條件(運動約束包括飛行包線約束、轉彎角度約束和角速度約束等)及無人機的機動消耗，針對多無人機沖突解脫提出了一種雙層優化的沖突解脫算法與對應求解過程.最后運用蒙特卡洛法驗證了運用雙層優化算法進行沖突解脫的安全性.仿真結果表明，該方法能夠實現多無人機的雙向解脫機動和分布式優化，在保證沖突解脫安全性的基礎上減少了解脫機動消耗.

1 沖突解脫模型

1.1 無人機幾何模型

Dsi(pi,ri),i∈N為無人機Ai在二維空間的保護區，即

Dsi(pi,ri)={p‖px-xi,py-yi‖

式中：i為無人機編號;pi=(xi,yi)為Ai的坐標;N為無人機的數量;ri為Ai保護區半徑.

本文采用的無人機運動方程為：

0<φi(t)<2π.

1.2 沖突解脫幾何關系

本文通過建立局部坐標系來分析無人機的沖突關系，如圖1(a)所示，以Aj的當前位置為原點建立局部坐標系.則Ai在t=0時的坐標為

Pi(0)=(xi(0)-xj(0),yi(0)-yj(0)).

假設Ai是靜止的，則Aj相對于Ai的速度為

圖1 兩機速度障礙示意

為了分析無人機位移之間的關系，本文根據速度、位移與時間的關系將速度坐標系轉換成位移坐標系，如圖1(b)所示.Aj與Ai在τ內的相對位移為Lji=Lj-Li，其中Lj、Li分別為Aj與Ai在τ內的位移，Lj、Li在線規劃過程中視為直線.Lji在Aj與Ai進行解脫機動后改變為L′ji，而L′ji應位于Dij之外.

2 沖突探測

2.1 無人機態勢

圖2中陰影區域為無人機在[0～τ]時間內的可達區域.臨近無人機在[0～τ]時間內存在3種態勢.圖2(a)為兩機處于安全態勢，在前瞻時間τ內不會發生沖突，圖2(b)為兩機已經有沖突存在，圖2(c)為兩機在前瞻時間τ內若進行不合適的機動就會存在沖突的可能.本文將圖2(b)、圖2(c)分別定義為既有沖突與潛在沖突.在多無人機的沖突解脫過程中，若只考慮既有沖突，則無人機在進行解脫機動時仍會與其他存在潛在沖突的無人機發生沖突，因此本文將潛在沖突與既有沖突均視為存在沖突危險，用crij表示為

為了避免誘發沖突的出現，本文將既有沖突約束與潛在沖突約束視為同一類型約束，這樣能夠保證多無人機沖突問題在最大范圍內求解.

2.2 沖突探測算法

沖突探測算法一般只考慮既有沖突[15-16]，雙層優化算法根據無人機狀態，通過采樣進行沖突探測.首先基于位移矢量Lji與前瞻時間τ在無人機的飛行路徑上進行預測采樣，再根據采樣值及無人機位置構建空間區域，最后判斷被檢測無人機與所構建的空間區域的關系即能進行沖突探測.

二維空間內無人機沖突檢測步驟如下.

Step1根據無人機Ai與Aj當前的狀態以及它們在前瞻時間τ內可機動的角度或速度范圍采樣在τ時刻相對位移Lji到達的終點散布區域，如圖3所示的藍色散布點.

Step2根據無人機Ai與Aj的初始速度和運動方向獲得Aj的初始相對速度vji.得到vji與正向X坐標軸之間的夾角σji，將坐標系XOY旋轉σji.所有采樣點的坐標點在新的坐標系中關于X軸對稱.得到采樣點集的極值xmax、xmin、ymax、ymin.根據極值點構建一個包含所有終點的矩形區域，將其定義為終點區域，如圖3中的黑色矩形框包圍的區域.

圖2 臨近無人機的3種態勢

圖3 沖突探測示意

Step5產生各類區域后算法采用分區域的方法檢測沖突：首先檢查Ai的坐標是否在終點影響區域中，然后檢查Ai的位置是否在飛行過程影響區域中.在檢查飛行過程影響區域時首先檢查Ai的坐標點是否在由終點影響區域邊界點EA與EB到安全區域圓的切線的交點IAB與EA和EB構成的三角形內，如果在三角形區域中，需要考慮Ai在綠色非威脅區域內的誤檢測情況.

3 沖突解脫約束條件

3.1 解脫機動的約束條件

如沖突解脫幾何關系所述，L′ji在[0～τ]時間內應位于Dij之外，將其歸結為兩個約束條件，即終點約束與切線約束.Ai與Aj在t時刻的距離為

dij(t,φi,φj)=‖Pi(0)-vjit‖,

則無人機在τ的終點約束為

式中：kji為L′ji的斜率;Pix、Piy為Pi(0)的坐標.其中kji的表達式為

式中:kji為周期函數，其定義域為[-π/2+kπ,π/2+kπ],k∈Z;vji的航向范圍為H1=[-π/2,π/2]和H2=[π/2,3π/2]，這是kji的兩個不連續的周期.vji航向的可行區域如圖4所示.圖4(a)表示的是可行區域的第1種情況，兩個可行子區域分別位于kji的兩個周期內.圖4(b)表示的是可行區域的第2種情況.本文采用旋轉局部坐標系的方法將情況1轉變為情況2，如圖4(b)所示，旋轉之后P′ix=0且P′iy>0.

圖4 vji航向的可行區域

3.2 目標函數

將由于機動導致的無人機額外飛行距離作為目標函數，記為

圖5 沖突解脫機動過程

3)Ai返回原始路徑.額外飛行距離為

式中:α為無人機的返回路徑與偏離距離的比例系數;β為無人機的返回路徑在原始路徑上的投影PfPr與偏離距離的比例系數;α、β均為定值.

4 雙層優化多無人機沖突解脫

集中式優化沖突解脫在無人機數量較少時可以取得理想的結果.隨著無人機數量的增多，集中式優化沖突解脫難以保證所有無人機的沖突解脫.本文采用分群的思想[17]，將多無人機沖突分解為若干無人機沖突群進行分布式沖突解脫.

由于目前能夠快速找到局部最優解的算法軟件包(如SQP)的計算速度和精度與初始解的好壞有關，所以本文算法采用雙層優化的方法獲得解脫方案.先采用隨機并行梯度下降法(stochastic parallel gradient descent, SPGD)[18]來搜索無人機的初始可行解以得到沖突解脫的可行解區域，然后在可行解區域的基礎之上運用序列二次規劃(SQP)的方法獲得最優解.

4.1 產生無人機沖突群

運用圖論的方法來對多無人機沖突問題進行沖突關系劃分.相關無人機的沖突關系用約束圖G(t)=(V,E(t))來表示，如圖6(b)所示，其中V={1,…,N}為圖的頂點集，每一個頂點表示一架無人機.E(t)={(j,i)|cij=1}為表示沖突關系的圖的對應邊集合.無人機之間沖突關系隨時間改變時G(t)也相應改變.無人機之間的沖突矩陣CM可由G(t)的鄰接矩陣得到：

CM={cm(i,j)=g(φi,φj)ifeij(φi)∈E(t),

cm(i,j)=0 else|i,j∈n}.

圖6 8機沖突構型

如圖6(b)所示，一些無人機之間沒有沖突關系.因此，本文提出根據無人機之間的沖突關系將其聚類為若干沖突群，每個沖突群組成一個連通子圖.這樣空域內的無人機被拆分為若干沖突群，而多無人機沖突解脫問題也就被分解為在每個沖突群內搜索可行的解脫方案，因此可以大大降低算法的復雜度.

4.2 SPGD求解可行區域

產生初始解的隨機并行梯度下降算法是一種迭代尋優算法，其流程如圖7所示.

圖7 隨機并行梯度下降法流程

引理1給定一個由nl個無人機構成的沖突簇(nl>2)，在局部單調空間中存在能夠保證沖突簇中無人機安全間隔可行解區域的前提下，應用SPGD算法求解初始可行解可以保證收斂到該可行區域.

因此，在統計意義上，隨機并行梯度下降方法能夠找到確保多個無人機安全間隔的初始可行解.

4.3 搜索最優解

本文已經討論了解脫機動航向的可行解區域的產生，在此基礎上進一步求解機動航向的最優解.基于航向調整的沖突解脫問題是一個非線性優化問題，采用序列二次規劃來求解最優解.對于第l個沖突群，其優化目標函數為：

s.t.φi=φi(0),vi=vi(0),xi=xi(0),yi=yi(0),

由于每架無人機機動航向的可行區域分為兩個子區域，所以對于n架無人機，需要搜索2n個子空間.為保證算法的實時性，當涉及無人機數量較多時，將優化目標降低為搜索若干個子空間內的局部最優解.

4.4 算法對比驗證分析

為驗證SPGD算法的有效性，本文設計了多無人機飛行的沖突場景，在不同規模下分別利用SPGD與遺傳算法(GA)和典型的非線性優化求解器(Snopt)進行1 000次沖突解脫解算，并收集了不同數量無人機(2～21)涉及沖突時的算法平均求解時間，將SPGD與遺傳算法和Snopt的平均計算時間進行比較，結果如圖8所示.

圖8 不同算法對比

由圖8可以看出，SPGD明顯優于Snopt和遺傳算法，即使當涉及沖突的無人機數量達到21時，SPGD的求解時間也沒有超過0.5 s，能夠滿足在線求解需要.當涉及沖突的無人機數量小于14時，Snopt的求解時間不超過1 s，但與SPGD相比，明顯時間復雜度更高.而遺傳算法在求解中明顯效率很低，不能滿足實時性的要求.

5 仿真分析

圖9(a)顯示了8機相同速度相遇時的情況，共同在(0 km,0 km)處遭遇.無人機的速度為40 m/s，復合保護區半徑為320 m.圖9(b)顯示了8架無人機在解脫過程中任意時刻與它機的最小間隔.仿真結果表明8架無人機成功解脫，沒有發生沖突，并在解脫完成以后返回到原始路徑.

圖10比較了雙層優化法與選擇性速度障礙法(selective velocity obstacle,SVO)在進行多無人機不同速度解脫中的性能.從圖10中可以看出，SVO進行解脫時無人機在某些態勢下，只有沖突中的一方負責進行解脫機動，這可能導致無人機出現兜圈的情況.而且某些情況SVO會造成無人機進行不可能的機動，比如圖10(b)中的無人機A3.圖11對兩種方法偏離計劃位置的距離進行了比較，在初始階段，由于采用雙向解脫方案，雙層優化法機動更快，能夠首先完成解脫機動.解脫完成之后，雙層優化法也能夠產生更少的額外飛行距離.無人機之間的最小間隔如圖12所示，結果表明雙層優化法能夠保證無人機在沖突解脫時的安全間隔.

圖9 8機相同速度

圖10 9機不同速度

圖11 偏離計劃位置的距離

圖12 雙層優化法無人機之間的最小距離

Fig.12 Minimum distance between UAVs by two-layer optimization

6 蒙特卡洛法沖突概率分析

在上述仿真分析中，多無人機的沖突全部成功解脫.但是，由于無人機在實際運行過程中環境相當復雜，上述的仿真只是基于位置、速度和航向均固定的沖突態勢，不能保證算法的普適性.因此，通過蒙特卡洛法產生大量隨機的無人機沖突來得到多無人機的沖突概率.與上述類似，本文依然基于小型無人機來進行仿真.

由于現實中的實驗具有高風險、耗費高和耗時長的特性，所以本文采用簡單、經濟、實用的蒙特卡洛法來產生無人機的沖突概率.根據無人機的等效安全水平原則[21]，無人機沖突解脫算法的成功率應為100%.

6.1 蒙特卡洛仿真條件

為了評價本文算法的性能，需要設置一些蒙特卡洛仿真的參數.算法的性能可以通過沖突概率Pvio來評價.

式中:Nvio、NMC分別為蒙特卡洛仿真過程中的沖突個數和采樣個數;Pvio將隨著NMC波動，但隨著NMC逐漸增大，Pvio將逐漸趨于一個穩定值.

蒙特卡洛仿真條件如下：

圖13 4機隨機態勢

2)雙層優化法中標準無人機解脫開始距離為Davo=τ×vi(τ=25 s).本文在沖突概率分析中考慮解脫開始距離小于Davo的情況，并定義比例系數ρavo為

式中D′avo為仿真中的無人機沖突解脫開始距離.如表1所示，蒙特卡洛仿真采用3種仿真類型：MC1、MC2、MC3. MC1中，ρavo∈[0,0]，即不使用沖突解脫算法. MC2中，ρavo∈[0,1]，即所有無人機的解脫開始距離D′avo小于標準解脫開始距離Davo.MC3中，ρavo∈[1,1]，即所有無人機的解脫開始距離D′avo等于標準解脫開始距離Davo.為了避免無人機的初始間隔對沖突概率的影響，仿真中t=0時無人機的間隔均大于D′avo.

表1 蒙特卡洛仿真參數設置

3)由于小型無人機的規定速度為小于45 m/s，蒙特卡洛仿真中隨機產生的無人機初始速度vi∈(0 m/s,45 m/s)，且整個仿真過程中無人機的速度保持不變(見表1).

4)為了產生無人機的所有可能相遇態勢(對頭相遇、交叉相遇和追及相遇)，仿真產生的無人機初始航向范圍為(0,2π]，且在沖突解脫開始之前航向保持不變(見表1).

仿真過程中，首先在正方形區域Asqu中產生N(N=2,3,4,5)架無人機，并根據仿真類型和表1中的參數范圍隨機產生無人機的位置、速度、航向和比例系數ρavo.若無人機在飛行過程中探測到了沖突存在則無人機運用雙層優化法進行沖突解脫，否則無人機航向保持不變.

6.2 結果分析

蒙特卡洛仿真采樣次數為106次.仿真結果中的Pvio與采樣次數的關系如圖14所示，無人機不同數量下的沖突概率如圖15所示.由圖14、15中可以看出，MC3的沖突概率在2～5機時的沖突概率均為0，符合等效安全水平的要求.MC2中雖然沖突概率比不使用算法的情況下大幅下降，但不能夠解脫一切沖突，不滿足等效安全水平的要求，解脫失敗的原因在于沖突解脫的距離過短.

圖14 不同仿真類型的沖突概率

圖15 沖突概率對比

通過分析可以得出，在標準的沖突解脫開始距離下雙層優化算法的解脫成功率能夠達到100%，滿足無人機等效安全水平的要求.

7 結 論

1)算法能夠解決多無人機的沖突解脫問題，減少解脫代價，滿足在線規劃需要并降低了對空中交通的影響.可滿足無人機等效安全水平的要求，在解脫開始距離Davo=τ×vi(τ=25 s)的情況下能夠實現100%的沖突解脫.

2)分析了沖突解脫的幾何模型和約束條件，重點研究了沖突幾何的終點約束、切線約束和kji的周期性特點，并同時考慮了無人機的既有沖突與潛在沖突，有效避免了誘發沖突，保證沖突解脫問題在最大范圍內求解.

3)提出了一種雙層優化算法，首先通過隨機并行梯度下降法求得沖突群的可行解區域，再用序列二次規劃進行最優解的求解，能夠在保證成功解脫的情況下進行航向機動的優化. 通過蒙特卡洛法設置不同的仿真條件比較驗證了雙層優化算法進行多無人機沖突探測與解脫的安全性.