胡斐
【摘要】全局路徑規(guī)劃則是智能移動機器人開發(fā)的重要環(huán)節(jié)之一。文章對幾種常用路徑規(guī)劃方法進(jìn)行了分析,提出了改進(jìn)的A*angle算法,并通過仿真實驗證明了改進(jìn)A*算法進(jìn)行全局路徑規(guī)劃的有效性。
【關(guān)鍵詞】全局路徑規(guī)劃 移動機器人 A*angle算法 全局地圖建模 四又樹建模
全局路徑規(guī)劃技術(shù)是移動機器人學(xué)研究領(lǐng)域中一個重要的部分,機器人路徑規(guī)劃就是依據(jù)某個或某些優(yōu)化標(biāo)準(zhǔn),在空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)路徑,因而路徑規(guī)劃問題又可以稱為避碰規(guī)劃問題。本文對全局路徑規(guī)劃進(jìn)行了研究,并設(shè)計了一種基于腫angle算法的全局路徑規(guī)劃實驗,驗證算法的可行性。
一、全局路徑規(guī)劃分析
路徑規(guī)劃包含如下方面z在移動障礙物之間計算出無碰路徑:獲取物體之間的精確關(guān)系:分析基于傳感信息所做的運動策略的不穩(wěn)定性:處理物理模型的特性以及機器人對物體的抓取。
路徑規(guī)劃用數(shù)學(xué)語言可描述為:C為一個機器人,W就是機器人C的工作空間,定義為RN,N=2或3:設(shè)B1川Bq是空間W中分布的靜態(tài)障礙物。如果C..,Bq的幾何特性以及B;的位置己知的話。機器人C在W中從起始點到目標(biāo)點并且不碰到B,的一系列連續(xù)的線段就是C的運動規(guī)劃問題。
(一)路徑規(guī)劃的分類及現(xiàn)狀
從到目前為止的研究來看,移動機器人路徑規(guī)劃方法主要可以分為以下三種類型:
1.基于事例的學(xué)習(xí)規(guī)劃方法。基于事例的學(xué)習(xí)規(guī)劃方法依靠過去的經(jīng)驗進(jìn)行學(xué)習(xí)及問題求解,一個新的事例可以通過修改事例庫中與當(dāng)前情況相似的舊的事例來獲得。將其應(yīng)用于移動機器人的路徑規(guī)劃中可以描述為:首先,利用路徑規(guī)劃所用到的或己產(chǎn)生的信息建立一個事例庫,庫中的任一事例包含每一次規(guī)劃時的環(huán)境信息和路徑信息,這些事例可以通過特定的索引取得:隨后,將由當(dāng)前規(guī)劃任務(wù)和環(huán)境信息產(chǎn)生的事例與事例庫中的事例進(jìn)行匹配,以尋找出一個最優(yōu)匹配事例,然后對該事例進(jìn)行修正,并以此作為最后的結(jié)果。
2.基于環(huán)境模型的規(guī)劃方法。該方法首先需要建立一個關(guān)于機器人運動環(huán)境的環(huán)境模型。在很多時候由于移動機器人的工作環(huán)境具有不確定性(包括非結(jié)構(gòu)性、動態(tài)性等),使得移動機器人無法建立全局環(huán)境模型,而只能根據(jù)傳感器信息實時地建立局部環(huán)境模型,因此局部模型的實時性、可靠性成為影響移動機器人是否可以安全、連續(xù)、平穩(wěn)運動的關(guān)鍵。環(huán)境建模的方法基本上可以分為兩類:網(wǎng)絡(luò)/圖建模方法、基于網(wǎng)格的建模方法。前者主要包括自由空間法、頂點圖像法、廣義錐法等,利用它們在進(jìn)行路徑規(guī)劃時可得到比較精確的解,但所耗費的計算量相當(dāng)大,不適合于實際的應(yīng)用。而后者在實現(xiàn)上要簡單許多,所以應(yīng)用比較廣泛,其典型代表就是四叉樹建模法及其擴展算法(如基于位置碼四叉樹建模法、Framed-quad trees建模法等)。
3.基于行為的路徑規(guī)劃方法?;谛袨榈姆椒ㄓ葿rooks在他著名的包容式結(jié)構(gòu)中建立,它是一門從生物系統(tǒng)收到啟發(fā)而產(chǎn)生的用來設(shè)計自主機器人的技術(shù),它采用類似動物進(jìn)化的自底向上的原理體系,嘗試從簡單的智能體來建立-個復(fù)雜的系統(tǒng)。將其用于解決移動機器人路徑規(guī)劃問題是一種新的發(fā)展趨勢,它把導(dǎo)航問題分解為許多相對獨立的行為單元,比如跟蹤、避碰、目標(biāo)制導(dǎo)等。這些行為單元是一些由傳感器和執(zhí)行器組成的完整的運動控制單元,具有相應(yīng)的軍航功能,各行為單元所采用的行為方式各不相同,這些單元通過相互協(xié)調(diào)工作來完成導(dǎo)航任務(wù)。
(二)常用的路徑規(guī)劃算法
Dijkstra算法是由荷蘭數(shù)學(xué)家E.W.Dijkstra于1959年提出的一種適用于非負(fù)權(quán)值網(wǎng)絡(luò)的單源最短路算法,是目前求解最短路問題的理論上最完備、應(yīng)用最廣的經(jīng)典算法,它可以給出從指定結(jié)點到圖中所有其他結(jié)點的最短路徑。
A*算法,啟發(fā)式搜索(Heuristic Search)是基于知識的搜索策略,即從初始狀態(tài)和當(dāng)前狀態(tài)到目標(biāo)狀態(tài)搜索時具有與步驟數(shù)或費用相關(guān)的信息。該搜索法包括最佳優(yōu)先搜索、存儲界限搜索和迭代漸近算法,如:爬山搜索和模擬方法等。
Floyd算法又稱插點法,是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。Floyd算法是在1962年由Floyd提出的。它可以直接求出圖中所有頂點對之間的最短路徑和最短路徑長度。
(三)全局地圖建模方法
全局規(guī)劃的第一步就是要建立全局地圖,其構(gòu)建方法分為自由空間法和構(gòu)造空間法。構(gòu)造空間又進(jìn)一步劃分為可視圖法(Visibility Graph)、沃羅諾伊圖法(Voronoi Diagram)和柵格法(Grids)。
本文采用柵格法構(gòu)建地圖,并運用四叉樹方法是對柵格法的改進(jìn),考慮移動機器人系統(tǒng)運行在一個平面正方形區(qū)域內(nèi)(若不滿足,可以對原來平面做拓展,并把拓展部分設(shè)置為障礙區(qū)域),基于位置碼的四叉樹法把環(huán)境劃分為2n*2n個基本元素。每個基本元素的形狀也是正方形,其邊長不小于機器人的步長。基本元素的取值為0或1,0表示自由區(qū)域,1表示障礙區(qū)域或包含障礙的區(qū)域。然后模型遞歸地把環(huán)境分為4個大小相等的子區(qū)域,直到每個區(qū)域中所包含的基本元素全為0或全為lo
四叉樹模型的圖形表達(dá)中,用黑結(jié)點表示障礙區(qū)域,用白結(jié)點表示自由區(qū)域,這兩類結(jié)點均為葉子結(jié)點:非葉子結(jié)點則可以使用灰結(jié)點表示,該結(jié)點可以一進(jìn)步遞歸分解。
二、改進(jìn)的A*算法
Mangle是對啟發(fā)式算法腫的改進(jìn):
1.用后向鏈表代替了原始A*算法中的Closed歹Ll表,在實現(xiàn)過程中主要是多定義了父親節(jié)點這樣一個變量,按照指針指向就可以找到路徑。優(yōu)化了路徑鏈表。
2.在啟發(fā)式函數(shù)上,我們不再用Manhattan函數(shù)來計算距離,而是改用最佳柵格距離來表示。所謂最佳柵格距離是指機器人遵循柵格移動準(zhǔn)則限制下的理想最小距離。更一般化的h(町,sz)=Mi舊(欲,今)+0.4142×Min(dx,dy)。
3.在原始A*算法的基礎(chǔ)上,對其評估函數(shù)進(jìn)行了改進(jìn),加入了轉(zhuǎn)向角度和轉(zhuǎn)次數(shù)這兩個約束條件:f(n)=W1×/+w2×α+W3×n。在編程過程中需建立兩個列表Vfather和OPEN,其中Vfather列表以存放被擴展的節(jié)點n,OPEN列表中存放待擴展的節(jié)點,且在OPEN中啟發(fā)式函數(shù)f最小的節(jié)點始終在表尾,以便每次擴展后建立的后項列表總是指向f值最小的方向。
三、仿真實驗結(jié)果
環(huán)境地圖被構(gòu)造成柵格地圖,符號“0”所在柵格表示障礙物所在位置:符號“口”所在柵格為起始節(jié)點:符號“V”所在柵格表示目標(biāo)節(jié)點:空白柵格表示可穿越地區(qū),將柵格數(shù)據(jù)表示為以Morton碼為下標(biāo)一的維數(shù)組。
參考文獻(xiàn):
[1]許心德.環(huán)境部分未知情況下的服務(wù)機器人導(dǎo)航研究[D].中國科學(xué)技術(shù)大學(xué),2009.
[2]陳西博.家庭環(huán)境只能空間中服務(wù)機器人導(dǎo)航技術(shù)研究[D].山東大學(xué),2010.
[3]嚴(yán)蔚敏,吳偉民數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2002.
[4]P.E.Hart,N.J.Nilsson,B.Raphael.A Formal Basis for the Heuristic Detenninations of Minimum Cost PathsW. IEEE Trans Syst Cybemetics, 1968,4 (2).
[5]Floyd R W.Algorithm 97:Shortet Path. Communica-tions oftheACM,1962,5 (6).