移動(dòng)機(jī)器人路徑規(guī)劃課件

移動(dòng)機(jī)器人路徑規(guī)劃概述

與人工勢(shì)場(chǎng)法

整理人：李帥仿生感知實(shí)驗(yàn)室overview1.什么是路徑規(guī)劃2.路徑規(guī)劃的常用方法

3.人工勢(shì)場(chǎng)法

1.1定義-----howshouldIgothere？依據(jù)某種最優(yōu)準(zhǔn)則，在工作空間中尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的避開(kāi)障礙物的最優(yōu)路徑。需要解決的問(wèn)題： 1.始于初始點(diǎn)止于目標(biāo)點(diǎn)。 2.避障。 3.盡可能優(yōu)化的路徑。1.什么是路徑規(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.2D*（dynamicA*)算法（3）美國(guó)火星探測(cè)器核心的尋路算法就是采用的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ī)器人通過(guò)傳感器測(cè)得的當(dāng)前狀態(tài)。2.定義一個(gè)行為（action）集，該集合反映了機(jī)器人當(dāng)前可以采取的動(dòng)作。3.確定從狀態(tài)到行為的映射關(guān)系。2.33基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在基于邏輯推理的路徑規(guī)劃方法基礎(chǔ)進(jìn)行改進(jìn)：具有在線學(xué)習(xí)功能（通過(guò)Q學(xué)習(xí)算法實(shí)現(xiàn)）2.34基于遺傳算法的路徑規(guī)劃（1）建模： 對(duì)2維路徑規(guī)劃問(wèn)題，將待規(guī)劃的路徑看成是n個(gè)點(diǎn)組成的點(diǎn)集，除初始點(diǎn)和目標(biāo)點(diǎn)外其余n-2個(gè)點(diǎn){（xi，yi）}i=2,3,4…n-1都未知，共有2(n-2)個(gè)未知參數(shù)。2.34基于遺傳算法的路徑規(guī)劃（2）優(yōu)化目標(biāo)：約束：（xi，yi）必須在障礙物外部。采用懲罰函數(shù)法轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題進(jìn)行處理：(EC為懲罰項(xiàng)）2.35基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃1.按照2.34的方法，轉(zhuǎn)化為優(yōu)化問(wèn)題。2.用神經(jīng)網(wǎng)絡(luò)表示懲罰函數(shù)。3根據(jù)E遞減推導(dǎo)出相應(yīng)的反向傳播算法用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練.優(yōu)勢(shì)：神經(jīng)元可以并行計(jì)算2.4人工勢(shì)場(chǎng)法基本原理障礙物對(duì)機(jī)器人施加排斥力，目標(biāo)點(diǎn)對(duì)機(jī)器人施加吸引力合力形成勢(shì)場(chǎng)，機(jī)器人移動(dòng)就像球從山上滾下來(lái)一樣機(jī)器人在合力作用下向目標(biāo)點(diǎn)移動(dòng)3.人工勢(shì)場(chǎng)法3.1人工勢(shì)場(chǎng)法的基本原理（2.4）3.2人工勢(shì)場(chǎng)法的實(shí)用算法3.3人工勢(shì)場(chǎng)法的改進(jìn)算法3.21非點(diǎn)形障礙物問(wèn)題普通的障礙物的形狀不是一個(gè)點(diǎn)，如何確定一個(gè)障礙物對(duì)機(jī)器人的排斥力呢？方案1：計(jì)算障礙物內(nèi)所有點(diǎn)斥力的合力。方案2：用離障礙物最近的點(diǎn)進(jìn)行計(jì)算。方案3：3.22死鎖（deadlock）現(xiàn)象（1）如何克服死鎖現(xiàn)象：死鎖現(xiàn)象的實(shí)質(zhì)是落入局部極值，全局優(yōu)化算法可以避免落入局部極值。3.22死鎖（deadlock）現(xiàn)象（2）避免死鎖的改進(jìn)算法：APF與隨機(jī)采樣相結(jié)合如RPP算法APF與遺傳算法（GA）相結(jié)合APF與其他全局優(yōu)化算法相結(jié)合：如：粒群算法，蟻群算法，模擬退火法，附加動(dòng)量法等。3.24移動(dòng)機(jī)器人為多面體的情況方案1：一般情況下，可以將機(jī)器人作為點(diǎn)，適當(dāng)擴(kuò)大障礙物來(lái)進(jìn)行研究。方案2：對(duì)多面體每個(gè)頂點(diǎn)計(jì)算排斥力和吸引力，障礙物對(duì)機(jī)器人的排斥力是對(duì)所有頂點(diǎn)排斥力的合力。3.3人工勢(shì)場(chǎng)法的改進(jìn)算法（1）主要是針對(duì)死鎖問(wèn)題進(jìn)行改進(jìn)RPP算法(APF與隨機(jī)采樣相結(jié)合）的原理：1.開(kāi)始時(shí)執(zhí)行Descend模式