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

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

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

0 引 言

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

近年來,博弈論在解決沖突、優化資源配置方面的優勢被逐漸應用于飛行沖突解脫領域。Tomlin等人使用非合作博弈論研究兩機沖突,計算出目標機在最差航跡下我機保持安全間隔的初始狀態[8],并在文獻[9]中采用微分對策理論證明了密集平行進近階段鄰近兩機的可能失誤不會違反間隔要求。崔軍輝[10]等人使用微分對策理論對感知-規避問題給出了安全區域對無人機飛行策略和制導律的影響。朱衍波使用效益博弈解決雙機飛行沖突[11],為博弈論在飛行沖突解脫中的應用提供了指導性思路,但在他的研究中,避讓飛機和避讓策略的確定是單獨的,且支付函數中懲罰與補償的引入可能剔除滿足安全標準的最優解。

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

1 合作博弈與聯盟福利最優解

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

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

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

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

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

2 模型的建立與分析

從合作博弈的理論基礎中可以發現,多機飛行沖突解脫就是一個多方合作博弈的過程。有沖突風險的航空器是參與博弈的局中人,具有若干飛行解脫策略,它們通過地面、機載通信導航設備實現信息互通,以全國統一的飛行管制為基礎形成具有強執行力的穩固聯盟,圍繞各自的避讓支付代價展開合作博弈。一方面,從個體的角度出發,希望自己的避讓飛行代價小;而另一方面,從聯盟整體角度考慮,要以安全間隔為約束條件并合理均衡各方利益。在航空器重要程度相當的前提下,希望各避讓較小角度,避免有的航空器不避讓,有的機動角度過大,安全性降低。這種追求整體利益最大化的特點符合聯盟福利最優解的特性。

2.1 合作博弈沖突解脫模型

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

·uij

(1)

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

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

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

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

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

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

(3)把航空器視為質點,機載雷達探測半徑為100 km,在50 km以內建立告警區,10 km以內劃設保護區。

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

≤Ssafe

(2)

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

2.2 效用函數的提出

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

Stotal=vcruise·ttotal

(3)

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

Q=βttotal

(4)

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

(5)

式中,t是該航空器飛行解脫的時間,從進入告警流程開始到解脫結束恢復航線為止。另外,避讓的偏轉角度也是衡量避讓效益的一個重要指標,效用函數對應的解策略為角度最優策略，即

(6)

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

(7)

式中,λ是調節參數，λ越大,表明策略更注重時間指標,反之λ越小,更注重轉角指標。

2.3 策略公平性與聯盟福利最優的統一性

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

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

(8)

在ΔS1OS2中,由正弦定理知

(9)

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

(10)

在ΔO′OS2中

φ=π-θ-α

(11)

由正弦定理知

(12)

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

(13)

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

?

(14)

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

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

(15)

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

(16)

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

(17)

同理

(18)

(19)

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

?

(20)

(21)

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

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

3 基于粒子群優化算法的沖突消解

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

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

(1)適應度函數

將聯盟福利函數作為該問題的適應度函數。

(2)編碼方式

(3)約束條件

①通過取整函數保證運算每一步粒子位置值均為整數;

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

(22)

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

(23)

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

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

4 仿真分析

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

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

表1 3種策略下航空器機動角度

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

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

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

圖7 適應度值隨收斂代數的變化Fig.7 Change of fitness with the convergence times

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

下面進一步考察算法穩定性,我們對粒子群算法的消解進行了多次仿真,與遍歷出的最優策略比較,結果如表2所示。

表2 粒子群優化效果比較

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

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

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

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

表3 3種策略下航空器機動角度

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

表4 不同策略下各機轉角及航線飛行時間

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

5 結 論

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