移動機器人路徑規(guī)劃.ppt

移動機器人路徑規(guī)劃技術(shù) 體系結(jié)構(gòu) 基于功能的分層式體系結(jié)構(gòu)功能 感知 建模 規(guī)劃 行動基于 傳感器 行為的反應(yīng)式體系結(jié)構(gòu)如Brooks包容式體系結(jié)構(gòu)機器人行為控制器構(gòu)造優(yōu)化方法基于模糊邏輯及神經(jīng)網(wǎng)絡(luò)的監(jiān)督學習基于傳感器信息的局部運動規(guī)劃 前兩種 混合式 BrooksR RobisA LayeredControlSystemforaMobileRobot IEEETransonRobotics Automation 1986 2 1 14 23 路徑規(guī)劃 以C表示機器人的位形空間 以F表示無碰撞的自由位形空間 給定機器人初始位形qinit和目標位形qgoal 在F中尋找一條連接這兩點的連續(xù)曲線 滿足某些性能指標 如路徑最短 行走時間最短 工作代價最小等 路徑規(guī)劃主要包括環(huán)境 路徑搜索和路徑平滑環(huán)節(jié) 環(huán)境建模 從現(xiàn)實物理空間到算法處理抽象空間的映射表示常用建模表示方法 柵格法類似于矩陣 柵格數(shù)據(jù)表示有無障礙物易創(chuàng)建和維護 但分辯率和數(shù)據(jù)量互相制約幾何法利用幾何特征表示需要對感知信息作額外處理圖將前面兩種方法結(jié)果用拓撲法連接成一個圖 路徑搜索 路徑表達 以環(huán)境模型中的結(jié)點序列組成或由直線段序列組成路徑平滑 依據(jù)機器人運動學或動力學約束形成機器人可跟蹤執(zhí)行的運動軌跡如果考慮機器人運動學約束 則路徑軌跡的一階導數(shù)應(yīng)連續(xù)如果考慮動力學約束 則路徑軌跡的二階導數(shù)應(yīng)連續(xù) 路徑規(guī)劃 基于地圖的全局路徑規(guī)劃環(huán)境已知的離線全局路徑規(guī)劃環(huán)境未知的在線規(guī)劃基于進化算法基于廣義預(yù)測控制基于傳感器的局部路徑規(guī)劃增量式構(gòu)造當前可視區(qū)域路徑圖的規(guī)劃方法基于近似單元分解的局部路徑規(guī)劃方法基于微分平坦系統(tǒng)理論的運動規(guī)劃方法 路徑規(guī)劃方法分類 傳統(tǒng)經(jīng)典算法基于圖的方法基于柵格的方法勢場法數(shù)學編程法智能方法模糊方法神經(jīng)網(wǎng)絡(luò)方法遺傳算法 基于圖的方法 通過起始點和目標點以及障礙物頂點在內(nèi)的一系列點構(gòu)造可視圖 連接這些點 使某點與其周圍的可視點 即中間無障礙物 相連 然后機器人沿著這些點在圖中搜索路徑 全局圖法可視圖法 Voronoi圖法 Silhouette法 基于啟發(fā)式搜索的Q M圖法全局搜索 路徑完備 但計算量大 難實現(xiàn)基于隨機路圖的方法PRM ProbabilisticRoadmapMethod 易于實現(xiàn) 速度效率高 但僅具有概率完備性 基于柵格的方法 將區(qū)域劃分成柵格 搜索連通柵格表示路徑 優(yōu)點 易于建模 存儲 處理 更新與分析Dijkstra算法 通過枚舉求解兩點間距離最短A 算法 通過代價評估加快搜索梯度法 由起點到目標點距離下降最大梯度方向搜索 不能保證全局最短 可能陷入局部最小點距離變換法 逆向的梯度法 保證全局最短 但搜索效率隨柵格和障礙物數(shù)目增加急驟下降四叉樹法 不能最優(yōu)甚至次優(yōu) 損失大量可行自由空間 勢場法 目標產(chǎn)生引力 障礙物產(chǎn)生斥力 合力控制機器人運動適用于靜態(tài)環(huán)境或動態(tài)環(huán)境存在振蕩和局部最小值方法 人工勢場法虛擬力場法電場法結(jié)合模擬退火的人工勢場法 數(shù)學編程法 用一組不等式來表示機器人的避碰約束 機器人運動起點和終點分別用一個函數(shù)的起始條件和終止條件表示 同時設(shè)定一個最優(yōu)評價函數(shù) 從而將路徑規(guī)劃問題轉(zhuǎn)化為一個純數(shù)學的最優(yōu)求解問題 基于模糊邏輯的方法 模糊邏輯 構(gòu)造二維隸屬度函數(shù) 模糊綜合評價該方法在環(huán)境未知或發(fā)生變化的情況下 能夠快速而準確地規(guī)劃機器人路徑 對于要求較少規(guī)劃時間的機器人是一種良好的導航方法 缺點是當障礙物數(shù)目增加時 該方法的計算量會很大 影響規(guī)劃結(jié)果 基于神經(jīng)網(wǎng)絡(luò)的方法 利用神經(jīng)網(wǎng)絡(luò)進行路徑規(guī)劃缺點 運算時間長 在運動空間數(shù)據(jù)不完備時可能發(fā)生不收斂或路徑不可行問題 基于遺傳算法的路徑規(guī)劃 遺傳算法是計算數(shù)學中用于解決最優(yōu)化的搜索算法 是進化算法的一種 遺傳算法通常實現(xiàn)為一種計算機模擬 對于一個最優(yōu)化問題 一定數(shù)量的候選解 稱為個體 的抽象表示 稱為染色體 的種群向更好的解進化 傳統(tǒng)上 解用二進制表示 即0和1的串 但也可以用其他表示方法 進化從完全隨機個體的種群開始 之后一代一代發(fā)生 在每一代中 整個種群的適應(yīng)度被評價 從當前種群中隨機地選擇多個個體 基于它們的適應(yīng)度 通過自然選擇和突變產(chǎn)生新的生命種群 該種群在算法的下一次迭代中成為當前種群 衍生算法 退火遺傳算法 改進遺傳算子等 其它智能機器人路徑規(guī)劃方法 螞蟻算法 一種全局優(yōu)化算法 模仿螞蟻搜索食物的行為 是一種通用型隨機優(yōu)化方法 基于電路地圖的路徑規(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種診斷決策方法 閾值法模糊邏輯貝葉斯分類故障假設(shè)檢驗 機器學習 機器學習為復(fù)雜未知環(huán)境中的信息提取 環(huán)境理解 任務(wù)規(guī)劃和行為決策提供了有效的解決途徑增強學習理論和算法進化學習算法統(tǒng)計學習 支持向量機 SVM 理論和算法