基于馬爾可夫模型的無人機路徑規(guī)劃的線性化

【信息科學與控制工程】

基于馬爾可夫模型的無人機路徑規(guī)劃的線性化

王社偉,梁國偉,陶軍

(空軍航空大學,長春130022)

摘要：研究了利用馬爾可夫模型對無人機路徑規(guī)劃問題建模，以及馬爾可夫模型的線性化問題，提出了離散的馬爾可夫模型線性化的方法，并利用數(shù)學歸納法進行了證明。仿真結(jié)果表明，對狀態(tài)流程圖進行線性化以后，由初始狀態(tài)到終止狀態(tài)的每條路徑的狀態(tài)轉(zhuǎn)移概率變得更加直觀，能夠從狀態(tài)流程圖中清楚地得到各個因素對整個系統(tǒng)任務的影響。

關(guān)鍵詞：無人機路徑規(guī)劃；馬爾可夫模型；線性化

收稿日期：2014-08-26

作者簡介：王社偉(1965—)，男，副教授，博士，主要從事容錯控制與導航的故障診斷、可靠性分析以及飛行控制系統(tǒng)等研究;梁國偉(1989—)，男，碩士研究生，主要從事多無人機路徑規(guī)劃及任務分配研究;陶軍(1966—)，男，博士，講師，主要從事智能體控制,無人機任務規(guī)劃技術(shù)研究。

doi:10.11809/scbgxb2015.01.027

中圖分類號：V279

文章編號：1006-0707(2015)01-0095-04

本文引用格式：王社偉,梁國偉,陶軍.基于馬爾可夫模型的無人機路徑規(guī)劃的線性化[J].四川兵工學報，2015(1):95-98.

Citationformat:WANGShe-wei,LIANGGuo-wei,TAOJun.LinearizationofUAVPathPlanningBasedonMarkovModel[J].JournalofSichuanOrdnance,2015(1):95-98.

LinearizationofUAVPathPlanningBasedonMarkovModel

WANGShe-wei,LIANGGuo-wei,TAOJun

(AviationUniversityofAirForce,Changchun130022,China)

Abstract:The linearization of the markov model after building a model for Unmanned Aerial Vehicle (UAV) path planning using the markov model was discussed, and a linearization method was put forward for the discrete markov model, then we proved it by using mathematical induction. The simulation results show that the state transition probability of each path becomes more intuitive from initial state to the end state after the linearization of state flow diagram, and can get very clear impact of each factor on the entire system tasks from the flow diagram.

Keywords:UAVpathplanning;markovmodel;linearization

近年來，無人機的路徑規(guī)劃問題已經(jīng)成為無人機領(lǐng)域的一個研究熱點，是一個具有多約束條件的NP復雜問題。在戰(zhàn)場環(huán)境中，由于作戰(zhàn)的動態(tài)性和不確定性以及協(xié)同控制的復雜性，使得任務開始后會出現(xiàn)許多預先無法預料的情況，因此，良好的路徑規(guī)劃是無人機順利完成任務和發(fā)揮最大效能的保障和基礎(chǔ)。

由于戰(zhàn)場環(huán)境的連續(xù)性，建模時需要將連續(xù)的戰(zhàn)場環(huán)境離散化，其中一種方法是采用路徑圖的概念，將戰(zhàn)場環(huán)境抽象為一個圖，其節(jié)點是空間的自由點，節(jié)點之間的邊即為無碰撞的自由邊[1]。當無人機的當前位置、路徑節(jié)點和終點確定以后，可以將無人機的路徑規(guī)劃問題看成是時不變齊次的馬爾可夫鏈，其中，無人機當前位置為初始狀態(tài)，路徑節(jié)點為模型的狀態(tài)，任務終點為終止狀態(tài)。

為了分析比較不同的路徑規(guī)劃方案，常常希望能夠從狀態(tài)流程圖中更直觀地得到一些主要參數(shù)對系統(tǒng)任務的影響。因此，在狀態(tài)流程圖的化簡過程中，提出了將系統(tǒng)的馬爾可夫模型的狀態(tài)流程圖“線性化”(linearization)的概念[2]，這一概念同對控制系統(tǒng)中的非線性系統(tǒng)進行線性化是完全不同的2個概念。對系統(tǒng)馬爾可夫模型狀態(tài)流程圖的線性化是指在系統(tǒng)任務分析之前對流程圖進行化簡，盡量減少除初始狀態(tài)和終止狀態(tài)以外的中間狀態(tài)之間的交叉轉(zhuǎn)移關(guān)系。這樣盡管會使系統(tǒng)可靠性模型狀態(tài)數(shù)目增加，但不同于狀態(tài)合并的逆運算，它可以使無人機任務分析變得更加直觀方便[3]。

1線性化的基本概念

假設無人機路徑規(guī)劃的馬爾可夫模型為時不變齊次的馬爾可夫鏈[4]。圖1表示一個普通的馬爾可夫模型狀態(tài)流程圖，線性化的目的是將其化簡為和原圖等價的，其中任意一個從初始狀態(tài)到達終點吸收狀態(tài)的路徑都沒有經(jīng)過交叉轉(zhuǎn)移的狀態(tài)流程圖，如圖2所示。進行線性化的系統(tǒng)狀態(tài)流程圖須滿足以下條件[5]：

1) 只有一個初始狀態(tài)和至少一個吸收狀態(tài)；

2) 所有的狀態(tài)轉(zhuǎn)移概率都是時不變的常數(shù)；

3) 狀態(tài)之間的轉(zhuǎn)移關(guān)系均為單向的。

圖1　普通狀態(tài)流程示意圖

圖2　線性化狀態(tài)流程示意圖

為了方便后文分析問題，給出以下概念：

定義1：到達狀態(tài)流程圖中某狀態(tài)的路徑數(shù)大于1的狀態(tài)，稱為合并狀態(tài)。

定義2：狀態(tài)流程圖中某狀態(tài)可到達的其他狀態(tài)數(shù)大于1的狀態(tài)，稱為分叉狀態(tài)。

由定義1和定義2可知，在圖1中，狀態(tài)0、狀態(tài)1和狀態(tài)3是分叉狀態(tài)；狀態(tài)5和狀態(tài)F是合并狀態(tài)。在圖2中，只有初始狀態(tài)是分叉狀態(tài)，終止狀態(tài)是合并狀態(tài)。

馬爾可夫模型線性化的過程可以分為2步，即合并狀態(tài)的分解和分叉狀態(tài)的化簡。

2合并狀態(tài)的分解

如圖3所示，對合并狀態(tài)分解的方法比較直觀，其具體的方法是：在整個狀態(tài)流程圖中，將初始狀態(tài)放在左邊，終止狀態(tài)放在右邊，然后由左向右逐一將每個合并狀態(tài)分解成和其輸入路徑數(shù)相等的一些新的狀態(tài)，直到最后只有終止狀態(tài)是合并態(tài)為止。例如，在圖3中，將合并狀態(tài)A分解為和其輸入路徑數(shù)M相等的狀態(tài)X1,X2,…,XM。

圖3　合并狀態(tài)的分解

3分叉狀態(tài)的化簡

同合并狀態(tài)的分解相比，分叉狀態(tài)的線性化相對要麻煩一些。如圖4所示，在圖4(a)中，馬爾可夫模型的狀態(tài)01,02,…,0M,A,11,12,…,1N在時刻k的狀態(tài)概率分布向量為：

π(k)=[x01(k),x02(k),…,x0M(k),xA(k),

x11(k),x12(k),…,x1N(k)]

(1)

在圖4(b)中，馬爾可夫模型狀態(tài)01,02,…,0M,A1,A2,…,AN,11,12,…,1N在時刻k的狀態(tài)分布概率向量定義為：

π′(k)=[x01(k),x02(k),…,x0M(k),xA1(k),xA2(k),…,

(2)

如果圖4(b)所示模型滿足：

1) 狀態(tài)Aj的初始狀態(tài)分布概率為：

j=1,2,…,N

(3)

2) 狀態(tài)0i的狀態(tài)分布概率x0i(k)同圖4(a)所示系統(tǒng)相同，其中i=1,2,…,M。則4(a)中的分叉狀態(tài)A和圖4(b)中虛框內(nèi)所示部分是等價的。

在式(1)中，圖4(a)中的分叉狀態(tài)A為該馬爾可夫模型狀態(tài)空間中第(M+1)個狀態(tài)。根據(jù)狀態(tài)概率分布向量的定義和圖4(a)中所示的狀態(tài)轉(zhuǎn)移關(guān)系，可得狀態(tài)A在下一時刻仍保持在原狀態(tài)的概率為：

(4)

由圖4(a)可知得：

i=1,2,…,M

(5)

x1j(k+1)=λAjxA(k)+(1-λ2j)x1j(k),

j=1,2,…,N

(6)

圖4　分叉狀態(tài)的線性化示意圖

由圖4(b)可得：

i=1,2,…,M;j=1,2,…,N

(7)

j=1,2,…,N

(8)

顯然，只要證明式(6)和式(8)等價即可。首先，利用數(shù)學歸納法證明：在所示的初始條件下，對于任意的k=0,1,2,…，λAxAj(k)=λAjxA(k)恒成立。

假設當k=0時

由式(5) 、式(7)，得

(9)

(10)

其中，i=1,2,…,M; j=1,2,…,N。

所以

j=1,2,…,N

(11)

j=1,2,…,N

(12)

λAxAj(1)=λAjxA(1),j=1,2,…,N

(13)

假設當k=n時

λAxAj(n)=λAjxA(n),j=1,2,…,N

(14)

成立。

則當k=n+1時，分別由式(5) 、式(7)可得

(15)

(16)

其中，i=1,2,…,M;j=1,2,…,N。

所以

(17)

j=1,2,…,N

(18)

將式(14)代入式(17)和式(18)，得到：

λAxAj(n+1)=λAjxA(n+1),j=1,2,…,N

(19)

所以，在定理所示初始條件下，對于任意的k=0,1,2,…,λAxAj(k)=λAjxA(k)恒成立。

由上述分析可知，圖4(a)中的分叉狀態(tài)可以化簡為圖4(b)中的狀態(tài)。

4仿真實例

圖5　無人機路徑規(guī)劃示意圖

按前面所述線性化方法，可以將圖5(a)化成圖5(b)的形式，其狀態(tài)轉(zhuǎn)移概率如圖所示，每條路徑的生存概率和時間如表1所示。

表1　結(jié)果統(tǒng)計表

5結(jié)束語

將系統(tǒng)馬爾可夫模型狀態(tài)流程圖5(b)同5(a)進行比較，雖然用于無人機路徑規(guī)劃的馬爾可夫模型的狀態(tài)數(shù)目有所增加，但是分析過程要簡單直觀許多。對狀態(tài)流程圖進行線性化以后，能夠從狀態(tài)流程圖中清楚直觀地得到各個因素對整個系統(tǒng)任務的影響，可以在路徑規(guī)劃過程中有針對性地加以改進。

參考文獻：

[1]高曉靜，陳曉峰，智勇.無人機路徑規(guī)劃中的環(huán)境和威脅模型研究[J].航空計算技術(shù)，2013,43(3)：63-68.

[2]王社偉.容錯導航系統(tǒng)的可靠性分析[D].北京：北京航空航天大學，1999.

[3]PattonR,ChenJ，NielsenSB.Model-basedmethodsforfaultdiagnosis:someguide-lines[J].Trans.OnInstituteofMeasurementandControl,1995,17(2):73-83.

[4]PermanM,Senegacnik,TumaM.Semi-Markovmodelswithanapplicationtopower-plantreliabilityanalysis[J].IEEETrans.onReliability,1997,46(4):526-532.

[5]BridalO.Safetyandreliabilityanalysisofrepairablefaulttolerantsystems[J].InternationalJournalofReliability、QualityandSafetyEngineering， 1997，42(3)：327-339.

(責任編輯楊繼森)