基于核仁解的低空無人機(jī)協(xié)作沖突解脫算法*

錢曉鵬 張洪海 田 宇 王立超

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

0 引 言

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

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

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

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

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

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

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

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

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

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

2 沖突解脫“分支”模型

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

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

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

(1)

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

(2)

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

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

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

對(duì)無人機(jī)沖突解脫過程中“核仁解”作出如下定義.

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

合作博弈的核仁即

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

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

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

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

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

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

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

(4)

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

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

(5)

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

(6)

(7)

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

(8)

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

合作博弈的核仁即

?y∈S}

(9)

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

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

解脫方案sk中無人機(jī)i機(jī)動(dòng)成本為

(10)

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

δ1+δ2+δ3=1

(11)

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

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

(12)

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

(13)

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

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

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

(14)

式中：φ,φ,γ為各類型成本代價(jià)對(duì)應(yīng)權(quán)重；ω為優(yōu)先級(jí)增益系數(shù).

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

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

(15)

k=1,2,…,K

(16)

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

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

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

圖3 單步機(jī)動(dòng)策略編碼示意

路徑方案總體二進(jìn)制編碼見表1.

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

沖突解脫過程中各無人機(jī)之間需始終滿足最小間隔標(biāo)準(zhǔn)要求，即在解脫過程中的任意時(shí)刻τ，任意兩無人機(jī)之間滿足：

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

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

(18)

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

4 實(shí)驗(yàn)及分析

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

表2 低空無人機(jī)沖突仿真情景

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

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

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

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

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

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

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

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

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

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

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

圖9 各機(jī)支付成本公平性對(duì)比

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

5 結(jié) 束 語

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

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