移動(dòng)機(jī)器人路徑規(guī)劃方法1.1路徑規(guī)劃方法路徑規(guī)劃技術(shù)是機(jī)器人研究領(lǐng)域中的一個(gè)重要課題，是機(jī)器人 導(dǎo)航中最重要的任務(wù)之一，國外文獻(xiàn)常將其稱為Path Pla nnin g,Fi nd-PathProblem,Collisi on-Free,ObstacleAvoida nee, Motio nPla nnin g,etc.所謂機(jī)器人的最優(yōu)路徑規(guī)劃問題，就是依據(jù)某 個(gè)或某些優(yōu)化準(zhǔn)則（如工作代價(jià)最小、行走路線最短、行走時(shí)間最短 等），在其工作空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)的能避開障礙 物的最優(yōu)路徑。路徑規(guī)劃主要涉及的問題包括：利用獲得的移動(dòng)機(jī)器人環(huán)境信息 建立較為合理的模型，再用某種算法尋找一條從起始狀態(tài)到目標(biāo)狀態(tài) 的最優(yōu)或近似最優(yōu)的無碰撞路徑；能夠處理環(huán)境模型中的不確定因素 和路徑跟蹤中出現(xiàn)的誤差，使外界物體對(duì)機(jī)器人的影響降到最??；如何利用已知的所有信息來引導(dǎo)機(jī)器人的動(dòng)作，從而得到相對(duì)更優(yōu)的行為決策。這其中的根本問題是世界模型的表達(dá)和搜尋策略。障礙物在環(huán)境中的不同分布情況當(dāng)然直接影響到規(guī)劃的路徑，而目標(biāo)位置的確定則是由更高一級(jí)的任務(wù)分解模塊提供的8。根據(jù)機(jī)器人對(duì)環(huán)境信息掌握的程度和障礙物運(yùn)動(dòng)狀態(tài)的不同，移動(dòng)機(jī)器人的路徑規(guī)劃基本上可分為以下四類：已知環(huán)境下的對(duì)靜態(tài)障礙物的路徑規(guī)劃；未知環(huán)境下的對(duì)靜態(tài)障礙物的路徑規(guī)劃知環(huán)境下對(duì)動(dòng)態(tài)障礙物的路徑規(guī)劃；未知環(huán)境下對(duì)動(dòng)態(tài)障礙物的路 徑規(guī)劃。因此根據(jù)機(jī)器人對(duì)環(huán)境信息掌握的程度不同，可將機(jī)器人的路徑規(guī)劃問題可分為二大類即：基于環(huán)境先驗(yàn)信息的全局路徑規(guī)劃問 題和基于不確定環(huán)境的局部路徑規(guī)劃問題。目前，路徑規(guī)劃研究方法大概可分為兩大類即：傳統(tǒng)方法和智能方法。1.2傳統(tǒng)路徑規(guī)劃方法傳統(tǒng)的路徑規(guī)劃方法主要包括：可視圖法 (V-Graph)、自由空間法(Free Space Approach)、人工勢(shì)場(chǎng)法( Artificial Pote ntial Field )和柵格法(Grids)等?？梢晥D法(V-Graph)可視圖法是Nilsson1968年在文獻(xiàn)中首次提出?？梢晥D法將移 動(dòng)機(jī)器人視為一點(diǎn)，將機(jī)器人起始點(diǎn)、目標(biāo)點(diǎn)和多邊形障礙物的各定 點(diǎn)組合連接，保證這些直線不與障礙物相交，這就構(gòu)成了一張無向圖 稱為可視圖。由于任意兩條直線的定點(diǎn)都是可見的， 從起點(diǎn)沿著這些 直線到達(dá)目標(biāo)點(diǎn)的路線都是無碰撞的。 于是，搜索最優(yōu)路徑的問題就 轉(zhuǎn)化為從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過這些可視直線的最短距離問題。這種方法的優(yōu)點(diǎn)是可以得到最優(yōu)路徑，但缺陷是環(huán)境特征的提取 比較困難，缺乏靈活性，一般需要機(jī)器人停止在障礙物前搜集傳感器 數(shù)據(jù)，并且傳感器的精度對(duì)其影響也較大，尤其在復(fù)雜的非規(guī)整環(huán)境下更加難以實(shí)現(xiàn)安全無碰撞的路徑規(guī)劃。自由空間法(Free Space Approach)自由空間法10,11的基本思想是采用預(yù)先定義的基本形狀（如廣義錐形，凸多邊形等）構(gòu)造自由空間，并將自由空間表示為連通圖，然 后通過對(duì)圖的搜索來規(guī)劃路徑，其算法的復(fù)雜度往往與障礙物的個(gè)數(shù) 成正比。首先，指定機(jī)器人在環(huán)境中的安全位置，將機(jī)器人簡化為一 個(gè)點(diǎn)，同時(shí)“膨脹”障礙物的尺寸，從而形成一個(gè)虛擬的障礙空間， 這樣就將機(jī)器人與障礙物的尺寸約束關(guān)系轉(zhuǎn)化到另一個(gè)虛擬數(shù)據(jù)空 間，簡化了問題。然后，尋找從起始位置到目標(biāo)位置的最短路徑就可 以得到機(jī)器人的最短安全路徑。自由空間的優(yōu)點(diǎn)是比較靈活，機(jī)器人的起始點(diǎn)和目標(biāo)點(diǎn)的改變不 會(huì)造成連通圖的重新構(gòu)造，缺點(diǎn)為當(dāng)障礙物增加時(shí)，其運(yùn)算復(fù)雜度會(huì) 相應(yīng)地增大，可能在有限的時(shí)間內(nèi)找不到最優(yōu)路徑。人工勢(shì)場(chǎng)法（Artificial Potential Field）人工勢(shì)場(chǎng)法12最初由Khatib提出，其基本思想是引入一個(gè)稱為 勢(shì)場(chǎng)的數(shù)值函數(shù)來描述機(jī)器人空間的幾何結(jié)構(gòu)， 通過搜索勢(shì)場(chǎng)的下降 方向來完成運(yùn)動(dòng)規(guī)劃。人工勢(shì)場(chǎng)法結(jié)構(gòu)簡單，便于低層的實(shí)時(shí)控制，在實(shí)時(shí)避障和平滑 的軌跡控制方面，得到了廣泛的應(yīng)用，但對(duì)存在局部最優(yōu)解的問題， 容易產(chǎn)生死鎖現(xiàn)象（DeadLock），因而可能使機(jī)器人在到達(dá)目標(biāo)點(diǎn)之前 就停留在局部最優(yōu)點(diǎn)；柵格法（Grids）柵格法13是W.E.Howden于 1968年提出的，柵格法用大小相等的 矩形柵格表示環(huán)境，并對(duì)環(huán)境中的自由空間與障礙空間進(jìn)行劃分，于是，路徑規(guī)劃問題就轉(zhuǎn)化為在柵格地圖上學(xué)找最優(yōu)路徑的問題。柵格法以柵格為單位記錄環(huán)境信息，柵格大小對(duì)環(huán)境信息存儲(chǔ)量的大小和 規(guī)劃時(shí)間的長短有著重要影響，柵格劃分大了，環(huán)境信息存儲(chǔ)量小， 規(guī)劃時(shí)間短，但分辨率就低；反之，雖然分辨率高了，但規(guī)劃時(shí)間長。 可以看出，柵格粒度越小，障礙物的示會(huì)越精確，但同時(shí)會(huì)占用大量 的存儲(chǔ)空間，算法的搜索范圍將按指數(shù)增加。柵格的粒度太大，規(guī)劃 的路徑會(huì)很不精確。所以柵格粒度大小的確定，是柵格法中的主要問 題。柵格法的特點(diǎn)是簡單和易于實(shí)現(xiàn)，易于擴(kuò)展到三維環(huán)境。它的缺 點(diǎn)是對(duì)工作區(qū)域的大小有一定的要求， 如果區(qū)域太大，將使柵格的數(shù) 量急劇增加，使搜索存在組合爆炸的問題。小結(jié)：綜上介紹的四種方法中，可視圖法、自由空間法、柵格法 為全局路徑規(guī)劃方法，首先根據(jù)已知環(huán)境用不同的方法建立數(shù)學(xué)模 型，然后利用相應(yīng)的搜索算法尋找最優(yōu)路徑。常用的搜索算法有：隨 機(jī)搜索法、梯度法、枚舉法、A*等圖搜索方法。這些方法中隨機(jī)搜索 法則計(jì)算效率太低，梯度法易陷入局部最小點(diǎn)，而枚舉法、圖搜索方 法不能用于高維的優(yōu)化問題。人工勢(shì)場(chǎng)法既可以用于全局路徑規(guī)劃也 可用于局部路徑規(guī)劃。1.3智能路徑規(guī)劃方法近年來，隨著遺傳算法、神經(jīng)網(wǎng)絡(luò)等智能算法的廣泛應(yīng)用，智能 機(jī)器人的路徑規(guī)劃方法也有了長足的進(jìn)步。 其中應(yīng)用較多的智能方法 主要有模糊邏輯算法(Fuzzy Logic Algorithm )、神經(jīng)網(wǎng)絡(luò)(Neural networks )和遺傳算法(Genetic Algorthm )。模糊邏輯算法(Fuzzy Logic Algorithm)模糊邏輯算法通過模擬駕駛員的駕駛思想，將模糊控制本身具備的魯棒性同基于生理學(xué)上的“感知一動(dòng)作”行為相結(jié)合，為移動(dòng)機(jī)器 人在未知環(huán)境或者不確定環(huán)境中的導(dǎo)航和路徑規(guī)劃提供了一個(gè)新的 思路。模糊控制器的設(shè)計(jì)通常包括四個(gè)步驟：模糊化過程、規(guī)則庫的 建立、模糊推理以及解模糊化14。由于模糊邏輯控制具有符合人類思 維的習(xí)慣，不需要建立精確的數(shù)學(xué)模型，易于將專家知識(shí)直接轉(zhuǎn)換為 控制信號(hào)等優(yōu)點(diǎn)，已成為移動(dòng)機(jī)器人導(dǎo)航的一種重要方法。在用模糊 控制的方法規(guī)劃機(jī)器人路徑時(shí)，往往要對(duì)機(jī)器人自身帶的傳感器獲取 信息進(jìn)行模糊化處理。模糊邏輯算法的優(yōu)點(diǎn)是算法直觀， 容易實(shí)現(xiàn)，能夠方便人的經(jīng)驗(yàn) 融合到算法當(dāng)中，計(jì)算量不大，能滿足實(shí)時(shí)性的要求。缺點(diǎn)是：當(dāng)環(huán) 境很復(fù)雜時(shí)，總結(jié)出的規(guī)則難以面面俱到，很難構(gòu)造出比較全面的知 識(shí)庫,缺乏泛化的能力15,16。神經(jīng)網(wǎng)絡(luò)算法(Neural networks )人工神經(jīng)網(wǎng)絡(luò)是由大量簡單的神經(jīng)元相互連接而形成的自適應(yīng) 非線性動(dòng)態(tài)系統(tǒng)。人工神經(jīng)網(wǎng)絡(luò)的研究可以追溯到本世紀(jì) 40年代, 1943年心理學(xué)家 W. MeCulloch和數(shù)學(xué)家 W. P it ts首次提出神經(jīng)元的數(shù)學(xué)模型即 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)向角和速度等，引導(dǎo)機(jī)器人避障行駛，直至到達(dá)目 的地。神經(jīng)網(wǎng)絡(luò)具備以下幾個(gè)特點(diǎn)：并行處理性，處理速度快。信息分布式存儲(chǔ)，信息具有容錯(cuò)性和全息性。自適應(yīng)和自組織性。層次性。神經(jīng)網(wǎng)絡(luò)算法的優(yōu)點(diǎn)是其并行處理效率高，具有學(xué)習(xí)功能，能收斂到最優(yōu)路徑，機(jī)器人能夠?qū)崿F(xiàn)較好的自主導(dǎo)航。但當(dāng)障礙物較多， 網(wǎng)絡(luò)規(guī)模往往龐大，使得實(shí)際中難應(yīng)用18。遺傳算法(Genetic Algorthm )遺傳算法的基本思想是基于 Darwin的進(jìn)化論和Men del的遺傳 學(xué)說。該算法由密執(zhí)安大學(xué)教授 Holand及其學(xué)生于1975年創(chuàng)建。 它是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨 機(jī)、自適應(yīng)搜索算法。遺傳算法采用群體搜索技術(shù)，通過選擇、交叉 和變異等一系列遺傳操作，使種群得以進(jìn)化，避免了困難的理論推導(dǎo)， 直接獲得問題的最優(yōu)解。算法的基本思想是：將路徑個(gè)體表達(dá)為路徑 中一系列中途點(diǎn)，并轉(zhuǎn)換為二進(jìn)制串，首先初始化路徑群體，然后進(jìn) 行遺傳操作，如選擇、交叉、復(fù)制、變異，經(jīng)過若干代進(jìn)化以后，停 止進(jìn)化，輸出當(dāng)前最優(yōu)個(gè)體19。遺傳算法能過在不同區(qū)域的解空間中不斷搜索，能夠避免了陷入局部極小解的情況，更有可能得到全局最優(yōu)的路徑。但在傳統(tǒng)遺傳算 法在處理復(fù)雜的、多目標(biāo)、多變量優(yōu)化問題時(shí)，往往存在早熟或收斂 慢的問題。小結(jié)：以上介紹的三種智能規(guī)劃方法都可以用于移動(dòng)機(jī)器人在未知環(huán)境的局部路徑規(guī)劃問題。適當(dāng)?shù)膶⑦z傳算法、模糊邏輯以及神經(jīng) 網(wǎng)絡(luò)等方法相結(jié)合，可以組成新的智能型路徑規(guī)劃方法， 從而提高機(jī) 器人路徑規(guī)劃的避障精度，加快規(guī)劃速度，滿足實(shí)際應(yīng)用的需要。1.4本章小結(jié)本章主要介紹了移動(dòng)機(jī)器人路徑規(guī)劃的一些常用方法及分類，著重?cái)⑹隽顺Ｓ寐窂揭?guī)劃算法的思想。 同時(shí)，分析了不同方法的優(yōu)勢(shì)與 局限性。因此，在理論研究中應(yīng)該進(jìn)一步努力完善和改進(jìn)算法；在實(shí) 際應(yīng)用中，應(yīng)根據(jù)實(shí)際情況選擇適當(dāng)?shù)穆窂揭?guī)劃方法， 更好的發(fā)揮不 同算法的優(yōu)勢(shì)。