1、移動機器人路徑規(guī)劃路徑規(guī)劃路徑規(guī)劃 以C表示機器人的位形空間，以F表示無碰撞的自由位形空間。給定機器人初始位形qinit和目標(biāo)位形qgoal，在F中尋找一條連接這兩點的連續(xù)曲線，滿足某些性能指標(biāo)，如路徑最短、行走時間最短、工作代價最小等。 路徑規(guī)劃主要包括環(huán)境、路徑搜索和路徑平滑環(huán)節(jié)環(huán)境建模環(huán)境建模 從現(xiàn)實物理空間到算法處理抽象空間的映射表示 常用建模表示方法： 柵格法 類似于矩陣，柵格數(shù)據(jù)表示有無障礙物 易創(chuàng)建和維護，但分辯率和數(shù)據(jù)量互相制約 幾何法 利用幾何特征表示 需要對感知信息作額外處理 圖 將前面兩種方法結(jié)果用拓撲法連接成一個圖路徑搜索路徑搜索 路徑表達： 以環(huán)境模型中的結(jié)點序列組成

2、或由直線段序列組成 路徑平滑：依據(jù)機器人運動學(xué)或動力學(xué)約束形成機器人可跟蹤執(zhí)行的運動軌跡 如果考慮機器人運動學(xué)約束，則路徑軌跡的一階導(dǎo)數(shù)應(yīng)連續(xù) 如果考慮動力學(xué)約束，則路徑軌跡的二階導(dǎo)數(shù)應(yīng)連續(xù)路徑規(guī)劃路徑規(guī)劃 基于地圖的全局路徑規(guī)劃 環(huán)境已知的離線全局路徑規(guī)劃 環(huán)境未知的在線規(guī)劃 基于進化算法 基于廣義預(yù)測控制 基于傳感器的局部路徑規(guī)劃 增量式構(gòu)造當(dāng)前可視區(qū)域路徑圖的規(guī)劃方法 基于近似單元分解的局部路徑規(guī)劃方法基于微分平坦系統(tǒng)理論的運動規(guī)劃方法基于微分平坦系統(tǒng)理論的運動規(guī)劃方法路徑規(guī)劃方法分類路徑規(guī)劃方法分類 傳統(tǒng)經(jīng)典算法 基于圖的方法 基于柵格的方法 勢場法 數(shù)學(xué)編程法 智能方法 模糊方法 神

3、經(jīng)網(wǎng)絡(luò)方法 遺傳算法基于圖的方法基于圖的方法 通過起始點和目標(biāo)點以及障礙物頂點在內(nèi)的一系列點構(gòu)造可視圖，連接這些點，使某點與其周圍的可視點（即中間無障礙物）相連，然后機器人沿著這些點在圖中搜索路徑。 全局圖法 可視圖法、Voronoi圖法、Silhouette法、基于啟發(fā)式搜索的Q-M圖法 全局搜索，路徑完備，但計算量大，難實現(xiàn) 基于隨機路圖的方法 PRM（Probabilistic Roadmap Method） 易于實現(xiàn)，速度效率高，但僅具有概率完備性基于柵格的方法基于柵格的方法 將區(qū)域劃分成柵格，搜索連通柵格表示路徑。優(yōu)點：易于建模、存儲、處理、更新與分析 Dijkstra算法：通過枚舉

4、求解兩點間距離最短 A*算法：通過代價評估加快搜索 梯度法：由起點到目標(biāo)點距離下降最大梯度方向搜索，不能保證全局最短，可能陷入局部最小點 距離變換法：逆向的梯度法，保證全局最短，但搜索效率隨柵格和障礙物數(shù)目增加急驟下降 四叉樹法：不能最優(yōu)甚至次優(yōu)、損失大量可行自由空間勢場法勢場法 目標(biāo)產(chǎn)生引力、障礙物產(chǎn)生斥力，合力控制機器人運動 適用于靜態(tài)環(huán)境或動態(tài)環(huán)境 存在振蕩和局部最小值 方法： 人工勢場法 虛擬力場法 電場法 結(jié)合模擬退火的人工勢場法數(shù)學(xué)編程法數(shù)學(xué)編程法 用一組不等式來表示機器人的避碰約束，機器人運動起點和終點分別用一個函數(shù)的起始條件和終止條件表示，同時設(shè)定一個最優(yōu)評價函數(shù)，從而將路徑規(guī)

5、劃問題轉(zhuǎn)化為一個純數(shù)學(xué)的最優(yōu)求解問題?；谀：壿嫷姆椒ɑ谀：壿嫷姆椒?模糊邏輯：構(gòu)造二維隸屬度函數(shù)，模糊綜合評價 該方法在環(huán)境未知或發(fā)生變化的情況下，能夠快速而準(zhǔn)確地規(guī)劃機器人路徑，對于要求較少規(guī)劃時間的機器人是一種良好的導(dǎo)航方法。 缺點是當(dāng)障礙物數(shù)目增加時，該方法的計算量會很大，影響規(guī)劃結(jié)果基于神經(jīng)網(wǎng)絡(luò)的方法基于神經(jīng)網(wǎng)絡(luò)的方法 利用神經(jīng)網(wǎng)絡(luò)進行路徑規(guī)劃 缺點：運算時間長，在運動空間數(shù)據(jù)不完備時可能發(fā)生不收斂或路徑不可行問題基于遺傳算法的路徑規(guī)劃基于遺傳算法的路徑規(guī)劃 遺傳算法是計算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進化算法的一種。 遺傳算法通常實現(xiàn)為一種計算機模擬。對于一個最優(yōu)化問題，

6、一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統(tǒng)上，解用二進制表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之后一代一代發(fā)生。在每一代中，整個種群的適應(yīng)度被評價，從當(dāng)前種群中隨機地選擇多個個體（基于它們的適應(yīng)度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。 衍生算法：退火遺傳算法、改進遺傳算子等其它智能機器人路徑規(guī)劃方法其它智能機器人路徑規(guī)劃方法 螞蟻算法：一種全局優(yōu)化算法，模仿螞蟻搜索食物的行為，是一種通用型隨機優(yōu)化方法基于電路地圖的路徑規(guī)劃方法基于電路地圖的路徑規(guī)劃方法 將環(huán)境建模成電路圖。規(guī)劃路徑與電流相似，即路徑的長度以電路中某條通路中串聯(lián)電阻的多少來反映，路徑的寬度以電路中某個方向上的支路數(shù)目即并聯(lián)電阻多少來反映。根據(jù)歐姆定律和電的基本性質(zhì)，在電路中電阻最小的支路上電流最大，而串聯(lián)電阻少且并聯(lián)電阻多的支路即最大電流通路。 優(yōu)點：在規(guī)劃最短路徑的同時考慮了路徑寬度運動控制運動控制 基于路徑規(guī)劃的移動機器人路徑跟蹤控制 非完整控制系統(tǒng)的鎮(zhèn)定方法 非連續(xù)定常鎮(zhèn)定化 時變鎮(zhèn)定化 基于傳感器-執(zhí)行器直接映射的運動控制 模糊邏輯方法神經(jīng)網(wǎng)絡(luò)法(要求先驗知識) 基于動態(tài)規(guī)劃的增強故障診斷故障診斷 現(xiàn)有故障檢測方法可分為基于知識、基于解析模型和基于信號處理3種