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

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

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

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

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

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

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

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

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

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

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

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

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

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