度量路徑規(guī)劃-2015717

1、2022-6-81第10章 度量路徑規(guī)劃(metric path planning)2 10.1 目標(biāo)與概述 10.2 結(jié)構(gòu)空間及其表示法 10.3 基于圖的規(guī)劃器 10.4 基于波陣面的規(guī)劃器 10.5 路徑規(guī)劃與反應(yīng)式執(zhí)行的交叉 10.6 小結(jié)310.1 目標(biāo)與概述410.2 結(jié)構(gòu)空間及其表示法 機(jī)器人和障礙物所在的物理空間稱為環(huán)境空間(地圖),將地圖數(shù)字化，得到的一種數(shù)據(jù)結(jié)構(gòu)稱為結(jié)構(gòu)空間。機(jī)器人通過結(jié)構(gòu)空間來確定物體或自身的位姿(位置和姿態(tài))。 下圖顯示了現(xiàn)實(shí)物體到結(jié)構(gòu)空間的轉(zhuǎn)換。510.2.1 牧場地圖 牧場地圖把自由空間轉(zhuǎn)化成凸多邊形。路徑規(guī)劃問題變成求解機(jī)器人所穿過多邊形的最優(yōu)序列

2、的問題。 規(guī)劃器假設(shè)機(jī)器人是完整性的，并把機(jī)器人看做一個(gè)點(diǎn)，然后通過某些特征之間的線段來構(gòu)造凸多邊形。如圖10.3,取中點(diǎn)，形成無向圖。 6圖10.3中任一條路徑都有些據(jù)齒狀,每個(gè)彎曲點(diǎn)都是路途點(diǎn)。一般使用路徑松弛法,可以從路徑中刪掉大部分的鋸齒。如圖10.4存在的問題：1.計(jì)算復(fù)雜2.采用人為標(biāo)志來決定多邊形的邊界，使得機(jī)器人無法準(zhǔn)確操作。3.先驗(yàn)地圖和現(xiàn)實(shí)環(huán)境不相符時(shí)，機(jī)器人無法修正地圖。 710.2.2 廣義Voronoi圖法(Generalized Voronoi Graph)廣義Voronoi圖(GVG),其基本思想是是產(chǎn)生與所有邊界點(diǎn)等距離的線,叫做Voronoi邊,邊之間交匯的點(diǎn)

3、稱為Voronoi頂點(diǎn),如圖10.5。通過與所有障礙物均保持等距離的局部控制策略,機(jī)器入可以很容易地沿著GVG產(chǎn)生的路徑前進(jìn)。810.2.3 正則網(wǎng)格法 正則網(wǎng)格法是在環(huán)境空間上覆蓋一個(gè)二維笛卡爾網(wǎng)格,如果區(qū)域中的物體位于某個(gè)網(wǎng)格單元上,這個(gè)網(wǎng)格單元就被標(biāo)記為被占用,如圖10.6.缺陷：即使物體僅僅占用部分單元網(wǎng)格,仍標(biāo)記被占用,導(dǎo)致自由空間的浪費(fèi)。910.2.4 四叉樹法(Quadtree)四叉樹法是正則網(wǎng)格法的一個(gè)改進(jìn)。在三維情況下的四叉樹稱為八叉樹。1010.3 基于圖的規(guī)劃器11節(jié)點(diǎn)A開始，當(dāng)前只有B和C可供選擇。計(jì)算節(jié)點(diǎn)B和C的可接受性：f(B)=g(B)+h(B)=1+2.24=3

4、 .24f(C)=g(C)+h(C)=1+1=2顯然，f(C)f(B),選擇從A到C這條路徑。 這里假設(shè)每一個(gè)節(jié)點(diǎn)的h(n)都是已知的，因此算法必須遞歸地找出h(n)的正確值，這就需要對每一個(gè)節(jié)點(diǎn)進(jìn)行計(jì)算。1213從D向后，可能的選擇E、F：f*(E)=g*(E)+h*(E)=2.8f*(F)=g*(F)+h*(F)=3.4顯然E是最佳選擇。A*算法優(yōu)點(diǎn):可用于所有結(jié)構(gòu)空間描述法局限性：很難用于除了距離之外還需考慮其他因素的路徑規(guī)劃問題。1410.5 基于波陣面的規(guī)劃器基本原理:波陣面把結(jié)構(gòu)空間視為一種導(dǎo)熱物質(zhì)，如果存在一個(gè)路徑，熱從起始節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)傳導(dǎo)，如圖所示，熱量將最終達(dá)到目標(biāo)節(jié)點(diǎn)。1516波陣面?zhèn)鞑シ梢蕴幚淼匦?。圖10.12中的例子使用的是Trulla規(guī)劃算法。1710.6 路徑規(guī)劃與反應(yīng)式執(zhí)行的交叉度量路徑的反應(yīng)式執(zhí)行時(shí)有兩個(gè)難題：1.子目標(biāo)困擾是指機(jī)器人過分追求精確到達(dá)子目標(biāo)位置而花費(fèi)太多的時(shí)間和能量的情況。2.缺乏重新規(guī)劃的機(jī)會。反應(yīng)式的執(zhí)行方式事實(shí)上缺乏抓住機(jī)會改進(jìn)路徑的能力。兩類方法:D*算法(A*算法的變異)和Trulla算法的擴(kuò)展。兩種算法都從先驗(yàn)地圖開始,計(jì)算每個(gè)位置到目標(biāo)的最優(yōu)路徑。18如圖10.13，機(jī)器人在避障到達(dá)新目標(biāo)點(diǎn)后，不用重新規(guī)劃就可以重新確定最優(yōu)路徑的走向。19Trulla采用預(yù)期路徑向量和實(shí)際