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