移動機器人自動巡徑淺析

胡斐

【摘要】全局路徑規(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）.