移動(dòng)機(jī)器人自動(dòng)巡徑淺析

胡斐

【摘要】全局路徑規(guī)劃則是智能移動(dòng)機(jī)器人開(kāi)發(fā)的重要環(huán)節(jié)之一。文章對(duì)幾種常用路徑規(guī)劃方法進(jìn)行了分析，提出了改進(jìn)的A*angle算法，并通過(guò)仿真實(shí)驗(yàn)證明了改進(jìn)A*算法進(jìn)行全局路徑規(guī)劃的有效性。

【關(guān)鍵詞】全局路徑規(guī)劃 移動(dòng)機(jī)器人 A*angle算法 全局地圖建模 四又樹(shù)建模

全局路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人學(xué)研究領(lǐng)域中一個(gè)重要的部分，機(jī)器人路徑規(guī)劃就是依據(jù)某個(gè)或某些優(yōu)化標(biāo)準(zhǔn)，在空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)路徑，因而路徑規(guī)劃問(wèn)題又可以稱為避碰規(guī)劃問(wèn)題。本文對(duì)全局路徑規(guī)劃進(jìn)行了研究，并設(shè)計(jì)了一種基于腫angle算法的全局路徑規(guī)劃實(shí)驗(yàn)，驗(yàn)證算法的可行性。

一、全局路徑規(guī)劃分析

路徑規(guī)劃包含如下方面z在移動(dòng)障礙物之間計(jì)算出無(wú)碰路徑：獲取物體之間的精確關(guān)系：分析基于傳感信息所做的運(yùn)動(dòng)策略的不穩(wěn)定性：處理物理模型的特性以及機(jī)器人對(duì)物體的抓取。

路徑規(guī)劃用數(shù)學(xué)語(yǔ)言可描述為：C為一個(gè)機(jī)器人，W就是機(jī)器人C的工作空間，定義為RN，N=2或3：設(shè)B1川Bq是空間W中分布的靜態(tài)障礙物。如果C..，Bq的幾何特性以及B;的位置己知的話。機(jī)器人C在W中從起始點(diǎn)到目標(biāo)點(diǎn)并且不碰到B，的一系列連續(xù)的線段就是C的運(yùn)動(dòng)規(guī)劃問(wèn)題。

（一）路徑規(guī)劃的分類及現(xiàn)狀

從到目前為止的研究來(lái)看，移動(dòng)機(jī)器人路徑規(guī)劃方法主要可以分為以下三種類型：

1.基于事例的學(xué)習(xí)規(guī)劃方法。基于事例的學(xué)習(xí)規(guī)劃方法依靠過(guò)去的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)及問(wèn)題求解，一個(gè)新的事例可以通過(guò)修改事例庫(kù)中與當(dāng)前情況相似的舊的事例來(lái)獲得。將其應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃中可以描述為：首先，利用路徑規(guī)劃所用到的或己產(chǎn)生的信息建立一個(gè)事例庫(kù)，庫(kù)中的任一事例包含每一次規(guī)劃時(shí)的環(huán)境信息和路徑信息，這些事例可以通過(guò)特定的索引取得：隨后，將由當(dāng)前規(guī)劃任務(wù)和環(huán)境信息產(chǎn)生的事例與事例庫(kù)中的事例進(jìn)行匹配，以尋找出一個(gè)最優(yōu)匹配事例，然后對(duì)該事例進(jìn)行修正，并以此作為最后的結(jié)果。

2.基于環(huán)境模型的規(guī)劃方法。該方法首先需要建立一個(gè)關(guān)于機(jī)器人運(yùn)動(dòng)環(huán)境的環(huán)境模型。在很多時(shí)候由于移動(dòng)機(jī)器人的工作環(huán)境具有不確定性（包括非結(jié)構(gòu)性、動(dòng)態(tài)性等），使得移動(dòng)機(jī)器人無(wú)法建立全局環(huán)境模型，而只能根據(jù)傳感器信息實(shí)時(shí)地建立局部環(huán)境模型，因此局部模型的實(shí)時(shí)性、可靠性成為影響移動(dòng)機(jī)器人是否可以安全、連續(xù)、平穩(wěn)運(yùn)動(dòng)的關(guān)鍵。環(huán)境建模的方法基本上可以分為兩類：網(wǎng)絡(luò)/圖建模方法、基于網(wǎng)格的建模方法。前者主要包括自由空間法、頂點(diǎn)圖像法、廣義錐法等，利用它們?cè)谶M(jìn)行路徑規(guī)劃時(shí)可得到比較精確的解，但所耗費(fèi)的計(jì)算量相當(dāng)大，不適合于實(shí)際的應(yīng)用。而后者在實(shí)現(xiàn)上要簡(jiǎn)單許多，所以應(yīng)用比較廣泛，其典型代表就是四叉樹(shù)建模法及其擴(kuò)展算法（如基于位置碼四叉樹(shù)建模法、Framed-quad trees建模法等）。

3.基于行為的路徑規(guī)劃方法。基于行為的方法由Brooks在他著名的包容式結(jié)構(gòu)中建立，它是一門從生物系統(tǒng)收到啟發(fā)而產(chǎn)生的用來(lái)設(shè)計(jì)自主機(jī)器人的技術(shù)，它采用類似動(dòng)物進(jìn)化的自底向上的原理體系，嘗試從簡(jiǎn)單的智能體來(lái)建立-個(gè)復(fù)雜的系統(tǒng)。將其用于解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題是一種新的發(fā)展趨勢(shì)，它把導(dǎo)航問(wèn)題分解為許多相對(duì)獨(dú)立的行為單元，比如跟蹤、避碰、目標(biāo)制導(dǎo)等。這些行為單元是一些由傳感器和執(zhí)行器組成的完整的運(yùn)動(dòng)控制單元，具有相應(yīng)的軍航功能，各行為單元所采用的行為方式各不相同，這些單元通過(guò)相互協(xié)調(diào)工作來(lái)完成導(dǎo)航任務(wù)。

（二）常用的路徑規(guī)劃算法

Dijkstra算法是由荷蘭數(shù)學(xué)家E.W.Dijkstra于1959年提出的一種適用于非負(fù)權(quán)值網(wǎng)絡(luò)的單源最短路算法，是目前求解最短路問(wèn)題的理論上最完備、應(yīng)用最廣的經(jīng)典算法，它可以給出從指定結(jié)點(diǎn)到圖中所有其他結(jié)點(diǎn)的最短路徑。

A*算法，啟發(fā)式搜索（Heuristic Search）是基于知識(shí)的搜索策略，即從初始狀態(tài)和當(dāng)前狀態(tài)到目標(biāo)狀態(tài)搜索時(shí)具有與步驟數(shù)或費(fèi)用相關(guān)的信息。該搜索法包括最佳優(yōu)先搜索、存儲(chǔ)界限搜索和迭代漸近算法，如：爬山搜索和模擬方法等。

Floyd算法又稱插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。Floyd算法是在1962年由Floyd提出的。它可以直接求出圖中所有頂點(diǎn)對(duì)之間的最短路徑和最短路徑長(zhǎng)度。

（三）全局地圖建模方法

全局規(guī)劃的第一步就是要建立全局地圖，其構(gòu)建方法分為自由空間法和構(gòu)造空間法。構(gòu)造空間又進(jìn)一步劃分為可視圖法（Visibility Graph）、沃羅諾伊圖法（Voronoi Diagram）和柵格法（Grids）。

本文采用柵格法構(gòu)建地圖，并運(yùn)用四叉樹(shù)方法是對(duì)柵格法的改進(jìn)，考慮移動(dòng)機(jī)器人系統(tǒng)運(yùn)行在一個(gè)平面正方形區(qū)域內(nèi)（若不滿足，可以對(duì)原來(lái)平面做拓展，并把拓展部分設(shè)置為障礙區(qū)域），基于位置碼的四叉樹(shù)法把環(huán)境劃分為2n*2n個(gè)基本元素。每個(gè)基本元素的形狀也是正方形，其邊長(zhǎng)不小于機(jī)器人的步長(zhǎng)。基本元素的取值為0或1，0表示自由區(qū)域，1表示障礙區(qū)域或包含障礙的區(qū)域。然后模型遞歸地把環(huán)境分為4個(gè)大小相等的子區(qū)域，直到每個(gè)區(qū)域中所包含的基本元素全為0或全為lo

四叉樹(shù)模型的圖形表達(dá)中，用黑結(jié)點(diǎn)表示障礙區(qū)域，用白結(jié)點(diǎn)表示自由區(qū)域，這兩類結(jié)點(diǎn)均為葉子結(jié)點(diǎn)：非葉子結(jié)點(diǎn)則可以使用灰結(jié)點(diǎn)表示，該結(jié)點(diǎn)可以一進(jìn)步遞歸分解。

二、改進(jìn)的A*算法

Mangle是對(duì)啟發(fā)式算法腫的改進(jìn)：

1.用后向鏈表代替了原始A*算法中的Closed歹Ll表，在實(shí)現(xiàn)過(guò)程中主要是多定義了父親節(jié)點(diǎn)這樣一個(gè)變量，按照指針指向就可以找到路徑。優(yōu)化了路徑鏈表。

2.在啟發(fā)式函數(shù)上，我們不再用Manhattan函數(shù)來(lái)計(jì)算距離，而是改用最佳柵格距離來(lái)表示。所謂最佳柵格距離是指機(jī)器人遵循柵格移動(dòng)準(zhǔn)則限制下的理想最小距離。更一般化的h（町，sz）=Mi舊（欲，今）+0.4142×Min（dx，dy）。

3.在原始A*算法的基礎(chǔ)上，對(duì)其評(píng)估函數(shù)進(jìn)行了改進(jìn)，加入了轉(zhuǎn)向角度和轉(zhuǎn)次數(shù)這兩個(gè)約束條件：f（n）=W1×/+w2×α+W3×n。在編程過(guò)程中需建立兩個(gè)列表Vfather和OPEN，其中Vfather列表以存放被擴(kuò)展的節(jié)點(diǎn)n，OPEN列表中存放待擴(kuò)展的節(jié)點(diǎn)，且在OPEN中啟發(fā)式函數(shù)f最小的節(jié)點(diǎn)始終在表尾，以便每次擴(kuò)展后建立的后項(xiàng)列表總是指向f值最小的方向。

三、仿真實(shí)驗(yàn)結(jié)果

環(huán)境地圖被構(gòu)造成柵格地圖，符號(hào)“0”所在柵格表示障礙物所在位置：符號(hào)“口”所在柵格為起始節(jié)點(diǎn)：符號(hào)“V”所在柵格表示目標(biāo)節(jié)點(diǎn)：空白柵格表示可穿越地區(qū)，將柵格數(shù)據(jù)表示為以Morton碼為下標(biāo)一的維數(shù)組。

參考文獻(xiàn)：

[1]許心德.環(huán)境部分未知情況下的服務(wù)機(jī)器人導(dǎo)航研究[D].中國(guó)科學(xué)技術(shù)大學(xué)，2009.

[2]陳西博.家庭環(huán)境只能空間中服務(wù)機(jī)器人導(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）.