基于合作博弈的多機(jī)飛行沖突解脫策略

蔣旭瑞, 吳明功, 溫祥西, 涂從良, 聶黨民

(1. 空軍工程大學(xué)空管領(lǐng)航學(xué)院, 陜西 西安 710051; 2. 國家空管防相撞技術(shù)重點實驗室,陜西 西安 710051; 3. 中國人民解放軍94347部隊, 遼寧 沈陽 110043)

0 引 言

近年來,我國航空運(yùn)輸需求不斷增長,給空中交通管理帶來了巨大壓力。在現(xiàn)行機(jī)場-終端-航路航線的運(yùn)行模式下,難以突破“人在回路”的制約,空域整體利用率不高。針對這一狀況,“自由飛行”[1]是一個有效的解決思路。在自由飛行條件下,飛行員在保證安全間隔的基礎(chǔ)上,自主選擇航線以提升效率。然而,飛行路線的多向性必然導(dǎo)致飛行沖突的可能性增加。為保證飛機(jī)間的安全間隔,尋求一種中、短期飛行沖突解脫方法尤為重要[2]。目前工程上應(yīng)用最多的沖突解脫方法是幾何法,主要采用線性外推的方法預(yù)測飛機(jī)航跡[3-4]。其主要缺點在于,對于多機(jī)沖突解脫的情況,不能保證得到的解是全局最優(yōu)的。Eby把在機(jī)器人領(lǐng)域廣泛應(yīng)用的規(guī)避障礙物的方法勢能法引入到飛行沖突解脫中[5],勢能法具有很強(qiáng)的魯棒性,能夠適應(yīng)復(fù)雜環(huán)境,但要求飛機(jī)連續(xù)大角度機(jī)動或速度大范圍改變,產(chǎn)生超出邊界條件的解。以遺傳算法為代表的優(yōu)化算法是沖突解脫方法中研究較早的智能算法[6-7],遺傳算法沖突模型的選擇對算法的復(fù)雜度有很大的影響,且運(yùn)算量大。以雙機(jī)沖突為例,遺傳算法運(yùn)行時間為12.35s,在多機(jī)沖突中難以實時解算。

近年來,博弈論在解決沖突、優(yōu)化資源配置方面的優(yōu)勢被逐漸應(yīng)用于飛行沖突解脫領(lǐng)域。Tomlin等人使用非合作博弈論研究兩機(jī)沖突,計算出目標(biāo)機(jī)在最差航跡下我機(jī)保持安全間隔的初始狀態(tài)[8],并在文獻(xiàn)[9]中采用微分對策理論證明了密集平行進(jìn)近階段鄰近兩機(jī)的可能失誤不會違反間隔要求。崔軍輝[10]等人使用微分對策理論對感知-規(guī)避問題給出了安全區(qū)域?qū)o人機(jī)飛行策略和制導(dǎo)律的影響。朱衍波使用效益博弈解決雙機(jī)飛行沖突[11],為博弈論在飛行沖突解脫中的應(yīng)用提供了指導(dǎo)性思路,但在他的研究中,避讓飛機(jī)和避讓策略的確定是單獨的,且支付函數(shù)中懲罰與補(bǔ)償?shù)囊肟赡芴蕹凉M足安全標(biāo)準(zhǔn)的最優(yōu)解。

基于此,本文針對多機(jī)沖突特點,提出了合作博弈飛行沖突解脫模型。以聯(lián)盟福利最優(yōu)解均衡各方效益,使可能沖突的飛機(jī)各避讓較小角度,既保證聯(lián)盟整體利益,體現(xiàn)公平性要求,又使各機(jī)根據(jù)重要程度實現(xiàn)了效益均衡。在考察了評價航空器沖突解脫效果的指標(biāo)后,提出了3種效用函數(shù),分別對應(yīng)航空器的時間最短策略、避讓角度最小策略和綜合最優(yōu)策略。在沖突解脫過程中,首先計算出局中人每一個滿足安全間隔標(biāo)準(zhǔn)的可行策略的效用值;其次,對局中人任意策略組合的效用值加權(quán)求和得到聯(lián)盟福利函數(shù);再次,解算出使聯(lián)盟福利函數(shù)最大的策略集合,即為合作博弈的聯(lián)盟福利最優(yōu)解;最后,通過粒子群算法求解,降低了運(yùn)行時間。希望通過以上方法,根據(jù)偏好快速獲得各方均滿意的解脫策略,輔助飛行員決策及管制員調(diào)配,實現(xiàn)實時的中、短期沖突解脫。

1 合作博弈與聯(lián)盟福利最優(yōu)解

合作博弈是指在協(xié)議的約束下各方利益都有所增加,或者在不損害任意一方利益的前提下,有參與者利益增加,從而整個聯(lián)盟的利益有所增加。與非合作博弈相比,合作博弈更加強(qiáng)調(diào)集體主義和團(tuán)體理性(collective rationality),主要研究了參與者達(dá)成合作時如何分配合作所得收益的問題。聯(lián)盟內(nèi)部的信息互通和存在有約束力的可執(zhí)行契約是達(dá)成合作博弈的兩個前提條件。

合作博弈在發(fā)展的過程中提出了眾多的解概念,其基本思想就是要設(shè)計出一種公平解,促使參與者在不損害聯(lián)盟利益的前提下獲得更高的收益。這里我們以聯(lián)盟福利最優(yōu)解[12-13]為解配置均衡各方利益,聯(lián)盟福利最優(yōu)解要滿足以下3個條件:

(1) 聯(lián)盟參與人具有為聯(lián)盟整體謀求最大福利的行為;

(2) 聯(lián)盟參與人具有追求公平的偏好;

(3) 聯(lián)盟參與人追求個人利益和公平性不能以犧牲聯(lián)盟福利為代價。

2 模型的建立與分析

從合作博弈的理論基礎(chǔ)中可以發(fā)現(xiàn),多機(jī)飛行沖突解脫就是一個多方合作博弈的過程。有沖突風(fēng)險的航空器是參與博弈的局中人,具有若干飛行解脫策略,它們通過地面、機(jī)載通信導(dǎo)航設(shè)備實現(xiàn)信息互通,以全國統(tǒng)一的飛行管制為基礎(chǔ)形成具有強(qiáng)執(zhí)行力的穩(wěn)固聯(lián)盟,圍繞各自的避讓支付代價展開合作博弈。一方面,從個體的角度出發(fā),希望自己的避讓飛行代價小;而另一方面,從聯(lián)盟整體角度考慮,要以安全間隔為約束條件并合理均衡各方利益。在航空器重要程度相當(dāng)?shù)那疤嵯?希望各避讓較小角度,避免有的航空器不避讓,有的機(jī)動角度過大,安全性降低。這種追求整體利益最大化的特點符合聯(lián)盟福利最優(yōu)解的特性。

2.1 合作博弈沖突解脫模型

當(dāng)航空器探測到下一階段可能發(fā)生飛行沖突,各局中人I={i|i∈[1,N]}的所有解脫策略組成策略空間Si(sij∈Si表示參與人i的第j個策略),在安全間隔的約束下互相博弈,獲得相應(yīng)效用u={u1,u2,…,un}。效用函數(shù)ui:S→R,表示第i位參與者在不同策略組合下所得的收益。把每個參與者的各一個策略組成的某策略集合{s1,s2,…,sn}對應(yīng)收益{u1,u2,…,un}加權(quán)求和得到聯(lián)盟福利函數(shù):

·uij

(1)

圖1 博弈沖突解脫基本流程Fig.1 Flow graph of conflict resolution based on cooperativegame theory

模型中,研究的主要對象是可能發(fā)生危險沖突的航空器組成的聯(lián)盟。參與者之間通過聯(lián)盟獲取更高的效用,而對于某個體航空器而言,所選擇的策略不一定是收益最高的。以聯(lián)盟福利最優(yōu)解為解配置,在保證航空器聯(lián)盟安全的前提下,根據(jù)付出的總避讓代價最小的原則,確定出需要避讓的飛機(jī)及其機(jī)動策略,文中主要研究了航向解脫。

根據(jù)飛行操縱的實際情況,將模型簡化如下:

(1)在自由飛行條件下,除起飛和降落階段以外,都是在指定高度層飛行。因此,將模型簡化為二維平面的沖突解脫問題。

(2)從安全角度考慮,非戰(zhàn)斗機(jī)一般不進(jìn)行大角度機(jī)動,我們規(guī)定航空器航向角改變范圍為[-30°,30°]。在實際飛行中,為方便飛行員操作,管制員一般以整5°指揮飛機(jī)航向機(jī)動,這里把航向角變化范圍也離散成相差5°的策略集合,如圖2所示。

圖2 解脫角度離散化Fig.2 Angle discretization

(3)把航空器視為質(zhì)點,機(jī)載雷達(dá)探測半徑為100 km,在50 km以內(nèi)建立告警區(qū),10 km以內(nèi)劃設(shè)保護(hù)區(qū)。

當(dāng)2架飛機(jī)進(jìn)入對方告警區(qū),我們認(rèn)為存在飛行沖突的潛在威脅,進(jìn)入解脫流程。為防止當(dāng)前沖突的雙機(jī)解脫后與周圍飛機(jī)發(fā)生新的沖突,探測范圍內(nèi)的所有航空器均參與博弈確定避讓策略,避免二次解脫。當(dāng)兩機(jī)距離小于10 km,我們認(rèn)為飛行沖突發(fā)生,避讓失敗,即

≤Ssafe

(2)

式中,(xi,yi)和(xj,yj)分別為航空器i、j在平面上的坐標(biāo)；Ssafe為兩機(jī)的安全間隔10 km。解脫流程從進(jìn)入告警區(qū)開始,至到達(dá)目的地為止。

2.2 效用函數(shù)的提出

效用函數(shù)又稱支付函數(shù),是參與人從博弈中獲得的效用水平,主要由避讓支付的代價決定。航空器在沖突解脫中支付越少機(jī)動成本將獲得越高的效用,選擇不避讓的航空器將獲得最高的收益。從航空器整個沖突解脫流程出發(fā),考察各機(jī)效益。對于航空器個體而言,在避讓中支付的代價,主要由飛行時間、飛行航程(航路費(fèi))、航空器耗油量和轉(zhuǎn)彎角度決定。模型假設(shè)飛機(jī)進(jìn)入航線飛行后采用巡航速度飛行,且避讓時速度大小不變,航程可以表示為時間的函數(shù)，即

Stotal=vcruise·ttotal

(3)

式中,Stotal為總航程;vcruise為巡航速度;ttotal為總飛行時間。由于解脫策略僅考慮航向機(jī)動,不涉及高度、速度的變化,耗油量可以表示為飛行總時間的函數(shù)，即

Q=βttotal

(4)

式中,Q為耗油量;β是燃油消耗率,主要受航空器機(jī)型影響。可以看出,影響航空器解脫效用的指標(biāo)與飛行時間存在密切關(guān)系,可以把時間的函數(shù)作為博弈中的效用函數(shù),對應(yīng)的解為時間最優(yōu)策略，即

(5)

式中,t是該航空器飛行解脫的時間,從進(jìn)入告警流程開始到解脫結(jié)束恢復(fù)航線為止。另外,避讓的偏轉(zhuǎn)角度也是衡量避讓效益的一個重要指標(biāo),效用函數(shù)對應(yīng)的解策略為角度最優(yōu)策略，即

(6)

式中,θ是航空器避讓偏轉(zhuǎn)角度,偏轉(zhuǎn)越大,越不利于飛行安全。綜合考慮時間和轉(zhuǎn)角的因素,我們提出了時間、角度的綜合避讓方案,其效用函數(shù)可以表示為

(7)

式中,λ是調(diào)節(jié)參數(shù)，λ越大,表明策略更注重時間指標(biāo),反之λ越小,更注重轉(zhuǎn)角指標(biāo)。

2.3 策略公平性與聯(lián)盟福利最優(yōu)的統(tǒng)一性

從第1節(jié)中我們知道,如果所得的策略集合單單是公平解,聯(lián)盟整體福利因為兼顧公平而受到損失,這個解就不是最優(yōu)的。為了證明聯(lián)盟福利最優(yōu)解作為解決飛行沖突解配置的有效性,我們推導(dǎo)了任意航跡交叉角θ下策略公平性與聯(lián)盟福利的關(guān)系。雙機(jī)對頭飛行場景如圖3所示。

圖3 雙機(jī)匯聚飛行場景 Fig.3 Centering flight of two aircraft

(8)

在ΔS1OS2中,由正弦定理知

(9)

對于單機(jī)解脫的情況,兩機(jī)距離之和為

(10)

在ΔO′OS2中

φ=π-θ-α

(11)

由正弦定理知

(12)

′)2=(S2O′)2+(S2S2′)2-2cosα·S2O′·S2S2′

(13)

在ΔS1S2P′中,由正弦定理知

?

(14)

將式(8)、式(9)、式(11)～式(14)代入式(10)中,可得L1的表達(dá)式。

對于雙機(jī)解脫的情況,兩機(jī)距離之和為

(15)

在ΔS1S2O′中,由正弦定理知

(16)

′)2=(S1O′)2+(S1S1′)2-2cosβ·S1O′·S1S1′

(17)

同理

(18)

(19)

在ΔS1S2P′中,由正弦定理知

?

(20)

(21)

將式(8)、式(9)、式(16)～式(21)代入式(15)中,可得L2的表達(dá)式。令f(θ)=L1-L2,作出L隨航跡交叉角θ的變化曲線,如圖4所示。

當(dāng)航向交叉角小于20°時,近似于平行飛行,在沖突解脫問題中,僅通過航向機(jī)動調(diào)配代價很大,故不作考慮。圖4中,函數(shù)f(θ)=L1-L2恒大于零,即兩機(jī)匯聚飛行狀態(tài)下,無論航向交叉角θ如何變化,單機(jī)大角度機(jī)動避讓較雙機(jī)同時同角度避讓支付代價更大,聯(lián)盟福利最優(yōu)解配置的公平性與整體效益性是統(tǒng)一的。另外,航向交叉角越小,雙機(jī)同時避讓的優(yōu)越性越能體現(xiàn)。

3 基于粒子群優(yōu)化算法的沖突消解

粒子群優(yōu)化(particle swarm optimization, PSO)算法是進(jìn)化算法中的一種用于優(yōu)化的并行算法。它從隨機(jī)解出發(fā),經(jīng)過迭代找出最優(yōu)解,通過適應(yīng)度評價解的品質(zhì)。因其實現(xiàn)容易、精度高、收斂快等特點被廣泛應(yīng)用。

在合作博弈沖突解脫模型中,當(dāng)沖突機(jī)數(shù)量較少時(如三機(jī)沖突解脫),通過遍歷所有航空器的行動集合可以較快地尋優(yōu),但當(dāng)沖突機(jī)數(shù)量較多時,遍歷所有策略組合耗時過長,難以滿足實時解脫要求。在六機(jī)沖突場景中,遍歷13種行動組合共136=4 826 809種情況,仿真運(yùn)算時間較長。利用粒子群優(yōu)化算法快速求解,其主要思路如下:

(1)適應(yīng)度函數(shù)

將聯(lián)盟福利函數(shù)作為該問題的適應(yīng)度函數(shù)。

(2)編碼方式

(3)約束條件

①通過取整函數(shù)保證運(yùn)算每一步粒子位置值均為整數(shù);

通過不斷選擇、改變超出邊界的位置值保證解的可行性[14]。對于粒子中位置值小于1的情況作如下處理:

(22)

對粒子位置值大于13的作如下處理:

(23)

求解的主要流程如圖5所示。

圖5 粒子群算法沖突消解主要流程Fig.5 Process of PSO

4 仿真分析

為了驗證基于合作博弈的飛行沖突解脫效果,在Matlab環(huán)境中分別對三機(jī)和六機(jī)沖突場景進(jìn)行了仿真。其中,三機(jī)沖突的解算遍歷所有策略,根據(jù)提出的3種效用函數(shù)偏好,得出相應(yīng)的最優(yōu)航跡;六機(jī)沖突利用粒子群優(yōu)化算法消解沖突,得出3種策略對應(yīng)的解脫航跡。以最短時間策略為例,與遍歷法求得的航跡進(jìn)行了比較,從運(yùn)算時間和適應(yīng)度兩個指標(biāo),表明了粒子群算法優(yōu)化結(jié)果的有效性與穩(wěn)定性。

圖6 三機(jī)沖突解脫軌跡Fig.6 Trajectory of three aircraft resolution

表1 3種策略下航空器機(jī)動角度

最小轉(zhuǎn)角和綜合最優(yōu)策略解脫航跡是相同的。從解脫效果看,有效避免了解脫過程中某架航空器采取大角度機(jī)動而其他航空器不避讓的情況,在均衡效益的同時,實現(xiàn)了聯(lián)盟利益的最大化。

為了進(jìn)一步驗證模型可行性,針對提出的3種策略,我們對六機(jī)沖突場景進(jìn)行了仿真:a、b、c、d、e、f為6架航空器,在t0時刻分別位于初始位置(20,0),(80,100),(80,0),(20,100),(100,50),(0,50)向目的地飛行,其他參數(shù)設(shè)置與三機(jī)沖突是一致的。

以最短時間策略為例,通過粒子群算法與遍歷法求得策略比較,檢驗了粒子群優(yōu)化算法的收斂性與穩(wěn)定性。設(shè)置粒子種群數(shù)N=20,維度D=6,迭代次數(shù)M=50。因滿足安全間隔要求的解數(shù)量有限,為提高算法跳出局部最優(yōu)的能力,取較小的學(xué)習(xí)因子c1=c2=0.8和較大的慣性因子?=0.8。我們考察算法的收斂性,觀察策略的適應(yīng)度值隨收斂代數(shù)的變化情況,結(jié)果如圖7所示。

圖7 適應(yīng)度值隨收斂代數(shù)的變化Fig.7 Change of fitness with the convergence times

從圖7中可以看出,算法在第4、10、17、27、36代跳出局部最優(yōu),在41代時收斂于全局最優(yōu)0.008 6,算法收斂性較好。

下面進(jìn)一步考察算法穩(wěn)定性,我們對粒子群算法的消解進(jìn)行了多次仿真,與遍歷出的最優(yōu)策略比較,結(jié)果如表2所示。

表2 粒子群優(yōu)化效果比較

表2首行是遍歷法求解的時間最短策略,其余各行是粒子群算法多次運(yùn)算的結(jié)果,以上行動選擇均滿足安全間隔要求。仿真結(jié)果表明,在該參數(shù)設(shè)置下,粒子群算法多次運(yùn)行結(jié)果適應(yīng)度值均收斂于0.008 6,與遍歷算法求解的聯(lián)盟福利函數(shù)值相等,算法穩(wěn)定性較好,且運(yùn)行時間大大縮短。吳君等人的研究中,遺傳算法用于兩機(jī)沖突解脫需12.35 s[15];王淵等人的研究中,改進(jìn)蜂群算法用于兩機(jī)沖突需8.22 s[16]。文中提出的合作博弈沖突解脫模型,遍歷法用于三機(jī)沖突解脫運(yùn)行時間僅0.36 s,經(jīng)粒子群算法優(yōu)化后六機(jī)沖突平均運(yùn)行時間為3.13 s,為實時沖突解脫提供了參考。

利用粒子群優(yōu)化算法解算最短時間策略、最小轉(zhuǎn)角策略和綜合最優(yōu)策略的解脫航跡如圖8所示。

圖8 粒子群優(yōu)化算法消解沖突解脫軌跡Fig.8 Conflict resolution track based on PSO

在這3種偏好解脫策略下,達(dá)到均衡點時各機(jī)機(jī)動角度如表3所示。

表3 3種策略下航空器機(jī)動角度

從仿真結(jié)果可以看出,該方法在六機(jī)沖突中也能解算出有效的行動選擇。我們還可以發(fā)現(xiàn),3種不同效用函數(shù)下得出的行動選擇均為同向避讓,與管制指揮調(diào)配規(guī)則是一致的。另外,我們還比較了不同策略下各機(jī)完成航線飛行的飛行時間,結(jié)果如表4所示。

表4 不同策略下各機(jī)轉(zhuǎn)角及航線飛行時間

從表4中可以發(fā)現(xiàn),最小轉(zhuǎn)角策略在一定程度上增加了飛行時間,但聯(lián)盟總機(jī)動角度最小,綜合最優(yōu)策略是基于兩種策略的一種折中策略,各機(jī)的避讓時間都在可接受范圍內(nèi)。與遺傳算法相比,該算法在將解脫角度離散化處理時,犧牲了部分精度,但以整5°改變航向更加符合飛行實際,且付出的額外時間成本不大。

5 結(jié) 論

本文把合作博弈理論應(yīng)用于飛行沖突解脫領(lǐng)域,提出了合作博弈沖突解脫模型,論證了把聯(lián)盟福利最優(yōu)解作為飛行沖突問題解配置的可行性,根據(jù)解脫效果的偏好,提出了3種效用函數(shù),在保證飛行聯(lián)盟整體解脫代價最小的前提下,有效均衡了各方效益,解算出相對公平的解脫行動,并在此基礎(chǔ)上通過粒子群算法有效降低了運(yùn)行時間,實現(xiàn)了實時的沖突探測與解脫。此外,模型可通過調(diào)整航空器權(quán)重ki,根據(jù)飛機(jī)的重要程度實現(xiàn)效益均衡;通過調(diào)整效用函數(shù)中的調(diào)節(jié)系數(shù)λ改變偏好設(shè)置,或重新設(shè)計效用函數(shù),使解脫策略滿足實際的需求。