錢曉鵬 張洪海 田 宇 王立超

(南京航空航天大學民航學院 南京 210016)

0 引 言

為應對無人機民用空域混合運行需要，當前國內(nèi)外有不少學者對無人機交通管理系統(tǒng)(UTM)的構建展開研究.NASA開發(fā)了無人機交通管理系統(tǒng)快速仿真平臺.作為無人機交通管理系統(tǒng)的核心技術，沖突探測與解脫算法是無人機在空域內(nèi)安全運行的保障，也是無人機走出隔離區(qū)、進入國家當前空域系統(tǒng)與其他航空器融合運行的必要前提.

當前國內(nèi)外對無人機沖突解脫技術有一定研究基礎.Klaus等[1]為了滿足小型無人機尺寸、重量、能源等限制因素，提出了一種適用于小型無人機(sUAS)的沖突 “感知與避讓”技術.Castillo等[2]針對不斷增長的無人機運行需求，在自由飛概念下提出了兩種基于agent合作的分布式?jīng)_突解脫算法：IPPCA算法以及MPCA算法.Schmitt等[3]提出了基于導航的三維沖突避讓算法，使用部分離散的方法減少計算復雜性，使方法更加貼近實際應用.Alonso等[4]將集中沖突解脫轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題，在滿足所有沖突解脫限制條件的基礎上，以調(diào)速或者調(diào)航向總和最小為目標求解，實現(xiàn)了沖突解脫過程的系統(tǒng)最優(yōu).周建等[5]將多Agent技術與啟發(fā)式算法結(jié)合，研究了基于分布式MAS框架的飛行沖突探測與解脫方法.王淵等[6]針對同一空域內(nèi)多無人機飛行沖突解脫問題，提出了一種基于改進人工蜂群算法的沖突解脫策略.

目前研究大多以實現(xiàn)無人機沖突的有效解脫以及系統(tǒng)的整體效率較優(yōu)為目標，并沒有考慮無人機實際運行過程中解脫的公平性、優(yōu)先級合理性問題，不夠符合實際需求.在低空環(huán)境下，無人機具有各自的任務特點，實際飛行沖突解脫過程中必然要將解脫是否符合優(yōu)先級關系以及解脫方案對每架無人機的公平性等因素考慮在內(nèi).為此，本文基于智能體(Agent)技術，將博弈論“核仁解”概念引入到?jīng)_突解脫協(xié)商機制中，研究考慮無人機沖突解脫公平性、優(yōu)先級等因素的沖突解脫方法.

1 低空沖突解脫智能協(xié)作機制

假設空域內(nèi)無人機均為智能體，所有無人機均能通過ADS-B獲取本機及周邊無人機狀態(tài)數(shù)據(jù)且能與上級Agent進行通信，見圖1.低空無人機系統(tǒng)是分布式人工智能系統(tǒng)(DAI)，無人機與其他無人機發(fā)生沖突進行解脫是一種動態(tài)協(xié)作任務求解問題.提出協(xié)作流程如下.

步驟1所有具有關聯(lián)沖突的飛行器形成一個沖突團體.

步驟2沖突團體內(nèi)飛行器將各自狀態(tài)、屬性數(shù)據(jù)上傳至上級Agent.

步驟3上級Agent依據(jù)協(xié)商策略形成沖突解脫方案.

步驟4方案下發(fā)至各飛行器并執(zhí)行.

圖1 低空無人機沖突解脫智能協(xié)作示意

2 沖突解脫“分支”模型

當無人機遇到?jīng)_突，通常會采取一系列機動動作將沖突化解.本文采用確定性采樣方法建立沖突解脫“分支”模型規(guī)劃無人機沖突解脫軌跡.無人機沖突解脫過程被分支為固定采樣周期t的M步，其每一步有N種機動策略選擇.沖突解脫基本模型見圖2.

圖2 沖突解脫“分支”模型

模型中，對于無人機i，其初始狀態(tài)記為X0=[P0,θ0,v0].其中：P0=(x0,y0)，為無人機初始坐標位置；θ0為無人機初始航向角；v0為初始速度.第m步的控制量為Um=[θm,vm]，θm，vm分別為無人機第m步的航向角和速度控制量.無人機經(jīng)過m步機動后位置Pm=(xm,ym)為

(1)

受無人機轉(zhuǎn)彎率及飛行速度、加速度約束為

(2)

式中：ωmax，αmax，vmin，vmax分別為無人機最大轉(zhuǎn)彎率、最大加速度、最小飛行速度，以及最大飛行速度.

3 基于“核仁解”的沖突協(xié)商求解策略

對于MAS動態(tài)協(xié)作任務求解，協(xié)商策略是保證協(xié)作能夠順利實現(xiàn)的關鍵.對于多無人機飛行沖突解脫問題，各無人機均具有利己性，偏向于進行對自己更加有利的機動動作，解脫方案應均衡各無人機解脫代價.對此本文引入合作博弈思想，提出基于“核仁解”的沖突協(xié)商求解策略[7].

對無人機沖突解脫過程中“核仁解”作出如下定義.

對于無人機利益分配(成本分攤)聯(lián)盟博弈(A,v)，A={a1,a2,…,aP}是參與者集合，v是價值函數(shù)，S為可行解脫方案集合，S={s1,s2…,sK}，解脫方案sk中任意無人機ai都有對應解脫成本v(sk,ai)，對sk中所有無人機解脫成本v(sk,ai)進行排列，按照從大到小順序記為ε(sk).

合作博弈的核仁即

N(sk)={x∈S|ε(x)≤ε(y),?y∈S} (3)

基于“核仁解”的沖突解脫方案具備以下優(yōu)點[8].

1) 解脫方案具備群體合理性與個體合理性.

2) 沖突解脫合作博弈解脫方案具有唯一“核仁解”.

3) 解脫“核仁解”中處于對稱地位的參與者解脫代價相近.

3.1 無人機解脫聯(lián)盟額外支付成本矩陣

對于一個由P架無人機組成的沖突解脫聯(lián)盟，若存在K個組合解脫策略，則有如下額外支付成本矩陣V.

(4)

式(4)成本矩陣為K行P列矩陣，矩陣中的第k行給出了第k個解脫策略中P架無人機各自的額外支付成本.

解脫聯(lián)盟最大額外支付成本矩陣為

(5)

式中：v*(sk)=maxv(sk,ai),i=1,2,…P為第k個解脫策略中P架無人機成員所付出額外支付成本的最大值.為獲得次大額外支付成本矩陣，核仁解解脫方案集形成潛在解額外支付成本矩陣V潛，矩陣V潛每一行均已剔除最大不滿，潛在解脫方案s核k剔除最大不滿無人機后的參與者集合A核k為

(6)

(7)

次大潛在解額外支付成本矩陣為

(8)

依次往復，得到從大到小的所有額外支付成本矩陣.

合作博弈的核仁即

?y∈S}

(9)

式中：vi(sk)為解脫方案k的第i大不滿；ki為第i大不滿的權重系數(shù)；I為解脫團體中無人機數(shù)量.

無人機低空飛行沖突解脫過程中，解脫額外支付成本由三部分組成：機動成本vm、位置偏差成本vp,以及航向偏差成本vh.機動成本與每一步機動類型、機動程度相關；位置偏差成本與機動解脫完畢后無人機現(xiàn)位置與原目標位置偏差相關；與機動解脫完畢后無人機現(xiàn)航向與原目標航向偏差相關.

解脫方案sk中無人機i機動成本為

(10)

v(sk,ai,m)=δ1|Δv|+δ2|Δθ|+δ3|Δh|,

δ1+δ2+δ3=1

(11)

式中：δ1，δ2，δ3為0-1參量；Δv,Δθ,Δh分別為速度、航向、高度機動量.

解脫方案sk中無人機i位置偏差成本為

(12)

解脫方案sk中無人機i航向偏差成本為

(13)

解脫方案sk中無人機i在沖突解脫過程中付出的總額外支付成本為

v(sk,ai)=ω(φ·vm(sk,ai)+

φ·vp(sk,ai)+γ·vh(sk,ai))

(14)

式中：φ,φ,γ為各類型成本代價對應權重；ω為優(yōu)先級增益系數(shù).

3.2 無人機優(yōu)先級

對于有高優(yōu)先級無人機的沖突解脫博弈聯(lián)盟(A,v)，設無人機i#擁有更高優(yōu)先級(如搶險救災)，則無人機i#支付成本v(sk,ai#)在優(yōu)先級增益系數(shù)ω加成下，在任何解脫方案中都屬于最大值，即

(15)

k=1,2,…,K

(16)

即核仁解必定在高優(yōu)先級無人機i#所花費代價最小的解脫方案中產(chǎn)生，從而保證了i#意愿的優(yōu)先滿足，達到任務重要的無人機活動更加優(yōu)先的目的.

3.3 最優(yōu)解脫策略搜索算法

建立基于改進遺傳算法的最優(yōu)策略搜索算法(optimal strategy searcher based on improved genetic algorithm，OSBGA)，在所有可能的路徑策略中尋找滿足沖突解脫要求的最優(yōu)路徑方案.OSBGA對沖突解脫“分支”模型中的每一步的n種機動策略進行二進制編碼，見圖3.

圖3 單步機動策略編碼示意

路徑方案總體二進制編碼見表1.

表1 無人機沖突解脫路徑方案編碼示意

沖突解脫過程中各無人機之間需始終滿足最小間隔標準要求，即在解脫過程中的任意時刻τ，任意兩無人機之間滿足：

?i,j∈[1,P],i≠j有

遺傳算法中某串基因編碼是否能夠得到繼承取決于該基因編碼適應度(fitness).在航空領域，除了無人機飛行安全以外，飛行的效率及管制策略對各運行主體的公平性愈加得到關注，本文設計適應度函數(shù)為

(18)

式中：vi(sk)為解脫方案k的第i大不滿；ki為第i大不滿的權重系數(shù)；I為解脫團體中無人機數(shù)量.根據(jù)Schmeidler，核仁解具有群體合理性以及個體間公平性，因此，通過對核仁解的尋找可以實現(xiàn)公平性以及高效性指標.同時，本文通過對ω的設定可以滿足解脫優(yōu)先級合理性要求.

4 實驗及分析

為驗證本文算法有效性，設置15 km×15 km的飛行仿真環(huán)境，分別對基于單策略調(diào)速和單策略調(diào)航向情景進行仿真驗證.設計多種仿真情景見表2.

表2 低空無人機沖突仿真情景

情景1～3為調(diào)速解脫情景，雙機90°交叉相遇，仿真過程中初始速度設置為1.5 km/min，調(diào)速解脫分為10步，無人機速度變化范圍為±32%；情景4～6為調(diào)航向解脫情景，五架無人機起始位置均勻分布在半徑為7.5 km的圓上，圓上正對位置為其各自終點，其解脫步數(shù)設置為5步，每步步長3 km，每步可選擇航向變化量{0,±10°,±20°,±30°}，共計七種.

調(diào)速解脫3種情景仿真結(jié)果速度曲線見圖4，各情景a)、b)無人機額外支付成本見圖5，可以發(fā)現(xiàn)情景2加入“核仁解”優(yōu)化后，雙機不滿程度的差異明顯較情景1未加“核仁解”優(yōu)化的要小，解脫更加公平.情景3中，ɑ機具有更高優(yōu)先級，其額外支付成本遠小于b機，符合現(xiàn)實優(yōu)先級要求.同時可以發(fā)現(xiàn)，基于“核仁解”的解脫方案其總體額外支付成本略高于傳統(tǒng)解脫，可以認為是為實現(xiàn)公平所不可避免需要付出的代價.

圖5 調(diào)速解脫各機額外支付成本對比

在調(diào)航向解脫仿真實驗中，結(jié)合實際飛行能耗水平將權重φ,φ,γ分別設定為2，20，1[9]，得到情景4傳統(tǒng)調(diào)航向解脫與情景5基于“核仁解”調(diào)航向解脫的仿真結(jié)果見圖6.兩種情景都能實現(xiàn)沖突的有效化解，但其各機解脫所支付的額外成本有明顯差異.表3為調(diào)航向解脫過程中各機額外支付成本.為清晰體現(xiàn)出各情景解脫公平性差異，本文繪制洛倫茲曲線對數(shù)據(jù)進行更直觀呈現(xiàn).洛倫茲曲線為經(jīng)濟領域評價公平性的常用方法，由美國統(tǒng)計學家洛倫茲提出.洛倫茲曲線通過曲線與公平基準線之間所夾面積的大小判斷公平程度，若洛倫茲曲線與公平基準線重疊，則表明分配完全公平，相反所夾面積越大表明分配越不公平.

圖6 傳統(tǒng)和基于“核仁解”的調(diào)航向解脫

表3 五機調(diào)航向解脫各機額外支付成本

對情景4～5仿真結(jié)果中的各機額外支付成本分別繪制洛倫茲曲線，見圖7.由圖7可知，情景5洛倫茲曲線與公平基準線所夾面積僅為情景4的25%左右，遠小于情景4.表明加入“核仁解”優(yōu)化過后，調(diào)航向沖突解脫的公平性較傳統(tǒng)方法顯著提升.

圖7 不同方法調(diào)航向解脫公平度對比

圖8 最佳優(yōu)先級增益系數(shù)分析

由圖8中曲線變化規(guī)律可知，f(ω)隨著優(yōu)先級增益系數(shù)ω的增大而減小，當ω取值大于等于7后基本保持穩(wěn)定；而解脫過程中的整體額外支付成本S隨著優(yōu)先級增益系數(shù)ω的增大呈不斷上升趨勢.因此，取優(yōu)先級增益系數(shù)ω為7，使得解脫過程盡可能滿足高優(yōu)先級無人機利益，同時盡可能減少整體額外支付成本.

以典型情景6為例進行多次仿真實驗，情景6為五機匯聚相遇，其中一架無人機相較其它四架具有更高優(yōu)先級，使用本文基于核仁解調(diào)航向策略進行解脫.仿真過程中權重φ、φ、γ依舊設定為2，20，1，根據(jù)上述優(yōu)先級增益系數(shù)分析結(jié)果，設定優(yōu)先級增益系數(shù)ω為7.對多次仿真實驗中各機額外支付成本繪制洛倫茲曲線，見圖9.

圖9 各機支付成本公平性對比

由圖9可知，沖突解脫過程中具有更高優(yōu)先級的無人機所支付額外成本明顯低于其余四架無人機，平均額外支付成本約為低優(yōu)先級航空器的15%，如累計無人機數(shù)“0-1”段中所示，表明本文算法能夠有效優(yōu)化降低高優(yōu)先級無人機解脫額外支付成本，符合現(xiàn)實情況中低優(yōu)先級無人機避讓高優(yōu)先級無人機的要求.同時，其余4機額外支付成本的洛倫茲曲線基本呈直線走勢，表明其余同優(yōu)先級無人機解脫過程中公平性較好.

5 結(jié) 束 語

本文構建無人機沖突解脫“分支模型”，并將“核仁解”引入到低空無人機沖突解脫過程中，提出了基于核仁解的低空無人機協(xié)作沖突解脫算法，實現(xiàn)了低空多無人機之間的沖突化解.通過繪制洛倫茲曲線，直觀清晰的呈現(xiàn)的當前沖突解脫算法存在的解脫不公平問題.仿真比較發(fā)現(xiàn)，本文算法各無人機額外支付成本的洛倫茲曲線包絡面積僅為傳統(tǒng)算法的25%，能夠有效提高無人機沖突解脫過程中的公平性.同時，由于“核仁解”本身具備群體合理性，沖突解脫在滿足公平性要求的基礎上能夠盡可能逼近系統(tǒng)最優(yōu).其次，通過引入優(yōu)先級增益系數(shù)ω，本文沖突解脫算法實現(xiàn)了對高優(yōu)先級航空器的優(yōu)先避讓，使沖突解脫具備實際合理性.

由于當前航空器活動大多按固定高度層飛行，因此本文僅考慮了同一水平面無人機沖突解脫問題.當前低空“自由飛”概念廣受關注，低空的“高度層”特征并不特別明顯，后續(xù)研究將考慮加入無人機垂直方向上的沖突以及調(diào)高度的沖突解脫方式.