電力線路巡檢飛行機(jī)器人三維軌跡生成方法

柳長(zhǎng)安,楊國(guó)田,吳 華,周 宏

(華北電力大學(xué) 控制與計(jì)算機(jī)工程學(xué)院, 北京102206)

軌跡生成作為電力線路巡檢飛行機(jī)器人(flying robot for overhead powerline inspection,FROPI)自主飛行的重要保障, 是指依靠已知的地形(包括障礙)信息和威脅信息, 在某些約束條件下,尋找到從起點(diǎn)到目標(biāo)點(diǎn)的可行飛行路線.目前,路徑規(guī)劃的研究方法很多[1-2],基于決策論的路徑規(guī)劃是近年來(lái)才出現(xiàn)在人工智能研究領(lǐng)域的[3],作為一種處理順序決策問(wèn)題的規(guī)劃方法,特別適合于處理不確定情況下的軌跡生成問(wèn)題.

馬爾可夫決策過(guò)程(Markov decision process ,MDP)是其中最基本的應(yīng)用模型.在這個(gè)理論框架下,可以把FROPI 的軌跡生成問(wèn)題看作是在給定環(huán)境模型和獎(jiǎng)懲原則的情況下, 尋求最優(yōu)策略的問(wèn)題.針對(duì)某型FROPI 的低空作業(yè)飛行的環(huán)境和自身運(yùn)動(dòng)特性,本文初步建立基于MDP 的全局路徑規(guī)劃模型[4] .對(duì)于FROPI 具有時(shí)空開銷大、航向改變頻繁的缺點(diǎn),提出一種基于狀態(tài)聚類方法的分層馬爾可夫決策過(guò)程(hierarchical Markov decision process ,HMDP)模型,并結(jié)合FROPI 機(jī)載巡檢設(shè)備(如攝像機(jī))的控制標(biāo)準(zhǔn),將其拓展到三維全局軌跡生成中.

1 FROPI 的MDP 模型

1 .1 MDP 模型定義

一個(gè)MDP 可以用一個(gè)四元組M=〈S,A,T,R〉描述.

S:包括所有環(huán)境狀態(tài)的有限集合.定義80 km×80 km 范圍的環(huán)境作為FROPI 路徑規(guī)劃的環(huán)境狀態(tài).規(guī)劃時(shí),基于柵格法以100 m(由實(shí)際FROPI運(yùn)動(dòng)約束決定)間隔進(jìn)行二維離散化空間建模,得到6 .4 ×105個(gè)空間狀態(tài).

A:包括所有動(dòng)作的有限集合.定義FROPI 有9個(gè)可行的動(dòng)作, 分別為北、東北、東、東南、南、西南、西、西北和懸停.

T:S×A→Π(T)是狀態(tài)轉(zhuǎn)移函數(shù),在給定目前狀態(tài)和動(dòng)作的情況下, 下一狀態(tài)的概率分布將直接決定下一動(dòng)作的輸出.這里認(rèn)為在沒(méi)有目標(biāo)時(shí)的初始狀態(tài)轉(zhuǎn)移概率是平均分配的(圖1a).以目標(biāo)點(diǎn)在正北方為例, 若給出動(dòng)作北,狀態(tài)s周圍柵格的狀態(tài)遷移概率分布如圖1b 所示, 表示給定目前狀態(tài)s和動(dòng)作北的情況下,下一狀態(tài)s′的概率分布, 已知狀態(tài)分布后,再根據(jù)相應(yīng)的報(bào)酬, 就可以得到最優(yōu)策略.需要注意的是, 這只是概率分布的一種特殊情況,分布值會(huì)隨著目標(biāo)點(diǎn)、障礙情況而變化.

圖1 狀態(tài)遷移概率分配圖Fig.1 Probability distribution figure of the state transition

R:S×A→Π(R)是報(bào)酬函數(shù),表示在給定目前狀態(tài)和動(dòng)作的情況下所期望的立即報(bào)酬(一般用R(s,a)來(lái)表示在狀態(tài)s下執(zhí)行動(dòng)作a所能得到的立即報(bào)酬).構(gòu)造無(wú)模型的均勻表示的報(bào)酬函數(shù)模型Rm和Ra分別為正常飛行和遇到障礙時(shí)的報(bào)酬函數(shù).

在這個(gè)模型中, 下一個(gè)狀態(tài)和期望獲得的立即報(bào)酬只和當(dāng)前狀態(tài)、所執(zhí)行的動(dòng)作有關(guān),而與歷史無(wú)關(guān),這就是所謂的馬爾可夫?qū)傩訹5]:t+1 時(shí)刻的狀態(tài)和報(bào)酬只依賴于t時(shí)刻的狀態(tài)和在t時(shí)刻執(zhí)行的動(dòng)作.

1.2 搜索策略

FROPI 對(duì)動(dòng)作策略進(jìn)行搜索需要考慮因素有:①必須充分探索環(huán)境狀態(tài)空間, 從而能夠找到最優(yōu)的或者次優(yōu)的策略, 即探索問(wèn)題;②要利用通過(guò)概率學(xué)習(xí)獲得的經(jīng)驗(yàn)選擇動(dòng)作,即利用問(wèn)題.二者相互矛盾.如何合理地平衡二者從而有效選擇動(dòng)作, 即為搜索策略問(wèn)題.這里采用動(dòng)態(tài)規(guī)劃, 使要搜索的那些評(píng)價(jià)函數(shù)最優(yōu), 即無(wú)限折扣報(bào)酬期望和最大的決策序列[5] ,則最優(yōu)評(píng)價(jià)函數(shù)為

式中:λ為折扣因子, 本文取0 .8 ;E(·)為期望值;R t為t時(shí)刻的立即報(bào)酬.對(duì)于任意狀態(tài), 使評(píng)價(jià)函數(shù)最優(yōu)的充要條件為[5]

式中,P為轉(zhuǎn)移概率.式(4)為Bellman 方程.相應(yīng)地,最優(yōu)策略π*為

對(duì)于Bellman 方程的解, 采用函數(shù)迭代法,即直接對(duì)最優(yōu)評(píng)價(jià)函數(shù)V*進(jìn)行搜索.設(shè)在時(shí)間步t,系統(tǒng)的狀態(tài)為s,V*(s)則按下式進(jìn)行迭代:

比較兩步連續(xù)迭代的評(píng)價(jià)函數(shù)的最大值, 如果差值小于指定的精度ε, 則結(jié)束迭代.

2 FROPI 的HMDP 模型描述

2 .1 狀態(tài)聚類

通過(guò)上文構(gòu)建狀態(tài)空間的方法,可以看到,柵格的大小影響算法的時(shí)空復(fù)雜度.柵格的規(guī)格越小,劃分環(huán)境后得到的小區(qū)域越多, 則數(shù)據(jù)所占的內(nèi)存空間越多,搜索速度就越慢.但柵格太大又將影響路徑的精確程度.本文構(gòu)造的柵格平面狀態(tài)為6 .4 ×105個(gè),如果拓展到三維空間, 時(shí)空開銷是很大的, 同時(shí)在規(guī)劃中(如圖2 所示)可以看到, FROPI 出現(xiàn)了航向頻繁變化的問(wèn)題, 規(guī)劃的轉(zhuǎn)向角度也無(wú)法在實(shí)際飛行中實(shí)現(xiàn).因此,引入狀態(tài)空間聚類的思路方法.

狀態(tài)聚類的思路方法是通過(guò)把原始狀態(tài)歸并為較小的集結(jié)狀態(tài)集合, 從而在更小維數(shù)的空間上規(guī)劃路徑.明確地說(shuō), 把環(huán)境狀態(tài)空間S劃分成m個(gè)子集S1,S2,…,Sm,S=S1∪S2∪… ∪Sm,把每個(gè)子集作為一個(gè)集結(jié)狀態(tài),進(jìn)行規(guī)劃.這樣, 迭代的次數(shù)會(huì)明顯減少,有效克服維數(shù)災(zāi)和節(jié)點(diǎn)過(guò)多的問(wèn)題.依據(jù)標(biāo)準(zhǔn)的MDP 模型進(jìn)行狀態(tài)類聚,加入分層結(jié)構(gòu).定義由MDP 組成完整的分層系統(tǒng),它們可以分別轉(zhuǎn)化成標(biāo)準(zhǔn)的MDP .重新定義四元組Mn=〈Sn,An,Tn,Rn〉,其中n代表層數(shù), 根據(jù)狀態(tài)設(shè)定.定義M0為初始的平面MDP ,當(dāng)n≥1 時(shí),Mn由Mn-1通過(guò)聚類狀態(tài)Sn-1得到,每類狀態(tài)聚類后變?yōu)橐粋€(gè)狀態(tài),在分層的過(guò)程中, 無(wú)形之間減少了空間狀態(tài)數(shù)量, 大大加快了搜索速度.

每一層上的狀態(tài)轉(zhuǎn)移概率和報(bào)酬函數(shù)與平面MDP 模型中計(jì)算方法相同,只是范圍已經(jīng)局限在所在層的狀態(tài)之間.

2.2 HMDP 模型的FROPI 路徑規(guī)劃

根據(jù)環(huán)境中的障礙信息, 進(jìn)行狀態(tài)聚類,參照文獻(xiàn)[6-8] 中的八叉樹方法,采用縱向劃分狀態(tài)層次的方法(如圖2 所示).假設(shè)環(huán)境中有復(fù)雜形狀的障礙物, 按照縱向劃分標(biāo)準(zhǔn)把初始環(huán)境狀態(tài)劃分為9個(gè)子狀態(tài), 采用迭代策略,計(jì)算每一層次狀態(tài)之間的轉(zhuǎn)移概率, 在第1 次的搜索中, 規(guī)劃的可能路徑為1 →2 →4 →6 →7 →8 →9,當(dāng)?shù)讓油瓿珊笤俜祷氐缴蠈?再次搜索時(shí)已經(jīng)摒棄了一些無(wú)關(guān)的狀態(tài), 只在底層選定的狀態(tài)中繼續(xù)尋優(yōu).在圖2 的例子中, 底層的路徑規(guī)劃實(shí)際上是路徑的粗略選擇, 頂層的規(guī)劃其實(shí)是路徑的細(xì)化和執(zhí)行過(guò)程.對(duì)比平面MDP 規(guī)劃附加多個(gè)障礙物的例子,進(jìn)行相同條件下的仿真實(shí)驗(yàn),結(jié)果如圖3 所示, 將兩種算法的性能比較由表1 列出.可以看出, 分層后的規(guī)劃路徑具有節(jié)點(diǎn)少、路徑代價(jià)小、搜索時(shí)間快等優(yōu)點(diǎn).同時(shí)減少了FROPI 的航向變化, 因此規(guī)劃更具有合理性.

圖2 HMDP 模型的狀態(tài)聚類過(guò)程Fig .2 Clustering process based on HMDP model

圖3 附加不同障礙的HMDP 規(guī)劃實(shí)驗(yàn)圖Fig .3 Path planned by HMDP with different obstacles

表1 兩種算法性能分析Tab.1 Performance of the two algorithms

3 基于HMDP 的FROPI 的三維軌跡生成方法

根據(jù)文獻(xiàn)[9] 及實(shí)驗(yàn)測(cè)試, 現(xiàn)總結(jié)出以下關(guān)于FROPI 控制的基本標(biāo)準(zhǔn):

(1)FROPI 不能太靠近障礙物, 否則會(huì)被電力線的磁場(chǎng)干擾, 或者機(jī)載設(shè)備如攝像機(jī)屏幕的大部分會(huì)被障礙物所占據(jù).

(2)FROPI 的運(yùn)動(dòng)路徑應(yīng)盡量平滑, 不平滑的路徑會(huì)讓地面觀察者覺(jué)得拍攝的畫面不夠自然.

(3)FROPI 機(jī)載攝像機(jī)的視角要穩(wěn), 屏幕中的地平線應(yīng)當(dāng)水平.這就意味著機(jī)載攝像機(jī)的固定要牢靠.

(4)FROPI 的各方向角不能劇烈變化, 如快速地左右搖擺、上下?lián)u擺.

(5)當(dāng)FROPI 需要轉(zhuǎn)彎時(shí)應(yīng)當(dāng)減速, 否則, 機(jī)載設(shè)備的屏幕中的物體移動(dòng)過(guò)快, 所成圖像會(huì)模糊不清.

(6)FROPI 機(jī)載攝像機(jī)應(yīng)該對(duì)路徑的目標(biāo)有所提示,尤其是轉(zhuǎn)彎時(shí),不能等到轉(zhuǎn)彎結(jié)束才將鏡頭對(duì)著轉(zhuǎn)彎后的方向, 而應(yīng)該事先就將視角調(diào)整到轉(zhuǎn)彎后的方向,提示FROPI 觀看接下來(lái)的動(dòng)作.

本文將問(wèn)題求解過(guò)程分為場(chǎng)景預(yù)處理階段、路徑規(guī)劃和執(zhí)行階段.在場(chǎng)景預(yù)處理階段中, 利用層次細(xì)分方法將場(chǎng)景用八叉樹表示, 之后構(gòu)建連接圖用于路徑規(guī)劃;在路徑規(guī)劃與執(zhí)行階段中, 使用IDA*[10]算法在連接圖中找出較短的路徑,經(jīng)過(guò)三步優(yōu)化后,得到一階連續(xù)的曲線軌跡.機(jī)載攝像機(jī)沿此路徑運(yùn)動(dòng)時(shí),控制攝像機(jī)的速度與視角變化, 使結(jié)果符合上述的控制標(biāo)準(zhǔn).

為了進(jìn)行避障檢測(cè), 往往需要對(duì)模型進(jìn)行簡(jiǎn)化,使用至少包含模型的基本形體作為模型的包圍盒來(lái)進(jìn)行相交測(cè)試.簡(jiǎn)化所帶來(lái)的不精確性是一般的碰撞檢測(cè)所要避免的, 但過(guò)于精確的避障檢測(cè)模型反而容易使FROPI 接近障礙.本算法使用邊長(zhǎng)為L(zhǎng)的立方體來(lái)網(wǎng)格化模型, 若網(wǎng)格中存在物體或其中存在一部分物體, 統(tǒng)稱此類網(wǎng)格為障礙網(wǎng)格;否則稱為自由網(wǎng)格.將每一個(gè)原障礙網(wǎng)格周圍的26 個(gè)網(wǎng)格都視為障礙網(wǎng)格, 經(jīng)過(guò)這樣的處理后, 只要FROPI 在自由網(wǎng)格間移動(dòng),與障礙物的距離就不會(huì)小于L,這樣可以通過(guò)調(diào)整邊長(zhǎng)L來(lái)滿足不同的安全標(biāo)準(zhǔn).

對(duì)場(chǎng)景簡(jiǎn)化之后, 事實(shí)上已經(jīng)可以把每個(gè)網(wǎng)格作為連接圖的節(jié)點(diǎn), 根據(jù)網(wǎng)格的鄰接關(guān)系構(gòu)建連接圖用于路徑規(guī)劃.但是根據(jù)文獻(xiàn)[11] ,在啟發(fā)函數(shù)相同的情況下,降低連接圖中節(jié)點(diǎn)數(shù)對(duì)于A*算法效率的提高非常重要, 所以用八叉樹來(lái)表示這個(gè)簡(jiǎn)化了的場(chǎng)景.把八叉樹的單位分為障礙單元與自由單元,FROPI 只能在自由單元中移動(dòng), 并將八叉樹所有自由單元的中心點(diǎn)作為連接圖的節(jié)點(diǎn).將計(jì)算出相鄰單元連線的長(zhǎng)度作為連接圖的邊的權(quán)值.連接圖的邊由粗線表示, 連接了相鄰的自由單元.路徑規(guī)劃即在此連接圖中找到一條路徑, 使得路徑經(jīng)過(guò)的邊的權(quán)值之和最小.

帶權(quán)圖求解最短路徑問(wèn)題最早由Dijkstra 提出的算法解決,之后Hart 等在1968 年提出了A*算法.由于標(biāo)準(zhǔn)A*算法空間復(fù)雜度太高, Korf 又將其改進(jìn)為IDA*[10],其他的改進(jìn)方法詳見(jiàn)文獻(xiàn)[11] .筆者使用IDA*算法,將當(dāng)前位置與目標(biāo)的直線距離作為啟發(fā)函數(shù),從得到的連接圖中, 找到自起點(diǎn)所在單元中心點(diǎn)到終點(diǎn)所在單元中心點(diǎn)的最短路徑, 可以得到一條自起點(diǎn)到終點(diǎn)的連通路徑.

由于這條路徑以單元中心作為節(jié)點(diǎn), 忽略了從一單元行至另一單元的其他路線, 得到的路徑并不是最短的, 甚至不能算較短的.故借鑒了可見(jiàn)圖算法中的一些思想, 做如下改進(jìn):

步驟一,對(duì)路徑P1,每次從一個(gè)單元行進(jìn)至另一單元而必然通過(guò)的2 個(gè)單元的正方形鄰接面,按穿越順序編號(hào)為G1,G2,…,Gn,將Gi(i=1, …,n)的4 個(gè)頂點(diǎn)與4 條邊的中點(diǎn)組成的點(diǎn)集稱為PGi.

步驟二,i從1 循環(huán)至n-1,將PGi的每個(gè)點(diǎn)作為起點(diǎn),PGi+1的每個(gè)點(diǎn)作為終點(diǎn), 兩兩相連, 得到一張有向連接圖.再將起點(diǎn)Q與終點(diǎn)G加入到此連接圖,然后以Q為起點(diǎn),P G1中每個(gè)點(diǎn)作為終點(diǎn),形成的連線加入到連接圖中;同理, 將PSn到G的每條連線加入到連接圖中.選擇這些點(diǎn), 是因?yàn)橥ㄟ^(guò)計(jì)算,在路徑規(guī)劃中要繞過(guò)某障礙, 最短的路徑一定經(jīng)過(guò)這個(gè)障礙的邊界.

步驟三,同樣用IDA*方法, 在此有向連接圖中搜索最短路徑, 得到路徑P2 ,由于連接圖是有向的,且節(jié)點(diǎn)限制在與P1相關(guān)的這些點(diǎn),而不是來(lái)自整個(gè)飛行空間, 所以計(jì)算P2所需要的時(shí)間很少.

步驟四,把每個(gè)路徑點(diǎn)尋找可見(jiàn)的最遠(yuǎn)路徑點(diǎn)作為下一目標(biāo).設(shè)P2 上的路徑點(diǎn)為N1 ,N2,…,N m.i從1 開始,從N m到N i+2中尋找能與N i直接相連的路徑點(diǎn), 即它們的連線不與任何障礙單元相交.若找到, 則將N i與此點(diǎn)連接起來(lái),刪除中間的路徑點(diǎn),再?gòu)拇它c(diǎn)開始繼續(xù)此算法;否則,i+1 后繼續(xù)此算法,直至N m-2,得到路徑P3.

4 基于HMDP 的FROPI 三維軌跡生成仿真實(shí)驗(yàn)

通過(guò)前面的基于MDP 規(guī)劃算法的分析與研究,已經(jīng)能夠很好地求解FROPI 的二維全局路徑規(guī)劃問(wèn)題.但是,在FROPI 的實(shí)際飛行中,必須有高度方向的運(yùn)動(dòng),且FROPI 的使命要素中可能包含不同高度的規(guī)劃信息, 即要求FROPI 具有三維規(guī)劃的能力.現(xiàn)將HMDP 模型拓展到三維環(huán)境中(為某型FROPI 的低空飛行的環(huán)境20 km ×20 km ×1 km),三維的空間狀態(tài)并不是立體的柵格形式, 考慮FROPI 的最大爬升角, 定義高度方向的柵格尺寸為20 m ,三維HMDP 模型中的轉(zhuǎn)移概率和報(bào)酬函數(shù)與平面中的相同.

如圖4 所示,在三維環(huán)境坐標(biāo)系(OX YZ)下,據(jù)障礙的高度(h1～h2),按照前面的方法,向聚類垂直面內(nèi)的狀態(tài),由于進(jìn)行規(guī)則化描述, 障礙物均表示為長(zhǎng)方體形式.

圖4 HMDP 模型的三維狀態(tài)聚類過(guò)程Fig .4 Clustering process of the three dim ensional states based on HMDP model

分層后得到的頂層規(guī)劃狀態(tài)為s1,s2,…,s7,計(jì)算這些狀態(tài)的轉(zhuǎn)移概率, 并按照R進(jìn)行V*(s)的計(jì)算,搜索最大報(bào)酬動(dòng)作, 初步得到可行狀態(tài)為s1→s3→s7.在這3 個(gè)狀態(tài)上最后確定最優(yōu)的細(xì)化路徑.分層后將問(wèn)題分解, 避免產(chǎn)生由于數(shù)據(jù)量太大造成的維數(shù)災(zāi).為了較真實(shí)地描述實(shí)際環(huán)境中規(guī)劃問(wèn)題,按照前文所述的模型, 利用Matlab 生成網(wǎng)格圖, 并附加了2 個(gè)和3 個(gè)障礙.圖5a, 5b 即為三維規(guī)劃圖,可以看出,這種簡(jiǎn)單的HMDP 模型是合理、有效的.

圖5 基于HMDP 的三維軌跡生成圖Fig .5 Three dimensional trajectory based on HMDP

5 結(jié)論

帶有層次的HMDP 模型的總體思想其實(shí)仍舊是一種規(guī)劃策略,一種從分層狀態(tài)的概率分布到FROPI采取最佳動(dòng)作的優(yōu)化匹配.劃分層次后, 頂層的MDP 直觀地給出了到達(dá)目標(biāo)點(diǎn)所應(yīng)走的總體路線,并且包含了FROPI 的當(dāng)前狀態(tài).通過(guò)這種方法, 摒棄了與規(guī)劃無(wú)關(guān)的狀態(tài).頂層規(guī)劃完成后, 再在每一層狀態(tài)中搜索最優(yōu)路徑.優(yōu)化后得到的路徑仍可能不是最優(yōu)的, 但是要在三維的形態(tài)空間中尋找到最短的路徑,完備的方法具有指數(shù)級(jí)別的復(fù)雜度.基于效率考慮, 使用本算法可以得到令人滿意的較短路徑, 并且最終路徑的轉(zhuǎn)角不多, 非常適合作為FROPI 的運(yùn)動(dòng)軌跡.同時(shí), 結(jié)合高度分層, 實(shí)現(xiàn)了三維軌跡生成,為FROPI 在實(shí)際飛行中的局部規(guī)劃奠定了基礎(chǔ).

[1] 張建英, 劉暾.基于人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃[J] .航空學(xué)報(bào), 2007, 28(S1):183.ZH ANG Jianying, LIU Tun.Optimized path planning of mobile robot based on artificial potential field [J] .Acta Aeronau tica Et Astronau tica Sinica, 2007, 28(S1):183.

[2] 孫漢昌, 朱華勇.基于概率地圖方法的無(wú)人機(jī)路徑規(guī)劃研究[J] .系統(tǒng)仿真學(xué)報(bào), 2006(11):3050.SUN Hanchang,ZH U Huayong .Study on path planning for UAV based on probabilistic roadmap method [J] .Acta Simulata Systematica Sinica, 2006(11):3050.

[3] Foka A F,Trahanias P E .Predictive au tonom ous robot navigation[C] ∥Proceedings of the IEEE/ RSJ International Conference on Intelligen t Robots and Systems.Piscataway ,NJ:IE EE,2002:490-495.

[4] 洪曄, 房建成.基于H MDP 的無(wú)人機(jī)三維路徑規(guī)劃[J] .北京航空航天大學(xué)學(xué)報(bào), 2009, 35(1):100.H ONG Ye, FANG Jiancheng .Hierarchical Markov decision processes based path planning for UAV in three-dim ensional environment[J] .Jou rnal of Beijing University of Aeronautics and Astronau tics, 2009, 35(1):100.

[5] Baker B,Zivkovic Z,Krose B,et al.Hierarchical dynamic prog ramming for robot path planning[C] ∥Proceedings of the 2001 IEEE International C onference on Robotics &Automation.Orleans:IEE E,2002:46-50.

[6] 史紅兵, 張毅彬, 童若鋒, 等.虛擬場(chǎng)景自動(dòng)漫游的路徑規(guī)劃算法[J] .計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 4(18):592.SHI Hongbing,ZHANG Yibin, TONG Ruofeng,et al.Path planning for automated navigation in virtual environment[J] .Journal of Computer-Aided Design & Computer Graphics,2006, 4(18):592.

[7] Salom on B,Garber M.Interactive navigation in complex environment using path planning [C] ∥Proceeding s of Symposium on Interactive 3D Graphics.Monterey :A ssociation for Computing Machinery,2003:41-50.

[8] Peters B, Dziugys A .Numerical simulation of the motion of granular material using object oriented techniques [J] .Computer Methods in Applied Mechanics and Engineering ,2002, 5(3):193.

[9] Nieuw enhuisen D,Overmars M.Motion planning for camera movements in virtual environments [M] .Utrecht :Utrecht University,UUCS220032004, 2003.

[10] Korf R E .Depth2first iterative deepening :an optimal admissible tree search [J] .Artificial Intelligence,1985, 27(1):97.

[11] Russell Stuart,Norvig Peter .Artificial intelligence :a modern approach[M] .Englew ood Cliffs, NJ:P rentice Hall, 1995.92-110.