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

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

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

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

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

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

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

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

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

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

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

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

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