第五章工業(yè)機(jī)器人路徑規(guī)劃教學(xué)教材

第五章機(jī)器人路徑(lùjìng)規(guī)劃機(jī)器人路徑(lùjìng)規(guī)劃第一頁，共29頁。

第五章機(jī)器人路徑(lùjìng)規(guī)劃第一節(jié)路徑規(guī)劃(guīhuà)分類第二頁，共29頁。3一、路徑規(guī)劃(guīhuà)概述

什么是路徑規(guī)劃？

著名學(xué)者蔣新松將路徑規(guī)劃定義為路徑規(guī)劃是移動(dòng)機(jī)器人的一個(gè)(yīɡè)重要組成部分,它的任務(wù)就是在具有障礙物的環(huán)境內(nèi)按照一定的評價(jià)標(biāo)準(zhǔn)如工作代價(jià)最小、行走路線最短、行走時(shí)間最短等,尋找一條從起始狀態(tài)包括位置和姿態(tài)到達(dá)目標(biāo)狀態(tài)包括位置和姿態(tài)的無碰路徑。第五章機(jī)器人路徑(lùjìng)規(guī)劃第三頁，共29頁。4一、路徑(lùjìng)規(guī)劃概述

路徑規(guī)劃需要解決的問題：

1.使機(jī)器人能從初始位置運(yùn)動(dòng)到目標(biāo)位置。2.一定的算法使機(jī)器人能繞開障礙物,并且(bìngqiě)經(jīng)過某些必須經(jīng)過的點(diǎn)完成相應(yīng)的作業(yè)任務(wù)。3.在完成以上任務(wù)的前提下,盡量優(yōu)化機(jī)器人運(yùn)行軌跡。

第五章機(jī)器人路徑(lùjìng)規(guī)劃第四頁，共29頁。5二、路徑(lùjìng)規(guī)劃的分類

按對環(huán)境信息的把握程度分為全局或局部路徑規(guī)劃：

1.基于先驗(yàn)完全(wánquán)信息的是全局路徑規(guī)劃；全局路徑規(guī)劃屬于靜態(tài)規(guī)劃(又稱離線規(guī)劃)。全局路徑規(guī)劃需要掌握所有的環(huán)境信息，根據(jù)環(huán)境地圖的所有信息進(jìn)行路徑規(guī)劃。2.基于傳感器信息的是局部路徑規(guī)劃。局部路徑規(guī)劃屬于動(dòng)態(tài)規(guī)劃(又稱在線規(guī)劃)。局部路徑規(guī)劃只需要由傳感器實(shí)時(shí)采集環(huán)境信息，了解環(huán)境地圖信息，然后確定出所在地圖的位置及其局部的障礙物分布情況，從而可以選出從當(dāng)前結(jié)點(diǎn)到某一子目標(biāo)結(jié)點(diǎn)的最優(yōu)路徑。

。

第五章機(jī)器人路徑(lùjìng)規(guī)劃第五頁，共29頁。第五章機(jī)器人路徑(lùjìng)規(guī)劃第二節(jié)路徑(lùjìng)規(guī)劃方法第六頁，共29頁。7一、路徑規(guī)劃(guīhuà)方法

1.傳統(tǒng)方法(fāngfǎ)：可視圖法、自由空間法、柵格法、人工勢場法

第五章機(jī)器人路徑(lùjìng)規(guī)劃2.智能方法：蟻群算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法3.其他方法：A*算法、Dijkstra算法第七頁，共29頁。8二、可視圖法(túfǎ)

第五章機(jī)器人路徑(lùjìng)規(guī)劃對可視圖進(jìn)行搜索,并利用優(yōu)化算法刪除一些不必要的連線以簡化可視圖,縮短了搜索時(shí)間,最終就可以找到一條無碰最優(yōu)路徑。優(yōu)點(diǎn)是可以求得最短路徑,缺點(diǎn)是此法缺乏靈活性,即一旦(yīdàn)機(jī)器人的起點(diǎn)和目標(biāo)點(diǎn)發(fā)生改變,就要重新構(gòu)造可視圖,比較麻煩。第八頁，共29頁。9三、自由空間法

第五章機(jī)器人路徑(lùjìng)規(guī)劃自由空間法的基本思想是采用預(yù)先定義的基本形狀如廣義錐形,凸多邊形等構(gòu)造自由空間,并將自由空間表示為連通圖,然后通過(tōngguò)對圖的搜索來規(guī)劃路徑,其算法的復(fù)雜度往往與障礙物的個(gè)數(shù)成正比。由兩個(gè)障礙和工作空間邊界(biānjiè)生成的廣義錐1.自由空間法基本思想：第九頁，共29頁。10三、自由空間法

第五章機(jī)器人路徑(lùjìng)規(guī)劃

自由空間法的優(yōu)點(diǎn)是比較靈活,機(jī)器人的起始點(diǎn)和目標(biāo)點(diǎn)的改變不會(huì)造成連通圖的重新(chóngxīn)構(gòu)造。自由空間法的缺點(diǎn)為不是任何時(shí)候都可以獲得最短路徑。2.自由空間法的優(yōu)缺點(diǎn)：由算法(suànfǎ)找到的路徑第十頁，共29頁。11四、柵格法

第五章機(jī)器人路徑(lùjìng)規(guī)劃用編碼的柵格來表示地圖，把包含障礙物的柵格標(biāo)記為障礙柵格，反之則為自由柵格，以此(yǐcǐ)為基礎(chǔ)作路徑搜索。柵格法一般作為路徑規(guī)劃的環(huán)境建模技術(shù)來用，作為路徑規(guī)劃的方法它很難解決復(fù)雜環(huán)境信息的問題，一般需要與其他智能算法相結(jié)合。上圖中灰色(huīsè)區(qū)域?yàn)檎系K物上圖黃色路線為該算法得到的最優(yōu)路徑第十一頁，共29頁。12五、人工(réngōng)勢場法

第五章機(jī)器人路徑(lùjìng)規(guī)劃人工勢場法是一種虛擬力法。它模仿引力斥力下的物體運(yùn)動(dòng)，目標(biāo)點(diǎn)和運(yùn)動(dòng)體間為引力，運(yùn)動(dòng)體和障礙物間為斥力，通過建立引力場斥力場函數(shù)進(jìn)行路徑尋優(yōu)。優(yōu)點(diǎn)是規(guī)劃出來的路徑平滑安全、描述簡單等，但是存在局部最優(yōu)的問題，引力場的設(shè)計(jì)是算法能否(nénɡfǒu)成功應(yīng)用的關(guān)鍵。1.人工勢場法基本思想：第十二頁，共29頁。13第五章機(jī)器人路徑(lùjìng)規(guī)劃五、人工(réngōng)勢場法

第十三頁，共29頁。14五、人工(réngōng)勢場法

第五章機(jī)器人路徑(lùjìng)規(guī)劃2.人工(réngōng)勢場法的兩個(gè)問題：（1)非點(diǎn)形障礙物普通的障礙物的形狀不是一個(gè)點(diǎn)，如何確定一個(gè)障礙物對機(jī)器人的排斥力呢？方案1：計(jì)算障礙物內(nèi)所有點(diǎn)斥力的合力。方案2：用離障礙物最近的點(diǎn)進(jìn)行計(jì)算。（2)死鎖（deadlock）現(xiàn)象第十四頁，共29頁。15五、人工(réngōng)勢場法

第五章機(jī)器人路徑(lùjìng)規(guī)劃2.人工勢場法的兩個(gè)(liǎnɡɡè)問題：（3）避免死鎖的改進(jìn)算法：APF與隨機(jī)采樣相結(jié)合如RPP算法、APF與遺傳算法（GA）相結(jié)合、APF與其他全局優(yōu)化算法相結(jié)合：如：粒群算法，蟻群算法，模擬退火法，附加動(dòng)量法等。第十五頁，共29頁。16六、蟻群算法(suànfǎ)

第五章機(jī)器人路徑(lùjìng)規(guī)劃蟻群算法通過模擬蟻群搜索食物的過程,達(dá)到求解比較困難的組合優(yōu)化問題的目的。該方法是受到對真實(shí)蟻群行為研究的啟發(fā)而提出的。仿生學(xué)家經(jīng)過大量細(xì)致的觀察研究發(fā)現(xiàn)(fāxiàn),螞蟻個(gè)體之間是通過一種稱之為外激素的物質(zhì)進(jìn)行信息傳遞的。螞蟻在運(yùn)動(dòng)過程中,能夠在它所經(jīng)過的路徑上留下該種物質(zhì),而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)的存在及其強(qiáng)度,并以此指導(dǎo)自己的運(yùn)動(dòng)方向,螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象某一路經(jīng)上走過的螞蟻越多,則后來者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過這種信息的交流達(dá)到搜索食物的目的。算法通過迭代來模擬蟻群覓食的行為達(dá)到目的。具有良好的全局優(yōu)化能力、本質(zhì)上的并行性、易于用計(jì)算機(jī)實(shí)現(xiàn)等優(yōu)點(diǎn)，但計(jì)算量大、易陷入局部最優(yōu)解，不過可通過加入精英蟻等方法改進(jìn)。1.蟻群算法基本思想：第十六頁，共29頁。17六、蟻群算法(suànfǎ)

第五章機(jī)器人路徑(lùjìng)規(guī)劃設(shè)A是巢穴,E是食物源,CM為一障礙物。由于障礙物的存在,螞蟻要從A到E或E從到A,只能沿路線(lùxiàn)BCD或BMD通過,各點(diǎn)之間的距離如圖所示。設(shè)每個(gè)單位時(shí)間有50只螞蟻由到達(dá),螞蟻過后留下的激素物質(zhì)量信息素為1,為方便起見,假設(shè)信息素?fù)]發(fā)時(shí)間為10。在初始時(shí)刻,由于路徑BC、BM、CD、DM上均無信息素存在,位于B的螞蟻可以隨機(jī)選擇路徑。2.蟻群算法運(yùn)用分析：第十七頁，共29頁。18六、蟻群算法(suànfǎ)

第五章機(jī)器人路徑(lùjìng)規(guī)劃從統(tǒng)計(jì)的角度可以認(rèn)為開始時(shí)它們(tāmen)以相同的概率選擇路徑BCD、BMD,這樣由于路徑短,相同時(shí)間內(nèi)最終造成通過BCD的螞蟻比通過BMD的多,使得BCD上的信息素比BMD上的多,這樣又吸引更多的螞蟻沿路徑走,直至最終所有螞蟻選擇路徑BCD,從而找到由蟻巢到食物源的最短路徑。由此可見,螞蟻個(gè)體之間的信息交換是一個(gè)正反饋過程。第十八頁，共29頁。19七、神經(jīng)網(wǎng)絡(luò)算法(suànfǎ)（NeuralNetworks）

第五章機(jī)器人路徑(lùjìng)規(guī)劃神經(jīng)網(wǎng)絡(luò)算法是人工智能領(lǐng)域中的一種非常優(yōu)秀的算法，它主要模擬動(dòng)物神經(jīng)網(wǎng)絡(luò)行為，進(jìn)行分布式并行信息處理。但它在路徑規(guī)劃中的應(yīng)用卻并不成功，因?yàn)槁窂揭?guī)劃中復(fù)雜多變的環(huán)境很難用數(shù)學(xué)公式進(jìn)行描述，如果用神經(jīng)網(wǎng)絡(luò)去預(yù)測學(xué)習(xí)樣本分布空間以外的點(diǎn)，其效果必然是非常差。盡管神經(jīng)網(wǎng)絡(luò)具有優(yōu)秀的學(xué)習(xí)能力(nénglì)，但是泛化能力(nénglì)差是其致命缺點(diǎn)。但因其學(xué)習(xí)能力(nénglì)強(qiáng)魯棒性好，它與其他算法的結(jié)合應(yīng)用已經(jīng)成為路徑規(guī)劃領(lǐng)域研究的熱點(diǎn)。第十九頁，共29頁。20八、遺傳算法（GeneticAlgorithms）

第五章機(jī)器人路徑(lùjìng)規(guī)劃遺傳算法是當(dāng)代人工智能科學(xué)的一個(gè)重要研究分支(fēnzhī)，是一種模擬達(dá)爾文遺傳選擇和自然淘汰的生物進(jìn)化過程中的計(jì)算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是按照基因遺傳學(xué)原理而實(shí)現(xiàn)的一種迭代過程的搜索算法。最大的優(yōu)點(diǎn)是易于與其他算法相結(jié)合，并充分發(fā)揮自身迭代的優(yōu)勢，缺點(diǎn)是運(yùn)算效率不高，不如蟻群算法有先天優(yōu)勢，但其改進(jìn)算法也是目前研究的熱點(diǎn)。第二十頁，共29頁。第五章機(jī)器人路徑(lùjìng)規(guī)劃第三節(jié)路徑(lùjìng)規(guī)劃應(yīng)用第二十一頁，共29頁。22一、全球第一個(gè)能自動(dòng)(zìdòng)避開障礙物的機(jī)器人——Shakey

第五章機(jī)器人路徑(lùjìng)規(guī)劃1969年美國斯坦福國際研究所(StanfordResearchInstitute,SRI)研制了移動(dòng)式機(jī)器人Shakey,這是首臺(tái)采用了人工智能學(xué)的移動(dòng)機(jī)器人，Shakey具備一定人工智能，能夠(nénggòu)自主進(jìn)行感知、環(huán)境建模、行為規(guī)劃并執(zhí)行任務(wù)(如尋找木箱并將其推到指定目的位置)。它裝備了電視攝像機(jī)、三角法測距儀、碰撞傳感器、驅(qū)動(dòng)電機(jī)以及編碼器，并通過無線通訊系統(tǒng)由二臺(tái)計(jì)算機(jī)控制。圖像識(shí)別采用麻省理工（MIT）的Image-Understanding算法（Roberts，1965）圖像處理耗時(shí)巨大，shakey的移動(dòng)速度很慢，每小時(shí)只能移動(dòng)幾米。第二十二頁，共29頁。23第五章機(jī)器人路徑(lùjìng)規(guī)劃掃地(sǎodì)機(jī)器人采用隨機(jī)覆蓋法，有人也稱為隨機(jī)碰撞式導(dǎo)航，但這并非是指機(jī)器人真正與環(huán)境中的物體產(chǎn)生碰撞，也非毫無章法的在地板上隨機(jī)移動(dòng)。隨機(jī)覆蓋法是指機(jī)器人根據(jù)一定的移動(dòng)算法，如三角形、五邊形軌跡嘗試性的覆蓋作業(yè)區(qū)，如果遇到障礙，則執(zhí)行對應(yīng)的轉(zhuǎn)向函數(shù)。這種方法是一種(yīzhǒnɡ)以時(shí)間換空間的低成本策略，如不計(jì)時(shí)間可以達(dá)到100%覆蓋率。二、掃地機(jī)器人——ROOMBA第二十三頁，共29頁。24第五章機(jī)器人路徑(lùjìng)規(guī)劃二、掃地(sǎodì)機(jī)器人——ROOMBA隨機(jī)覆蓋法不用定位、也沒有環(huán)境地圖，也無法對路徑進(jìn)行(jìnxíng)規(guī)劃，所以其移動(dòng)路徑基本依賴于內(nèi)置的算法，算法的優(yōu)劣也決定了其清掃質(zhì)量與效率的高低。第二十四頁，共29頁。25第五章機(jī)器人路徑(lùjìng)規(guī)劃二、掃地(sǎodì)機(jī)器人——ROOMBA隨機(jī)覆蓋法不用定位、也沒有環(huán)境地圖(dìtú)，也無法對路徑進(jìn)行規(guī)劃，所以其移動(dòng)路徑基本依賴于內(nèi)置的算法，算法的優(yōu)劣也決定了其清掃質(zhì)量與效率的高低。三、火星探測器—D*算法：D*是動(dòng)態(tài)A*（D-Star,DynamicA*）卡內(nèi)基梅隆機(jī)器人中心的Stentz在1994和1995年兩篇文章提出，主要用于機(jī)器人探路。是火星探測器采用的尋路算法，適合于動(dòng)態(tài)路徑規(guī)劃。D*算法的思路可以推廣到改造自由空間法使其具有動(dòng)態(tài)規(guī)劃功能第二十五頁，共29頁。

第五章機(jī)器人路徑(l