《移動(dòng)機(jī)器人路徑規(guī)劃》由會(huì)員分享，可在線閱讀，更多相關(guān)《移動(dòng)機(jī)器人路徑規(guī)劃（29頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、 演講者：呼進(jìn)國 青 島 科 技 大 學(xué) 自 動(dòng) 化 電 子 與 工 程 學(xué) 院 檢 測 技 術(shù) 與 自 動(dòng) 化 裝 置 1.什 么 是 路 徑 規(guī) 劃2.路 徑 規(guī) 劃 的 常 用 方 法 3.人 工 勢 場 法 依據(jù)某種最優(yōu)準(zhǔn)則，在工作空間中尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的避開障礙物的最優(yōu)路徑。 1. 始于初始點(diǎn)止于目標(biāo)點(diǎn)。2. 避障。3. 盡可能優(yōu)化的路徑。 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柵
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、。3.確定從狀態(tài)到行為的映射關(guān)系。 2.32基于模糊邏輯的路徑規(guī)劃方法在基于邏輯推理的路徑規(guī)劃方法基礎(chǔ)進(jìn)行改進(jìn)：傳感器的一次測量值與多個(gè)狀態(tài)對應(yīng)，每個(gè)狀態(tài)有一個(gè)隸屬度對應(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）建模： 對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）1 12 2 22, 2, 3, 3,
4、1, 1 1 12 2min ( . ) ( ) ( ) n nl n n i i i i ii iE 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)行處理： min l cE E wE (EC為懲罰項(xiàng)） 2.34基于遺傳算法的路徑規(guī)劃（3）遺傳算法具有全局尋優(yōu)性能，對上述無約束優(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)勢
5、：神經(jīng)元可以并行計(jì)算 2.4人工勢場法基本原理障礙物對機(jī)器人施加排斥力，目標(biāo)點(diǎn)對機(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è)障礙物對機(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)化算法可以避
6、免落入局部極值。 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：對多面體每個(gè)頂點(diǎn)計(jì)算排斥力和吸引力，障礙物對機(jī)器人的排斥力是對所有頂點(diǎn)排斥力的合力。 3.3人工勢場法的改進(jìn)算法（1）主要是針對死鎖問題進(jìn)行改進(jìn)RP
7、P算法(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)的無碰撞路徑。對于一個(gè)種群來說，就可以得到從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞路徑。3.計(jì)算每個(gè)種群對應(yīng)的路徑的長度作為適配度，對（xi， y i ）進(jìn)行交叉、變異、選擇運(yùn)算得到新的n-2個(gè)參數(shù)。4.重復(fù)上述步驟直至結(jié)束。 3.3人工勢場法的改進(jìn)算法（2）交叉前：交叉后：
移動(dòng)機(jī)器人路徑規(guī)劃
