基于HMDP的無人機三維路徑規(guī)劃

1、2009年1月第35卷第1期北京航空航天大學學報JournalofBeijingUniversityofAeronauticsandAstronauticsJanuary2009Vol.35No11基于HMDP的無人機三維路徑規(guī)劃洪曄房建成(北京航空航天大學儀器科學與光電工程學院,北京100191)摘要:路徑規(guī)劃是UAV(UnmannedAerialVehicle)自主飛行的重要保障.初步建立了基于MDP(MarkovDecisionProcesses)的全局路徑規(guī)劃模型,把UAV的路徑規(guī)劃看作是給定環(huán)境模型和獎懲原則的情況下,尋求最優(yōu)策略的問題;為解決算法時空開銷大、UAV航向改變頻繁的缺點

2、,提出一種基于狀態(tài)聚類方法的HMDP(HierarchicalMarkovDecisionProcesses)模型,并將其拓展到三維規(guī)劃中.仿真實驗證明:這種簡單的規(guī)劃模型可以有效解決UAV的三維全局路徑規(guī)劃問題,為其在實際飛行中的局部規(guī)劃奠定了基礎.關鍵詞:無人機(UAV);路徑規(guī)劃;馬爾可夫決策過程過程(HMDP);仿真中圖分類號:TP24文獻標識碼:A文章號:)0120100204HieravdecisionprocessesbasedpathplanningforUAVinthree2dimensionalenvironmentHongYeFangJiancheng(SchoolofI

3、nstrumentScienceandOpto2electronicsEngineering,BeijingUniversityofAeronauticsandAstronautics,Beijing100191,China)Abstract:Theabilityofpathplanningisanimportantensureforunmannedaerialvehicle(UAV)inau2tonomousflight.ApathplanningmodelwasbasedonMarkovdecisionprocesses(MDP),inwhichtheprob2lemofpathplann

4、ingwasregardedaslookingforthebesttacticthroughthemodelofenvironmentandtheprin2cipleofrewardsandpunishment.Tosolvetheproblemsuchashugespace2timespendingandchangingcourseathighfrequency,thehierarchicalMarkovdecisionprocesses(HMDP)wereintroducedbasedonthemethodofclusteringstates.Thearithmeticwasalsouse

5、dforpathplanninginthree2dimensionalenvironment.There2sultsofsimulationshowtheHMDPmodelcanbeusedtopathplanningforUAVinthree2dimensionalenviron2ment.Itlaysthefoundationforlocalpathplanninginrealflight.Keywords:unmannedaerialvehicle(UAV);pathplanning;Markovdecisionprocesses(MDP);hier2archicalMarkovdeci

6、sionprocesses(HMDP);simulation路徑規(guī)劃作為無人機(UAV,UnmannedAerialVehicle)自主飛行的重要保障,是指依靠已知的地形(包括障礙)信息和威脅信息,在某些約束條件下,尋找到從起點到目標點的可行飛行路線.目前,路徑規(guī)劃的研究方法很多領域的31-2基礎的模型,在這個理論框架下,可以把UAV的路徑規(guī)劃問題看作是給定環(huán)境模型和獎懲原則的情況下,尋求最優(yōu)策略的問題.針對某型UAV進行低空超視距飛行的環(huán)境和飛機運動特性,本文初步建立了基于MDP的全局路徑規(guī)劃模型,由于出現(xiàn)時空開銷大、航向改變頻繁的缺點,提出一種基于狀態(tài)聚類方法的HMDP(Hierarchi

7、calMarkovDecisionProcess)模型,并將其拓展到三維全局規(guī),基于決策論的路徑規(guī)劃是近年來才出現(xiàn)在人工智能研究,作為一種處理順序決策問題的規(guī)劃方法,特別適合于處理不確定情況下的規(guī)劃問題.MDP(MarkovDecisionProcess)則是其中應用最為劃中.收稿日期:2008202228基金項目:國家自然科學基金重點資助項目(60736025);國防基礎科研重點資助項目(D1210060013)作者簡介:洪曄(1979-),女,黑龍江哈爾濱人,講師,hongye.第1期洪曄等:基于HMDP的無人機三維路徑規(guī)劃1011平面MDP模型描述1.1MDP模型定義刻的狀態(tài)和報酬只依賴

8、于t時刻的狀態(tài)和在t時刻執(zhí)行的動作.1.2搜索策略UAV對動作策略進行搜索需要考慮因素:一個MDP可以用一個四元組M=S,A,T,4R描述:S:指包括所有環(huán)境狀態(tài)的有限集合.定義必須對環(huán)境狀態(tài)空間作充分的探索,從而能夠找到最優(yōu)的或者次優(yōu)的策略,即探索問題;要利用通過概率學習獲得的經驗進行動作選擇,即利用問題.兩者相互矛盾,如何合理地平衡兩者進行有效的動作選擇,即搜索策略問題.本文采用動態(tài)規(guī)劃,使要搜索的那些評價函數(shù)最優(yōu),即無限折扣5報酬期望和最大的決策序列,最優(yōu)評價函數(shù)為V340km40km范圍的環(huán)境作為UAV路徑規(guī)劃的環(huán)境狀態(tài).規(guī)劃時,基于柵格法以100m(由實際無人機運動約束決定)間隔進行

9、二維離散化空間5建模,得到1.610個空間狀態(tài).A:指包括所有動作的有限集合.定義UAV有8個可行的動作,分別為:北、東北、東、東南、南、西南、西和西北.(T)是狀態(tài)轉移函數(shù),在給定目T:SA前狀態(tài)和動作的情況下,直接決定下一動作的輸出.:,s周1b所示,表示給定目前狀態(tài)s,下一狀態(tài)s的概率分布,已知狀態(tài)分布后,再根據(jù)相應的報酬,就可以得到最優(yōu)策略.需要注意的是,這只是概率分布的一種特殊情況,分布值會隨著目標點、障礙情況發(fā)生變化.(s)=R=0t(3),0.9;E()為期望;t.對于任意狀態(tài),使評V3a5(s)=mR(s,a)+(4)3P(s)|s,a)V(ssS式中,P為轉移概率.式(4)為

10、Bellman方程.相應3地,最優(yōu)策略為3(s)=argmR(s,a)+a3P(s)|s,a)V(ssS(5)對于Bellman方程的解,采用函數(shù)迭代法,即3直接對最優(yōu)評價函數(shù)V進行搜索.設在時間步t,3系統(tǒng)的狀態(tài)為s,V(s)則按下式進行迭代:a初始狀態(tài)轉移概率b狀態(tài)遷移概率分布Vt+1(s)=mR(s,a)+a圖1狀態(tài)遷移概率分配圖P(s)|s,a)Vt(ssS(6)(R)是報酬函數(shù),表示在給定目R:SA前狀態(tài)和動作的情況下所期望的立即報酬(一般用R(s,a)來表示在狀態(tài)s下執(zhí)行動作a所能得到的立即報酬).這里構造無模型的均勻表示的報酬函數(shù)模型Rm和Ra:二者分別為正常飛行和遇到障礙時的報

11、酬函數(shù)值.5趨向目標(1)Rm-1遠離目標發(fā)生碰撞5遠離障礙(2)Ra=-5沒有遠離障礙0沒有障礙在這個模型中,下一個狀態(tài)和期望獲得的立即報酬只和當前狀態(tài)、所執(zhí)行的動作有關,而與歷5史無關,這就是所謂的馬爾可夫屬性:t+1時-10對兩步連續(xù)迭代的評價函數(shù)的最大值進行比較,如果其差值小于指定的精度,則結束迭代過程.1.3平面MDP模型下的二維路徑規(guī)劃為了測試基于MDP模型的規(guī)劃算法的性能,在各種復雜環(huán)境中,利用VC+6.0編程,在平面環(huán)境坐標系(X2Y)下進行了附加不同障礙的規(guī)劃仿真實驗,結果如圖2.a小型障礙物b梳狀障礙物圖2附加不同障礙的MDP規(guī)劃實驗圖102北京航空航天大學學報2009年2

12、平面HMDP模型描述2.1狀態(tài)聚類關的狀態(tài),只在底層選定的狀態(tài)中繼續(xù)尋優(yōu).在圖3的例子中,在底層的路徑規(guī)劃實際上是路徑的粗略選擇,在頂層的規(guī)劃其實是路徑的細化和執(zhí)行過程.通過上文構建狀態(tài)空間的方法,可以看到,柵格的大小影響著算法的時空復雜度.柵格的規(guī)格越小,劃分環(huán)境后得到的小區(qū)域越多,則數(shù)據(jù)所占的內存空間越多,搜索時速度也就越慢.但是柵格太大又將影響路徑的精確程度.這里構造的平面狀態(tài)為1.610個,如果拓展到三維空間,時空開銷是很大的,同時在規(guī)劃中(圖2)可以看到UAV出現(xiàn)了航向頻繁變化的問題,規(guī)劃的轉向角度也無法在實際飛行中實現(xiàn).因此引入狀態(tài)空間聚類的思想.狀態(tài)聚類的思想是通過把原始狀態(tài)歸并

13、為較小的集結狀態(tài)集合,行路徑規(guī)劃,明確地說,m個子集:S1,S2,Sm,SS1m,這樣迭,多的問題.依據(jù)標準的MDP模型進行狀態(tài)類聚,加入分層結構.定義由MDP組成完整的分層系統(tǒng),它們5可以分別轉化成標準的MDP.重新定義四元組M=S,A,T,R,其中n代表層數(shù),根據(jù)狀態(tài)nnnnn5圖3HMDP模型的狀態(tài)聚類過程對比平面MDP,4所示.比4,1列.、路徑、搜索時間快等優(yōu)點.同時減少了UAV的航向變化,因此規(guī)劃更具有合理性.設定.定義M為初始的平面MDP,當n1時,Mn-1n-1由M通過聚類狀態(tài)S得到,每類狀態(tài)聚類后變?yōu)橐粋€狀態(tài),在分層的過程中,無形之間減少了空間狀態(tài)數(shù)量,大大加快了搜索速度.對

14、于四元組的其他變量作如下定義:nnnnT=P(sm|sk,a),為在第n層上由狀態(tài)sk轉移到狀態(tài)sm的概率;R=R(sm,a,sk),為在第n層上由狀態(tài)sk轉nnnnnn0na小型障礙物b梳狀障礙物移到狀態(tài)sm所得到的報酬;每一層上的狀態(tài)轉移概率和報酬函數(shù)與平面MDP模型中計算方法相同,只是范圍已經被局限在所在層的狀態(tài)之間進行.2.2基于HMDP模型的二維路徑規(guī)劃根據(jù)環(huán)境中的障礙信息,進行狀態(tài)聚類,參照文獻6-8中的八叉樹方法,采用縱向劃分狀態(tài)層次的方法,如圖3所示.假設環(huán)境中有復雜形狀的障礙物,按照縱向劃分標準把初始環(huán)境狀態(tài)劃分為10個子狀態(tài),采用迭代策略,計算每一層次狀態(tài)之間的轉移概率,在

15、第1次的搜索中規(guī)劃的可能路徑為12468910,當?shù)讓油瓿珊笤俜祷氐缴蠈?再次搜索時已經摒棄了一些無n圖4附加不同障礙的HMDP規(guī)劃實驗圖表1不同算法性能分析實驗方法附加小型障礙附加梳狀障礙MDPHMDPMDPHMDP規(guī)劃時間/ms9060165101描述路徑結點數(shù)8584路徑代價854706143210203基于HMDP模型三維路徑規(guī)劃通過前面的基于MDP規(guī)劃算法的分析與研究,已經能夠很好地求解UAV的二維全局路徑規(guī)劃問題.但是,在UAV的實際飛行中,必須有高度第1期洪曄等:基于HMDP的無人機三維路徑規(guī)劃103方向的運動,且UAV的使命要素中可能包含不同高度的規(guī)劃信息,即要求UAV具有三維

16、規(guī)劃的能力.將HMDP模型拓展到三維環(huán)境中(針對某型UAV進行低空超視距飛行的環(huán)境40km40km1km),三維的空間狀態(tài)并不是立體的柵格形式,舊是一種規(guī)劃策略,一種從分層狀態(tài)的概率分布到UAV采取最佳動作的優(yōu)化匹配.劃分層次后,頂層的MDP直觀地給出了到達目標點所應走的總體路線,并且包含了UAV的當前狀態(tài),通過這種方法摒棄了與規(guī)劃無關的狀態(tài).頂層規(guī)劃完成后,再在每一層狀態(tài)中搜索最優(yōu)路徑.同時,結合高度分層,實現(xiàn)了三維路徑規(guī)劃,為UAV在實際飛行中的局部規(guī)劃奠定了基礎.參考文獻(References)1張建英,劉暾.基于人工勢場法的移動機器人最優(yōu)路徑規(guī)劃J.航空學報,2007,28(S1):1

17、83-188ZhangJianying,LiuTun.tipathplanningofmobilero2botonJ.ActaAeronauticaetstr):183-188(inChinese),.,2006(11):3050-3054SunHanchang,ZhuHuayong.StudyonpathplanningforUAVbasedonprobabilisticroadmapmethodJ.JournalofSystemSimulation,2006(11):3050-3054(inChinese)3FokaAF,TrahaniasPE.Predictiveautonomousro

18、botnaviga2tionC/ProceedingsoftheIEEE/RSJInternationalConfer2enceonIntelligentRobotsandSystems.Piscataway,NJ:IEEE,考慮UAV的最大爬升角,定義高度方向的柵格尺寸為50m,三維HMDP模型中的轉移概率和報酬函數(shù)與平面中的相同.如圖5所示,在三維環(huán)境坐標系(X2Y2Z)下根據(jù)障礙的高度(h1h2之間),按照2.2節(jié)中的方法縱向聚類垂直面內的狀態(tài),在這里對障礙物進行規(guī)則化描述,均表示為長方體形式.圖5HMDP模型的三維狀態(tài)聚類過程2002:490-4954RoyN,BurgardW,Fox

19、D,etal.Coastalnavigationmobilero2botnavigationwithuncertaintyindynamicenvironmentsC/IEEEInternationalConferenceonRoboticsandAutomation.Pittsburgh:s.n.,1999,5(1):35-405BakerB,ZivkovicZ,KroseB,etal.Hierarchicaldynamicpro2grammingforrobotpathplanningC/Proceedingsofthe2001IEEEInternationalConferenceonRobotics&Automation.Orle2ans:IEEE,2002,3(2):46-506史紅兵,張毅彬,童若鋒,等.虛擬場景自動漫游的路徑規(guī)劃分層后得到的頂層規(guī)劃狀態(tài)為S1,S2,S7,計算這些狀態(tài)的轉移概率,并按照R進行V(s)的計算,搜索最大報酬動作,初步得到可行狀態(tài)為S1S3S7,再在這3個狀態(tài)上最后確定最優(yōu)的3細化路徑.分層后將問題分解,避免產生由于數(shù)據(jù)量太大造成的維