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

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

2、,提出一種基于狀態(tài)聚類方法的HMDP(HierarchicalMarkovDecisionProcesses)模型,并將其拓展到三維規(guī)劃中.仿真實(shí)驗(yàn)證明:這種簡單的規(guī)劃模型可以有效解決UAV的三維全局路徑規(guī)劃問題,為其在實(shí)際飛行中的局部規(guī)劃奠定了基礎(chǔ).關(guān)鍵詞:無人機(jī)(UAV);路徑規(guī)劃;馬爾可夫決策過程過程(HMDP);仿真中圖分類號:TP24文獻(xiàn)標(biāo)識碼: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ī)劃作為無人機(jī)(UAV,UnmannedAerialVehicle)自主飛行的重要保障,是指依靠已知的地形(包括障礙)信息和威脅信息,在某些約束條件下,尋找到從起點(diǎn)到目標(biāo)點(diǎn)的可行飛行路線.目前,路徑規(guī)劃的研究方法很多領(lǐng)域的31-2基礎(chǔ)的模型,在這個(gè)理論框架下,可以把UAV的路徑規(guī)劃問題看作是給定環(huán)境模型和獎懲原則的情況下,尋求最優(yōu)策略的問題.針對某型UAV進(jìn)行低空超視距飛行的環(huán)境和飛機(jī)運(yùn)動特性,本文初步建立了基于MDP的全局路徑規(guī)劃模型,由于出現(xiàn)時(shí)空開銷大、航向改變頻繁的缺點(diǎn),提出一種基于狀態(tài)聚類方法的HMDP(Hierarchi

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

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

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

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

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

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

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

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

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

16、規(guī)劃的能力.將HMDP模型拓展到三維環(huán)境中(針對某型UAV進(jìn)行低空超視距飛行的環(huán)境40km40km1km),三維的空間狀態(tài)并不是立體的柵格形式,舊是一種規(guī)劃策略,一種從分層狀態(tài)的概率分布到UAV采取最佳動作的優(yōu)化匹配.劃分層次后,頂層的MDP直觀地給出了到達(dá)目標(biāo)點(diǎn)所應(yīng)走的總體路線,并且包含了UAV的當(dāng)前狀態(tài),通過這種方法摒棄了與規(guī)劃無關(guān)的狀態(tài).頂層規(guī)劃完成后,再在每一層狀態(tài)中搜索最優(yōu)路徑.同時(shí),結(jié)合高度分層,實(shí)現(xiàn)了三維路徑規(guī)劃,為UAV在實(shí)際飛行中的局部規(guī)劃奠定了基礎(chǔ).參考文獻(xiàn)(References)1張建英,劉暾.基于人工勢場法的移動機(jī)器人最優(yōu)路徑規(guī)劃J.航空學(xué)報(bào),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模型中的轉(zhuǎn)移概率和報(bào)酬函數(shù)與平面中的相同.如圖5所示,在三維環(huán)境坐標(biāo)系(X2Y2Z)下根據(jù)障礙的高度(h1h2之間),按照2.2節(jié)中的方法縱向聚類垂直面內(nèi)的狀態(tài),在這里對障礙物進(jìn)行規(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,計(jì)算這些狀態(tài)的轉(zhuǎn)移概率,并按照R進(jìn)行V(s)的計(jì)算,搜索最大報(bào)酬動作,初步得到可行狀態(tài)為S1S3S7,再在這3個(gè)狀態(tài)上最后確定最優(yōu)的3細(xì)化路徑.分層后將問題分解,避免產(chǎn)生由于數(shù)據(jù)量太大造成的維