《pathplanning移動機器人路徑規(guī)劃方法綜述》由會員分享，可在線閱讀，更多相關(guān)《pathplanning移動機器人路徑規(guī)劃方法綜述（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、移動機器人路徑規(guī)劃方法1.1路徑規(guī)劃方法路徑規(guī)劃技術(shù)是機器人研究領(lǐng)域中的一個重要課題，是機器人 導(dǎo)航中最重要的任務(wù)之一，國外文獻常將其稱為Path Pla nnin g,Fi nd-PathProblem,Collisi on-Free,ObstacleAvoida nee, Motio nPla nnin g,etc.所謂機器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某 個或某些優(yōu)化準則（如工作代價最小、行走路線最短、行走時間最短 等），在其工作空間中找到一條從起始狀態(tài)到目標狀態(tài)的能避開障礙 物的最優(yōu)路徑。路徑規(guī)劃主要涉及的問題包括：利用獲得的移動機器人環(huán)境信息 建立較為合理的模型，再用某種算法尋找一條

2、從起始狀態(tài)到目標狀態(tài) 的最優(yōu)或近似最優(yōu)的無碰撞路徑；能夠處理環(huán)境模型中的不確定因素 和路徑跟蹤中出現(xiàn)的誤差，使外界物體對機器人的影響降到最??；如何利用已知的所有信息來引導(dǎo)機器人的動作，從而得到相對更優(yōu)的行為決策。這其中的根本問題是世界模型的表達和搜尋策略。障礙物在環(huán)境中的不同分布情況當然直接影響到規(guī)劃的路徑，而目標位置的確定則是由更高一級的任務(wù)分解模塊提供的8。根據(jù)機器人對環(huán)境信息掌握的程度和障礙物運動狀態(tài)的不同，移動機器人的路徑規(guī)劃基本上可分為以下四類：已知環(huán)境下的對靜態(tài)障礙物的路徑規(guī)劃；未知環(huán)境下的對靜態(tài)障礙物的路徑規(guī)劃知環(huán)境下對動態(tài)障礙物的路徑規(guī)劃；未知環(huán)境下對動態(tài)障礙物的路 徑規(guī)劃。因

3、此根據(jù)機器人對環(huán)境信息掌握的程度不同，可將機器人的路徑規(guī)劃問題可分為二大類即：基于環(huán)境先驗信息的全局路徑規(guī)劃問 題和基于不確定環(huán)境的局部路徑規(guī)劃問題。目前，路徑規(guī)劃研究方法大概可分為兩大類即：傳統(tǒng)方法和智能方法。1.2傳統(tǒng)路徑規(guī)劃方法傳統(tǒng)的路徑規(guī)劃方法主要包括：可視圖法 (V-Graph)、自由空間法(Free Space Approach)、人工勢場法( Artificial Pote ntial Field )和柵格法(Grids)等?？梢晥D法(V-Graph)可視圖法是Nilsson1968年在文獻中首次提出?？梢晥D法將移 動機器人視為一點，將機器人起始點、目標點和多邊形障礙物的各定 點

4、組合連接，保證這些直線不與障礙物相交，這就構(gòu)成了一張無向圖 稱為可視圖。由于任意兩條直線的定點都是可見的， 從起點沿著這些 直線到達目標點的路線都是無碰撞的。 于是，搜索最優(yōu)路徑的問題就 轉(zhuǎn)化為從起始點到目標點經(jīng)過這些可視直線的最短距離問題。這種方法的優(yōu)點是可以得到最優(yōu)路徑，但缺陷是環(huán)境特征的提取 比較困難，缺乏靈活性，一般需要機器人停止在障礙物前搜集傳感器 數(shù)據(jù)，并且傳感器的精度對其影響也較大，尤其在復(fù)雜的非規(guī)整環(huán)境下更加難以實現(xiàn)安全無碰撞的路徑規(guī)劃。自由空間法(Free Space Approach)自由空間法10,11的基本思想是采用預(yù)先定義的基本形狀（如廣義錐形，凸多邊形等）構(gòu)造自由空

5、間，并將自由空間表示為連通圖，然 后通過對圖的搜索來規(guī)劃路徑，其算法的復(fù)雜度往往與障礙物的個數(shù) 成正比。首先，指定機器人在環(huán)境中的安全位置，將機器人簡化為一 個點，同時“膨脹”障礙物的尺寸，從而形成一個虛擬的障礙空間， 這樣就將機器人與障礙物的尺寸約束關(guān)系轉(zhuǎn)化到另一個虛擬數(shù)據(jù)空 間，簡化了問題。然后，尋找從起始位置到目標位置的最短路徑就可 以得到機器人的最短安全路徑。自由空間的優(yōu)點是比較靈活，機器人的起始點和目標點的改變不 會造成連通圖的重新構(gòu)造，缺點為當障礙物增加時，其運算復(fù)雜度會 相應(yīng)地增大，可能在有限的時間內(nèi)找不到最優(yōu)路徑。人工勢場法（Artificial Potential Field

6、）人工勢場法12最初由Khatib提出，其基本思想是引入一個稱為 勢場的數(shù)值函數(shù)來描述機器人空間的幾何結(jié)構(gòu)， 通過搜索勢場的下降 方向來完成運動規(guī)劃。人工勢場法結(jié)構(gòu)簡單，便于低層的實時控制，在實時避障和平滑 的軌跡控制方面，得到了廣泛的應(yīng)用，但對存在局部最優(yōu)解的問題， 容易產(chǎn)生死鎖現(xiàn)象（DeadLock），因而可能使機器人在到達目標點之前 就停留在局部最優(yōu)點；柵格法（Grids）柵格法13是W.E.Howden于 1968年提出的，柵格法用大小相等的 矩形柵格表示環(huán)境，并對環(huán)境中的自由空間與障礙空間進行劃分，于是，路徑規(guī)劃問題就轉(zhuǎn)化為在柵格地圖上學找最優(yōu)路徑的問題。柵格法以柵格為單位記錄環(huán)境信

7、息，柵格大小對環(huán)境信息存儲量的大小和 規(guī)劃時間的長短有著重要影響，柵格劃分大了，環(huán)境信息存儲量小， 規(guī)劃時間短，但分辨率就低；反之，雖然分辨率高了，但規(guī)劃時間長。 可以看出，柵格粒度越小，障礙物的示會越精確，但同時會占用大量 的存儲空間，算法的搜索范圍將按指數(shù)增加。柵格的粒度太大，規(guī)劃 的路徑會很不精確。所以柵格粒度大小的確定，是柵格法中的主要問 題。柵格法的特點是簡單和易于實現(xiàn)，易于擴展到三維環(huán)境。它的缺 點是對工作區(qū)域的大小有一定的要求， 如果區(qū)域太大，將使柵格的數(shù) 量急劇增加，使搜索存在組合爆炸的問題。小結(jié)：綜上介紹的四種方法中，可視圖法、自由空間法、柵格法 為全局路徑規(guī)劃方法，首先根據(jù)

8、已知環(huán)境用不同的方法建立數(shù)學模 型，然后利用相應(yīng)的搜索算法尋找最優(yōu)路徑。常用的搜索算法有：隨 機搜索法、梯度法、枚舉法、A*等圖搜索方法。這些方法中隨機搜索 法則計算效率太低，梯度法易陷入局部最小點，而枚舉法、圖搜索方 法不能用于高維的優(yōu)化問題。人工勢場法既可以用于全局路徑規(guī)劃也 可用于局部路徑規(guī)劃。1.3智能路徑規(guī)劃方法近年來，隨著遺傳算法、神經(jīng)網(wǎng)絡(luò)等智能算法的廣泛應(yīng)用，智能 機器人的路徑規(guī)劃方法也有了長足的進步。 其中應(yīng)用較多的智能方法 主要有模糊邏輯算法(Fuzzy Logic Algorithm )、神經(jīng)網(wǎng)絡(luò)(Neural networks )和遺傳算法(Genetic Algorth

9、m )。模糊邏輯算法(Fuzzy Logic Algorithm)模糊邏輯算法通過模擬駕駛員的駕駛思想，將模糊控制本身具備的魯棒性同基于生理學上的“感知一動作”行為相結(jié)合，為移動機器 人在未知環(huán)境或者不確定環(huán)境中的導(dǎo)航和路徑規(guī)劃提供了一個新的 思路。模糊控制器的設(shè)計通常包括四個步驟：模糊化過程、規(guī)則庫的 建立、模糊推理以及解模糊化14。由于模糊邏輯控制具有符合人類思 維的習慣，不需要建立精確的數(shù)學模型，易于將專家知識直接轉(zhuǎn)換為 控制信號等優(yōu)點，已成為移動機器人導(dǎo)航的一種重要方法。在用模糊 控制的方法規(guī)劃機器人路徑時，往往要對機器人自身帶的傳感器獲取 信息進行模糊化處理。模糊邏輯算法的優(yōu)點是算法

10、直觀， 容易實現(xiàn)，能夠方便人的經(jīng)驗 融合到算法當中，計算量不大，能滿足實時性的要求。缺點是：當環(huán) 境很復(fù)雜時，總結(jié)出的規(guī)則難以面面俱到，很難構(gòu)造出比較全面的知 識庫,缺乏泛化的能力15,16。神經(jīng)網(wǎng)絡(luò)算法(Neural networks )人工神經(jīng)網(wǎng)絡(luò)是由大量簡單的神經(jīng)元相互連接而形成的自適應(yīng) 非線性動態(tài)系統(tǒng)。人工神經(jīng)網(wǎng)絡(luò)的研究可以追溯到本世紀 40年代, 1943年心理學家 W. MeCulloch和數(shù)學家 W. P it ts首次提出神經(jīng)元的數(shù)學模型即 M P模型17。神經(jīng)網(wǎng)絡(luò)法的基本原理是將環(huán)境障礙 等作為神經(jīng)網(wǎng)絡(luò)的輸入層信息，經(jīng)由神經(jīng)網(wǎng)絡(luò)并行處理，神經(jīng)網(wǎng)絡(luò)輸出層輸出期望的轉(zhuǎn)向角和速度等

11、，引導(dǎo)機器人避障行駛，直至到達目 的地。神經(jīng)網(wǎng)絡(luò)具備以下幾個特點：并行處理性，處理速度快。信息分布式存儲，信息具有容錯性和全息性。自適應(yīng)和自組織性。層次性。神經(jīng)網(wǎng)絡(luò)算法的優(yōu)點是其并行處理效率高，具有學習功能，能收斂到最優(yōu)路徑，機器人能夠?qū)崿F(xiàn)較好的自主導(dǎo)航。但當障礙物較多， 網(wǎng)絡(luò)規(guī)模往往龐大，使得實際中難應(yīng)用18。遺傳算法(Genetic Algorthm )遺傳算法的基本思想是基于 Darwin的進化論和Men del的遺傳 學說。該算法由密執(zhí)安大學教授 Holand及其學生于1975年創(chuàng)建。 它是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨 機、自適應(yīng)搜索算法。遺傳算法采用群體搜索

12、技術(shù)，通過選擇、交叉 和變異等一系列遺傳操作，使種群得以進化，避免了困難的理論推導(dǎo)， 直接獲得問題的最優(yōu)解。算法的基本思想是：將路徑個體表達為路徑 中一系列中途點，并轉(zhuǎn)換為二進制串，首先初始化路徑群體，然后進 行遺傳操作，如選擇、交叉、復(fù)制、變異，經(jīng)過若干代進化以后，停 止進化，輸出當前最優(yōu)個體19。遺傳算法能過在不同區(qū)域的解空間中不斷搜索，能夠避免了陷入局部極小解的情況，更有可能得到全局最優(yōu)的路徑。但在傳統(tǒng)遺傳算 法在處理復(fù)雜的、多目標、多變量優(yōu)化問題時，往往存在早熟或收斂 慢的問題。小結(jié)：以上介紹的三種智能規(guī)劃方法都可以用于移動機器人在未知環(huán)境的局部路徑規(guī)劃問題。適當?shù)膶⑦z傳算法、模糊邏輯以及神經(jīng) 網(wǎng)絡(luò)等方法相結(jié)合，可以組成新的智能型路徑規(guī)劃方法， 從而提高機 器人路徑規(guī)劃的避障精度，加快規(guī)劃速度，滿足實際應(yīng)用的需要。1.4本章小結(jié)本章主要介紹了移動機器人路徑規(guī)劃的一些常用方法及分類，著重敘述了常用路徑規(guī)劃算法的思想。 同時，分析了不同方法的優(yōu)勢與 局限性。因此，在理論研究中應(yīng)該進一步努力完善和改進算法；在實 際應(yīng)用中，應(yīng)根據(jù)實際情況選擇適當?shù)穆窂揭?guī)劃方法， 更好的發(fā)揮不 同算法的優(yōu)勢。