移動機器人路徑規(guī)劃：局部路徑規(guī)劃，全局路徑規(guī)劃

移動機器人的運動規(guī)劃研究開始于20世紀60年代。1978年Wesley 和Lozano 第 一 次把位形空間(Configuration Space)的概念引入到運動規(guī)劃器的設(shè)計中。在C 空間中，每 一個位姿代表機器人在空間中的方位和位置。而機器人則被看做是一個質(zhì)點，那么運動 規(guī)劃問題就可以被看做是在位形空間中，尋找一條起始點到終點之間的路徑問題。所謂 的路徑，就是位形空間中機器人位形的一個特定序列，但是不考慮機器人位形的時間因 數(shù)。軌跡指的是何時到達路徑中的每個地點，強調(diào)了時間的相關(guān)性[130]。機器人的運動 規(guī)劃就是對軌跡的規(guī)劃，按照環(huán)境認知的不同，我們可以把移動機器人的運動規(guī)劃分成局 部路徑規(guī)劃和全局路徑規(guī)劃。

(1)局部路徑規(guī)劃

局部路徑規(guī)劃指的是機器人在全局信息位置的情況下，依靠傳感器信息進行的局部路徑規(guī)劃，主要可以分為人工勢場法(Artificial Potential Field)、遺傳算法、模糊邏輯算 法、神經(jīng)網(wǎng)絡(luò)算法等。人工勢場法Z初由Khatib 提出，其基本思想是引入一個稱為勢場 的數(shù)值函數(shù)來描述機器人空間的幾何結(jié)構(gòu)，通過搜索勢場的下降方向來完成運動規(guī)劃。 這種方法由于它的簡單性和優(yōu)美性而被廣泛采用。但是也存在著一些缺點，如存在陷阱 區(qū)、在相近的障礙物前不能發(fā)現(xiàn)路徑、在障礙物前產(chǎn)生振蕩以及在狹窄通道中擺動等。針 對人工勢場法的缺點，國內(nèi)外許多專家學(xué)者不斷尋找新的途徑，以克服該方法所存在的弊 端，文獻[131]采用預(yù)測與勢場法相結(jié)合的算法解決移動機器人的導(dǎo)航問題，取得了良好效果。文獻[132]通過引入虛擬障礙物使搜索過程跳出局部Z優(yōu)的陷阱，但引入虛擬障 礙物可能會產(chǎn)生新的局部極小點，同時也增加了算法的復(fù)雜度。

遺傳算法是一種多點搜索算法，因此能夠更有效地搜索到全局Z優(yōu)解，這也是為什么 遺傳算法可以用來解決機器人路徑規(guī)劃中的局部極值問題的原因。但是遺傳算法的運算 速度不夠快，在復(fù)雜環(huán)境問題規(guī)劃過程中需要占用大量的存儲空間和運算的時間。

模糊邏輯算法可以通過查表得到信息，完成路徑的局部規(guī)劃，克服了人工勢場法所帶 來的陷人局部極小值的缺點。用于時變位置環(huán)境下的路徑規(guī)劃，實時效果較好。

孫增圻等在假設(shè)檢驗方法中引入了罰函數(shù)項，依靠優(yōu)化罰函數(shù)的方法來尋求機器人 運動的Z優(yōu)路徑，同時利用神經(jīng)網(wǎng)絡(luò)模擬退火算法使其避免陷入局部Z小值。他把移動 物體的碰撞罰函數(shù)定義為各種障礙物與移動物體上的各個測試點之間的碰撞罰函數(shù)之 和。路徑的碰撞罰函數(shù)則為所有在路徑點上的碰撞罰函數(shù)和路徑總長之和[133。謝宏斌 提出了一種基于模糊概念的動態(tài)環(huán)境模型，并在該模型基礎(chǔ)上結(jié)合模糊神經(jīng)網(wǎng)絡(luò)進行機 器人的路徑規(guī)劃，他使用動態(tài)環(huán)境中物體的信息調(diào)整模糊神經(jīng)網(wǎng)絡(luò)權(quán)值的方式來加快算 法的收斂速度，從而達到動態(tài)控制機器人下一步運動的目的[134]。

(2)全局路徑規(guī)劃

機器人的全局路徑規(guī)劃方法可以分為可視圖法(Visibility Graph)、結(jié)構(gòu)空間法 (Configuration Space)、柵格法、拓撲法、隨機路徑規(guī)劃法等。

可視圖法是將移動機器人看做一點，把目標點、機器人和具有多邊形的障礙物的各個 D點進行連接，要求機器人和障礙物各D點之間、目標點和障礙物各D點之間以及各障礙 物D點與D點之間的連線，都不能穿越障礙物，這樣形成的圖稱之為可視圖。該方法的優(yōu) 點是可以求得Z短路徑，但缺乏靈活性，并且隨著障礙物的D點個數(shù)的增多存在組合爆炸 問題[135]。

結(jié)構(gòu)空間法是一種數(shù)據(jù)結(jié)構(gòu)方法。移動機器人通過該數(shù)據(jù)結(jié)構(gòu)來確定物體或自身的 位姿。結(jié)構(gòu)空間表示法有許多種，Z具代表性的是Voronoi 圖法和四叉樹(Quadtree) 及 其擴展算法。Voronoi圖法的基本思想是：先產(chǎn)生與環(huán)境障礙物中所有邊界點等距離的 Voronoi邊 ，Voronoi邊之間的交點稱之為 Voronoi D點。然后，移動機器人沿著這些 Voronoi邊行走，不僅不會與障礙物相碰撞，而且一定在任意兩個障礙物的中間。四叉樹 是一種遞歸網(wǎng)格，先在移動機器人所處環(huán)境上建立一個二維直角坐標網(wǎng)格，然后用大的 網(wǎng)格單元對機器人所處環(huán)境進行劃分。倘若障礙物占用了網(wǎng)格單元的一個元素，則就把 這部分分成四個小格子(四叉樹)。如果這四個小格子中還有被占據(jù)的單元，則遞歸地對 該單元再分割成更小的四個子網(wǎng)格[136]。

柵格法將移動機器人工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元，多采用二維 笛卡兒矩陣柵格表示工作環(huán)境。每一個矩形柵格都有一個累積值CV, 表示在此方位中存 在障礙物的可信度，CV值越高，表征存在障礙物的可能性越高。用柵格法表示格子環(huán)境 模型中存在障礙物可能性的方法起源于美國的CMU大學(xué)，通過優(yōu)化算法在單元中搜索Z 優(yōu)路徑。由于該方法以柵格為單位記錄環(huán)境信息，環(huán)境被量化成具有一定分辨率的柵 格。因為柵格的大小直接影響著環(huán)境信息存儲量的大小以及路徑搜索的時間，所以在實 用上具有一定的局限性[137]。

拓撲法是根據(jù)環(huán)境信息和運動物體的幾何特點，將組成空間劃分成若干具有拓撲特 征一致的自由空間。根據(jù)彼此間的連通性建立拓撲網(wǎng)，從該網(wǎng)中搜索一條拓撲路徑，即完 成了路徑規(guī)劃的任務(wù)。該方法的優(yōu)點在于因為利用了拓撲特征而大大縮小了搜索空間， 其算法復(fù)雜性只與障礙物的數(shù)目有關(guān)，在理論上是完備的。但是，建立拓撲網(wǎng)的過程是相 當(dāng)復(fù)雜而費時的，特別是當(dāng)增加或減少障礙物時如何有效地修正已經(jīng)存在的拓撲網(wǎng)絡(luò)以 及如何提高圖形搜索速度是目前亟待解決的問題。但是針對一種環(huán)境，拓撲網(wǎng)只需建立 一次，因而在其上進行多次路徑規(guī)劃就可期望獲得較高的效率[138]。

以上幾種方法都是基于自由空間幾何構(gòu)造的規(guī)劃，而快速隨機搜索樹算法 RRT(Rapidly Exploring Random Tree) 則是近年興起的一種以解決高維姿態(tài)空間和復(fù)雜 環(huán)境中運動規(guī)劃為目的的基于隨機采樣的運動規(guī)劃。1998年美國伊利諾伊大學(xué)(UIUC) 的科學(xué)家S.M.La Valle 在Z優(yōu)控制理論、非完整規(guī)劃和隨機路徑規(guī)劃的基礎(chǔ)上提出了一 種單一查詢RRT。路徑產(chǎn)生階段，從目標狀態(tài)點出發(fā)，找到父親節(jié)點，依此直至到達起始 狀態(tài)點，即樹根，就規(guī)劃出從起始狀態(tài)點到達目標狀態(tài)點滿足全局和微分約束的路徑以及 在每一時刻的控制輸人參數(shù)。因為在搜索樹的生成過程中充分考慮了機器人客觀存在的 微分約束(如非完整約束、動力學(xué)約束、運動動力學(xué)約束等),因而算法規(guī)劃出來的軌跡合 理性非常好，但算法的隨機性導(dǎo)致其只能概率完備。