第五章機器人路徑規(guī)劃機器人路徑規(guī)劃第五章機器人路徑規(guī)劃機器人路徑規(guī)劃

第五章機器人路徑規(guī)劃第一節(jié)路徑規(guī)劃分類第五章機器人路徑規(guī)劃第一節(jié)路徑規(guī)劃分類3一、路徑規(guī)劃概述

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

著名學(xué)者蔣新松將路徑規(guī)劃定義為路徑規(guī)劃是移動

機器人的一個重要組成部分,它的任務(wù)就是在具有障礙物

的環(huán)境內(nèi)按照一定的評價標準如工作代價最小、行走路

線最短、行走時間最短等,尋找一條從起始狀態(tài)包括位置

和姿態(tài)到達目標狀態(tài)包括位置和姿態(tài)的無碰路徑。第五章機器人路徑規(guī)劃3一、路徑規(guī)劃概述什么是路徑規(guī)劃？第五章機器人路徑規(guī)劃4一、路徑規(guī)劃概述

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

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

第五章機器人路徑規(guī)劃4一、路徑規(guī)劃概述路徑規(guī)劃需要解決的問題：第五章機器人路徑5二、路徑規(guī)劃的分類

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

1.基于先驗完全信息的是全局路徑規(guī)劃；全局路徑規(guī)劃屬于靜態(tài)規(guī)劃(又稱離線規(guī)劃)。全局路徑規(guī)劃需要掌握所有的環(huán)境信息，根據(jù)環(huán)境地圖的所有信息進行路徑規(guī)劃。

2.基于傳感器信息的是局部路徑規(guī)劃。局部路徑規(guī)劃屬于動態(tài)規(guī)劃(又稱在線規(guī)劃)。局部路徑規(guī)劃只需要由傳感器實時采集環(huán)境信息，了解環(huán)境地圖信息，然后確定出所在地圖的位置及其局部的障礙物分布情況，從而可以選出從當前結(jié)點到某一子目標結(jié)點的最優(yōu)路徑。

。

第五章機器人路徑規(guī)劃5二、路徑規(guī)劃的分類按對環(huán)境信息的把握程度分為全局或局部路徑第五章機器人路徑規(guī)劃第二節(jié)路徑規(guī)劃方法第五章機器人路徑規(guī)劃第二節(jié)路徑規(guī)劃方法7一、路徑規(guī)劃方法

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

第五章機器人路徑規(guī)劃2.智能方法：蟻群算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法3.其他方法：A*算法、Dijkstra算法7一、路徑規(guī)劃方法第五章機器人路徑規(guī)劃2.智能方法：蟻群算8二、可視圖法

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

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

第五章機器人路徑規(guī)劃

自由空間法的優(yōu)點是比較靈活,機器人的起始點和目標點的改變不會造成連通圖的重新構(gòu)造。自由空間法的缺點為不是任何時候都可以獲得最短路徑。2.自由空間法的優(yōu)缺點：由算法找到的路徑10三、自由空間法第五章機器人路徑規(guī)劃2.自由空間11四、柵格法

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

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

13第五章機器人路徑規(guī)劃五、人工勢場法14五、人工勢場法

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

第五章機器人路徑規(guī)劃2.人工勢場法的兩個問題：（3）避免死鎖的改進算法：APF與隨機采樣相結(jié)合如RPP算法、APF與遺傳算法（GA）相結(jié)合、APF與其他全局優(yōu)化算法相結(jié)合：如：粒群算法，蟻群算法，模擬退火法，附加動量法等。15五、人工勢場法第五章機器人路徑規(guī)劃2.人工勢場法的兩個16六、蟻群算法

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

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

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

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

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

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

第五章