基于改進馬爾可夫決策過程模型的多機協(xié)同航路規(guī)劃研究

劉 蓉,張 衡,肖穎峰

(南京航空航天大學(xué) 1.無人機研究院;2.工信部中小型無人機重點實驗室;3.自動化學(xué)院,江蘇 南京 210016;4.中電熊貓漢達科技有限公司,江蘇 南京 210016)

協(xié)同航路規(guī)劃作為實現(xiàn)多無人機協(xié)同作戰(zhàn)的關(guān)鍵環(huán)節(jié),已成功聚焦國內(nèi)外無人機領(lǐng)域?qū)＜业难芯糠较騕1-3]。協(xié)同航路規(guī)劃所生成航路能保證無人機之間相互配合,以最小的飛行代價完成任務(wù)[4]。目前,國內(nèi)外對多機航路規(guī)劃的研究,均側(cè)重于對多無人機進行單獨航路規(guī)劃,很多沒有考慮任務(wù)的時間協(xié)同要求[5-7]。常規(guī)的蟻群算法、遺傳算法、A*算法具有較強的魯棒性與良好的信息反饋能力等優(yōu)點,但在復(fù)雜的戰(zhàn)場環(huán)境下算法的收斂速度低導(dǎo)致路徑搜索時間較長且易陷入局部最優(yōu)[8-11]。隨著人工智能技術(shù)的發(fā)展,基于Q學(xué)習方法的馬爾科夫決策模型被應(yīng)用于航跡規(guī)劃,但其狀態(tài)轉(zhuǎn)移概率設(shè)計僅考慮了無目標點和目標點在正北方時的兩種情況,無法充分體現(xiàn)狀態(tài)轉(zhuǎn)移概率在大范圍狀態(tài)空間下的分布[12]。

針對以上問題,本文提出一種基于改進馬爾可夫決策模型的多無人機航路規(guī)劃算法,利用離散化的雷達威脅信息,合理設(shè)計多無人機作戰(zhàn)環(huán)境,離散化目標點方位空間,合理分配狀態(tài)轉(zhuǎn)移概率,在無模型均勻結(jié)構(gòu)的報酬函數(shù)基礎(chǔ)上引入了非均勻結(jié)構(gòu)雷達威脅模型,建立改進馬爾可夫決策過程(Markov decision processes,MDP)模型。最后在MATLAB環(huán)境中進行仿真實驗,驗證算法有效性。

1 多機協(xié)同航路規(guī)劃

1.1 任務(wù)描述

多機協(xié)同航路規(guī)劃是指多無人機的飛行航路滿足客觀約束條件同時能夠讓各無人機實現(xiàn)最優(yōu)或次優(yōu)的特定性能指標[13]。為降低威脅模型復(fù)雜度,本文僅考慮敵方雷達的影響[14]。如圖1所示,由3架某型無人機在特定場景下執(zhí)行任務(wù),在該飛行場景下利用柵格法建立坐標系,A、B、C為3架無人機的起始點,D點為任務(wù)目標點,圓形區(qū)域為雷達威脅區(qū)域。多無人機協(xié)同航路規(guī)劃的任務(wù)就是為整個無人機編隊規(guī)劃出安全可飛航路,并同時到達目標點[15]。

圖1 多無人機協(xié)同航路規(guī)劃示意圖

1.2 多無人機綜合航行代價

1.2.1 油耗代價

航路的油耗代價可表示為

JL,i=clLi

(1)

式中:cl為比例系數(shù);Li表示第i架無人機的航路長度;JL,i為無人機的油耗代價。

1.2.2 威脅代價

第p個航路段所受到的威脅代價可表示為

(2)

無人機整體航路所受到的威脅代價為

(3)

式中:JT,p表示無人機在第p個航路段所受到的雷達威脅代價;lp表示第p個航路段長度;NT為雷達威脅個數(shù);d1/4,p,q、d1/2,p,q、d3/4,p,q分別表示無人機在第p個航路段的1/4、1/2、3/4處與第q個雷達之間的距離;JT,i表示第i個無人機所受到的總體威脅代價。

1.2.3 多機協(xié)同航行代價

本文采用多機協(xié)同航行代價為時間協(xié)同代價。多無人機協(xié)同飛行在滿足時間協(xié)同約束的條件下,才能同時到達規(guī)定目標點。時間協(xié)同代價可表示為

Jt,i=α(Li/vi-ta)

(4)

式中:Jt,i為時間協(xié)同代價;α>0為調(diào)節(jié)權(quán)重;Li為無人機航程;vi為無人機的航行速度;ta為時間協(xié)同變量。

1.2.4 綜合航行代價

對于多無人機,航路代價不僅考慮單機的燃油代價、威脅代價等[16],還應(yīng)滿足多機協(xié)同航行代價。多無人機的綜合航行代價描述為

Ji=W1Jl,i+W2Jr,i+W3Jt

(5)

式中:W1、W2和W3分別為燃油代價、威脅代價以及協(xié)同代價的權(quán)重,Jl,i代表燃油代價,與無人機飛行航程有關(guān);Jr,i為威脅代價;Jt為協(xié)同代價,它隨著無人機飛行時間的變化而改變。多無人機航路規(guī)劃的目的就是使無人機綜合代價最小化。

2 改進MDP的多機航路規(guī)劃設(shè)計

2.1 馬爾可夫決策基本模型

MDP模型用以下四元組M=〈S,A,P,R〉來表示[17]:S為系統(tǒng)狀態(tài)的有限集合,包含無人機飛行環(huán)境的有限狀態(tài)點;A為無人機可用的有限動作集合;P為狀態(tài)轉(zhuǎn)移函數(shù),表示當主體處在狀態(tài)st時,執(zhí)行動作at∈A,而轉(zhuǎn)移到狀態(tài)st+1的概率。狀態(tài)轉(zhuǎn)移概率會隨著目標狀態(tài)、威脅狀況等發(fā)生改變;R為報酬函數(shù),表示在給定無人機當前狀態(tài)和動作的情況下所能獲得的立即報酬。

如圖2所示,描述了在馬爾可夫決策模型下,無人機與飛行環(huán)境間進行交互的過程:在無人機執(zhí)行一個動作后,環(huán)境根據(jù)無人機所執(zhí)行動作而提供一個立即收益,并根據(jù)該動作獲知環(huán)境當前狀態(tài)[18]。

圖2 基本MDP模型

定義策略π作為馬爾可夫決策過程的策略空間,即無人機與環(huán)境在交互過程中選取動作的方法。定義評價函數(shù)Vπ(s)作為評價策略的優(yōu)劣。在航路規(guī)劃的決策問題中,系統(tǒng)性能取決于長期的動作,無人機需經(jīng)過多個時間步后完成任務(wù)或達到最后目標才能得到有意義的報酬。其中評價函數(shù)有以下3種[19]:

(1)有限范圍報酬模型

(6)

(2)平均報酬模型

(7)

(3)無限范圍折扣模型

(8)

式中:其中γ為折扣因子,Rt為在t時刻所對應(yīng)的報酬值。

有限范圍報酬模型是針對決策系統(tǒng)中決策序列長度已知的問題進行研究,而平均報酬模型和無限范圍折扣模型則適用于對決策序列長度未知的系統(tǒng)進行求解?；跓o限范圍折扣報酬模型的評價函數(shù)相比平均報酬模型更注重近期報酬,更符合多無人機全局航路規(guī)劃的特點,且基于平均報酬模型與無限范圍折扣報酬模型相比前者研究尚未成熟。因此,本文在多無人機全局航路規(guī)劃中將采用無限范圍折扣報酬模型進行研究。

2.2 改進MDP模型的建立

2.2.1 狀態(tài)空間的表示

本文定義無人機任務(wù)空間為100 km×100 km,采用柵格法進行離散建模。無人機飛行環(huán)境中,存在可飛區(qū)域與禁飛區(qū)域,因此,建立狀態(tài)空間模型如圖3所示,其中包含各無人機起點、目標點和若干以圓形等效的雷達威脅源,圓心所在位置為雷達出現(xiàn)的位置,圓的半徑表示威脅源的有效作用范圍。

圖3 狀態(tài)空間模型

2.2.2 動作空間的設(shè)計

在多無人機的航路規(guī)劃中,設(shè)定了各飛機的起點和目標點之后,在航路規(guī)劃時將飛機看作為一個質(zhì)點?；跂鸥穹▌澐值沫h(huán)境空間,可將無人機的動作根據(jù)航向狀態(tài)進行離散,定義無人機有8個可執(zhí)行動作,a=1,2,3,…,8。整個360°被這些動作等分,相鄰兩個動作之間的角度為45°。如下圖所示,為無人機的8個基本動作劃分。

圖4 無人機基本動作圖

2.2.3 狀態(tài)轉(zhuǎn)移函數(shù)的設(shè)計

無人機所處時刻狀態(tài)和對應(yīng)的動作明確前提下,狀態(tài)轉(zhuǎn)移概率的分布將在很大程度上決定無人機在下一時刻的動作選擇。狀態(tài)轉(zhuǎn)移概率可表示為

P(s′|s,a)=P(st+1=s′|st=s,at=a)

(9)

(10)

式中:?s,s′∈S表示無人機的狀態(tài)實例,?a∈S表示無人機動作實例,st表示在t時刻下無人機所處的狀態(tài),at表示t時刻無人機所選擇的動作。

無人機以安全到達目標點為任務(wù)目標,因此在無人機從初始點到目標點飛行時,其運動方向是以目標點的方位為導(dǎo)向的。將目標點與無人機的連線與目標點與X方向之間的夾角定義為θ,可以控制無人機根據(jù)目標點方位不斷調(diào)整動作使無人機朝向目標點移動。根據(jù)θ可將目標點周圍360°空間以45°為間隔劃分,離散成8個位置狀態(tài)。狀態(tài)示意圖如圖5所示,目標點位置空間Tstate離散規(guī)則如下

(11)

在目標位置點已知時,為控制無人機朝著目標點移動,可執(zhí)行的動作有限,同時認定無人機將以較大概率朝目標點方向所在柵格給出動作,也會以一定概率進入相鄰的柵格,但概率較小。當無人機處于目標點某個位置空間內(nèi)時,將有5個可執(zhí)行動作,且每個動作概率不同,則對于8個位置空間,動作輸出狀態(tài)共有5×8=40。如表1所示,為部分位置空間下,無人機可執(zhí)行動作的轉(zhuǎn)移概率設(shè)計。

圖5 位置狀態(tài)示意圖

表1 部分狀態(tài)轉(zhuǎn)移概率設(shè)計

2.2.4 報酬函數(shù)的改進設(shè)計

馬爾可夫模型系統(tǒng)中,報酬函數(shù)是在無人機做出動作策略并與環(huán)境進行交互后由環(huán)境反饋的懲罰或獎勵信號。在模型中表征著無人機在某種狀態(tài)下所采取動作的好壞程度,同時也是引導(dǎo)無人機進行飛行決策和安全避障的重要依據(jù)。在設(shè)計報酬函數(shù)時,需要考慮以下因素[20]。

(1)靠近目標點。從起點出發(fā)至目標點,為了使每架無人機規(guī)劃出的航路具有可行性,在環(huán)境模型下無人機所做出的動作行為應(yīng)使其更加靠近目標點。對于無人機更加趨近目標點的動作行為,報酬函數(shù)會選擇獎勵,反之則會懲罰。

(2)安全性。在無人機的環(huán)境模型中,存在可飛安全區(qū)域與威脅源禁飛區(qū)域,無人機馬爾可夫決策模型應(yīng)在威脅源禁飛區(qū)域外規(guī)劃出滿足無人機可飛的航路,避開禁飛區(qū)。因此,在報酬函數(shù)中,對于接近禁飛區(qū)域的行為進行懲罰,反之則會獎勵。

本文針對航路規(guī)劃過程無人機的安全性和趨向目標點的問題對報酬函數(shù)進行設(shè)計,引入了無模型均勻結(jié)構(gòu)的報酬函數(shù)模型Rmovegoal和Ravoidobstacle。

(12)

(13)

式中:Rmovegoal為無人機正常行駛時報酬函數(shù)模型,Ravoidobstacle為無人機遇到威脅時報酬函數(shù)模型。

無人機在飛行過程中會時刻受到雷達的威脅,所規(guī)劃出的航路威脅代價過高時無人機會被雷達檢測到?；诨抉R爾可夫模型算法雖能為無人機規(guī)劃出有效路徑,但所設(shè)計的報酬模型中忽略了威脅代價對無人機安全造成的影響。因此,為進一步提高無人機自身安全性,在報酬函數(shù)中提出并引入了非均勻結(jié)構(gòu)的雷達威脅模型Rthreat。

(14)

式中:Rthreat為無人機行駛時雷達威脅報酬函數(shù)模型,對于無人機飛行時受到的雷達威脅給以負的獎賞。L為無人機做出動作決策后該航路段的長度,N為雷達威脅個數(shù),dk/4,i,k=1,2,3為航路段的k/4點處與第i個雷達威脅之間的距離。

2.3 搜索策略

基于馬爾可夫決策模型的多無人機航路規(guī)劃旨在通過無人機動作與飛行環(huán)境之間進行交互并最終產(chǎn)生決策,規(guī)劃出無人機的有效航路。無人機主體根據(jù)當前環(huán)境狀態(tài)s,選擇并執(zhí)行動作a,使無人機狀態(tài)由s轉(zhuǎn)移到s′,同時獲得報酬R,循環(huán)往復(fù),直到最終達到目標狀態(tài)。因此,尋找最優(yōu)策略π*,即根據(jù)無人機的當前狀態(tài),執(zhí)行搜索策略,搜索使期望報酬即評價函數(shù)Vπ(s)最大的動作序列。

最優(yōu)策略π*表示所有狀態(tài)s∈S均存在V*(s)=maxπVπ(s),最優(yōu)策略π*對應(yīng)評價函數(shù)為最優(yōu)評價函數(shù)V*(s)。最優(yōu)策略π*可用動態(tài)規(guī)劃來尋找最大獎勵V*(s)。評價函數(shù)Vπ(s)可以描述為

(15)

式中:γ為折扣因子Rt為在t時刻所對應(yīng)的報酬值。s為t=0時刻無人機所對應(yīng)的狀態(tài),s′為下一時刻無人機所處狀態(tài)。則以遞歸形式可將上式重寫為

(16)

式(16)給定了一種計算策略所對應(yīng)評價函數(shù)的方法,定義狀態(tài)-動作值函數(shù)Qπ(s,a)作為對評價函數(shù)求解過程中中間變量。在給定無人機初始狀態(tài)s和當前動作a的條件下,無人機下一時刻將以概率P(s′|s,a)轉(zhuǎn)向下一狀態(tài)s′,并在未來遵循此規(guī)則,狀態(tài)-動作值函數(shù)Qπ(s,a)可表示為

(17)

式中:R(s,a)為無人機在狀態(tài)s下,選取動作a的所獲得的報酬。

此時,MDP最優(yōu)策略π*(s)可以表示為

(18)

相應(yīng)地,最優(yōu)評價函數(shù)V*(s)表示為

V*(s)=maxa∈A[R(s,a)+

(19)

3 仿真驗證與分析

為驗證基于馬爾可夫決策模型的規(guī)劃算法性能,利用MATLAB仿真軟件,在二維坐標系下進行仿真實驗。目標環(huán)境為100 km×100 km,利用柵格法將目標區(qū)域劃分為100×100個單元。環(huán)境中分布3架具有相同RCS固定翼無人機及一定數(shù)量威脅源,無人機自身約束條件如表2所示。分別在簡單和復(fù)雜環(huán)境下進行仿真實驗。依據(jù)某預(yù)研項目的作戰(zhàn)任務(wù)需求,簡單環(huán)境下,雷達威脅個數(shù)為64,威脅半徑均為2 km;復(fù)雜環(huán)境下,雷達威脅個數(shù)為64,雷達分布情況及半徑參數(shù)如表3所示。

表2 無人機自身特性約束

表3 復(fù)雜環(huán)境下雷達威脅分布及半徑參數(shù)

在簡單環(huán)境下針對多無人機單目標任務(wù)分別采用基本蟻群算法和基本MDP模型算法進行航路規(guī)劃仿真試驗。其仿真結(jié)果如圖6和表4所示。在復(fù)雜環(huán)境下針對多無人機單目標與多目標任務(wù)分別采用基本MDP模型算法和改進MDP模型算法進行航路規(guī)劃仿真試驗,其仿真結(jié)果如圖7、圖8和表5所示。圖中,UAV為無人機各自的起飛點;圖6、圖7和圖8中橫軸和縱軸分別為無人機飛行橫向和縱向范圍。

圖6 簡單環(huán)境下仿真結(jié)果圖

表4 基本蟻群算法和基本MDP模型規(guī)劃算法實驗數(shù)據(jù)

表5 基本MDP模型算法和改進MDP模型規(guī)劃算法實驗數(shù)據(jù)

圖7 單目標仿真結(jié)果圖

圖8 多目標仿真結(jié)果圖

由圖6和表2可知,在簡單環(huán)境下,采用基本MDP模型規(guī)劃算法后,航路規(guī)劃時間減少37%,航路威脅代價降低23%,航路綜合代價降低19%。由圖7、圖8以及表3可知,復(fù)雜環(huán)境下多無人機執(zhí)行單目標任務(wù)時,采用改進MDP模型規(guī)劃算法后,航路規(guī)劃時間減少46%,航路威脅代價和航路綜合代價降低25%以上。當多無人機執(zhí)行多目標任務(wù)時,采用改進MDP模型規(guī)劃算法后,航路規(guī)劃時間減少6%,航路威脅代價和航路綜合代價降低25%以上。目前仿真驗證中無人機數(shù)量最大做到100架無人機的航路規(guī)劃,無人機數(shù)量增加后,算法仍能同時為多架無人機快速規(guī)劃出合理有效的飛行路徑,但算法的計算量變大,航路規(guī)劃的時間增加了3倍。

在相同的條件下,改進后的MDP模型算法在為多無人機快速規(guī)劃出合理有效的飛行路徑的同時,也使航路威脅代價和綜合代價大大減少,保障了在復(fù)雜戰(zhàn)場態(tài)勢下無人機高效執(zhí)行任務(wù)的安全性。

4 結(jié)論

針對多無人機在復(fù)雜環(huán)境下執(zhí)行作戰(zhàn)任務(wù)時易受環(huán)境威脅影響的問題,提出一種基于改進馬爾可夫決策模型的多無人機航路規(guī)劃算法。將威脅代價與馬爾可夫模型相結(jié)合,在無模型均勻結(jié)構(gòu)的報酬函數(shù)基礎(chǔ)上引入了非均勻結(jié)構(gòu)的雷達威脅模型,建立改進馬爾可夫決策模型執(zhí)行策略搜索,為多無人機進行飛行航路規(guī)劃。仿真結(jié)果表明,基于改進馬爾可夫決策模型的多無人機航路規(guī)劃不僅能為多無人機快速規(guī)劃出合理有效的飛行路徑,也將多無人機航路的威脅代價和航路綜合代價有效降低了25%,保障了在復(fù)雜戰(zhàn)場態(tài)勢下無人機高效執(zhí)行任務(wù)的安全性。