《移動機器人路徑規(guī)劃》由會員分享,可在線閱讀,更多相關(guān)《移動機器人路徑規(guī)劃(29頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、移動機器人路徑規(guī)劃概述 與人工勢場法 整理人:李帥 中國科學(xué)院合肥智能機械研究所 仿生感知實驗室 overview 1.什么是路徑規(guī)劃 2.路徑規(guī)劃的常用方法 3.人工勢場法 1.1 定義 -how should I go there? 依據(jù)某種最優(yōu)準則,在工作空間中尋找一條從起始狀 態(tài)到目標狀態(tài)的避開障礙物的最優(yōu)路徑。 需要解決的問題: 1. 始于初始點止于目標點。 2. 避障。 3. 盡可能優(yōu)化的路徑。 1 .什么是路徑規(guī)劃 2 . 機器人路徑規(guī)劃常用方法 2.4 人工勢場法 2.1 基于幾何構(gòu)造的方法 2.2 柵格法 2.3 智能化路徑規(guī)劃方法 2.1基于幾何構(gòu)造的方法 (自由空間法)
2、 基本步驟: 1.將機器人抽象為點,適當擴大障礙物的 大小。 2.構(gòu)造自由空間。 3.采用圖搜索算法如 Dijkstra算法尋找最 優(yōu)路徑。 2.11基于幾何構(gòu)造的常用算法 可視圖法 Voronoi法 2.2柵格法( 1) 圖中灰 色區(qū) 域為障礙物 2.2柵格法( 2) 圖中黃 色的路 線表示 該算法 得到的 最優(yōu)路 徑 2.2D*( dynamic A*)算法( 3) 美國火星探測器核 心的尋路算法就是 采用的 D*算法 適合于動態(tài)路徑規(guī) 劃 D*算法的思 路可以推廣 到改造自由 空間法使其 具有動態(tài)規(guī) 劃功能 2.3智能化路徑規(guī)劃方法 基于邏輯推理的路徑規(guī)劃方法 基于模糊邏輯的路徑規(guī)劃方法
3、 基于強化學(xué)習的路徑規(guī)劃方法 基于遺傳算法的路徑規(guī)劃方法 基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃方法 2.31基于邏輯推理的路徑規(guī)劃方法 1.定義一個狀態(tài)( state)集, 該集合反映機器人通過傳感 器測得的當前狀態(tài)。 2.定義一個行為( action)集, 該集合反映了機器人當前可 以采取的動作。 3.確定從狀態(tài)到行為的映射關(guān) 系。 2.32基于模糊邏輯的路徑規(guī)劃方法 在基于邏輯推理的路徑規(guī)劃方法基礎(chǔ)進 行改進: 傳感器的一次測量值與多個狀態(tài)對應(yīng),每個 狀態(tài)有一個隸屬度對應(yīng)。 根據(jù)模糊推理結(jié)果確定行為。 2.33基于強化學(xué)習的路徑規(guī)劃 在基于邏輯推理的路徑規(guī)劃方法基礎(chǔ)進 行改進: 具有在線學(xué)習功能(通過
4、Q學(xué)習算法實現(xiàn)) 2.34基于遺傳算法的路徑規(guī)劃( 1) 建模: 對 2維路徑規(guī)劃問題,將待規(guī)劃的路徑看 成是 n個點組成的點集,除初始點和目標點外 其余 n-2個點 ( xi, yi ) i=2,3,4n -1都未 知,共有 2(n-2)個未知參數(shù) 。 2.34基于遺傳算法的路徑規(guī)劃( 2) 11 2 2 2 2 , 2 , 3, 3, 1 , 1 1 1 22 m in ( . . . ) ( ) ( ) nn l n n i i i i i ii E f x y x y x y L x x y y 優(yōu)化目標: 約束: ( xi, yi )必須在障礙物外部。 采用懲罰函數(shù)法轉(zhuǎn)化為 無約束優(yōu)
5、化問題 進行處理: m i n lcE E w E (EC為懲罰項) 2.34基于遺傳算法的路徑規(guī)劃( 3) 遺傳算法具有全局尋優(yōu)性能,對上述無 約束優(yōu)化問題可以得到全局最優(yōu)解。 當然,其他的優(yōu)化算法同樣可以用于路 徑規(guī)劃。 2.35基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃 1.按照 2.34的方法,轉(zhuǎn)化為優(yōu) 化問題。 2.用神經(jīng)網(wǎng)絡(luò)表示懲罰函數(shù)。 3根據(jù) E遞減推導(dǎo)出相應(yīng)的反 向傳播算法用于神經(jīng)網(wǎng)絡(luò)的訓(xùn) 練 . 優(yōu)勢: 神經(jīng)元可以并行計算 2.4人工勢場法基本原理 障礙物對機器人施加排斥力,目 標點對機器人施加吸引力合力形 成勢場,機器人移動就像球從山 上滾下來一樣 機器人在合力作用下向目標 點移動 3.人工
6、勢場法 3.1人工勢場法的基本原理( 2.4) 3.2人工勢場法的實用算法 3.3人工勢場法的改進算法 3.2人工勢場法的實用算法 3.21非點形障礙物問題 普通的障礙物的形狀不是一個點,如何 確定一個障礙物對機器人的排斥力呢? 方案 1:計算障礙物內(nèi)所有點斥力的合力。 方案 2:用離障礙物最近的點進行計算。 方案 3: 3.22死鎖( dead lock)現(xiàn)象( 1) 如何克服死鎖現(xiàn)象: 死鎖現(xiàn)象的實質(zhì)是落入局部極 值,全局優(yōu)化算法可以避免落入局 部極值。 3.22死鎖( dead lock)現(xiàn)象( 2) 避免死鎖的改進算法: APF與隨機采樣相結(jié)合如 RPP算法 APF與遺傳算法( GA)
7、相結(jié)合 APF與其他全局優(yōu)化算法相結(jié)合: 如:粒群算法,蟻群算法,模擬退火法,附加 動量法等。 3.23GNRON問題: 障礙物與目標點過于接近引起斥力場和引力場 同時存在而阻礙到達目標點的現(xiàn)象。 解決方案: 3.24移動機器人為多面體的情況 方案 1:一般情況下,可以將機器人作為 點,適當擴大障礙物來進行研究。 方案 2:對多面體每個頂點計算排斥力和 吸引力,障礙物對機器人的排斥力是對 所有頂點排斥力的合力。 3.3人工勢場法的改進算法( 1) 主要是針對死鎖問題進行改進 RPP算法 (APF與隨機采樣相結(jié)合) 的原理: 1.開始時執(zhí)行 Descend模式 2.如果沒有出現(xiàn)死鎖則成功,否則執(zhí)
8、行 Escape模式 3.如果 Escape模式失敗,執(zhí)行 Backtrack模式 3.3人工勢場法的改進算法( 2) 一種 APF與 GA相結(jié)合的算法: 在基于 GA的路徑規(guī)劃算法( 2.34)中介 紹了 GA如何用于路徑規(guī)劃,但是這種算法 存在著計算量 (n) 與路徑規(guī)劃的質(zhì)量之間的 矛盾。采用 APF與 GA結(jié)合的算法可以取較 小的 n獲得滿意的效果并且避免死鎖。 3.3人工勢場法的改進算法( 2) APF與 GA相結(jié)合的算法原理: 1.選取初始可行種群,每個種群中具有 n-2個參數(shù) ( xi, yi ) ( 2.34)。 2. 每一個種群中 ,在相鄰兩個點( xi, yi )和( xi+1, yi+1 ) 之間利用 APF得到一條連接這兩個點的無碰撞路徑。 對于一個種群來說,就可以得到從起始點到目標點的 無碰撞路徑。 3.計算每個種群對應(yīng)的路徑的長度作為適配度,對 ( xi, yi ) 進行交叉、變異、選擇運算得到新的 n-2個參數(shù)。 4.重復(fù)上述步驟直至結(jié)束。 3.3人工勢場法的改進算法( 2) 交叉前: 交叉后: