5動態(tài)環(huán)境中的規(guī)劃ppt課件

1、動態(tài)環(huán)境中的規(guī)劃途徑規(guī)劃概要規(guī)劃經(jīng)常是一個反復(fù)過程，且要求快速。動態(tài)環(huán)境不準(zhǔn)確的初始模型真體位置有誤差基于A*的規(guī)劃器類型：ARA*隨時A*搜索輸出 亞優(yōu)解能在有時間約束下運(yùn)用D*與D*精簡版遞增A*搜索經(jīng)過復(fù)用前次搜索結(jié)果來計(jì)算最正確解經(jīng)常能顯著加速反復(fù)規(guī)劃隨時D*(AD*)隨時遞增A*搜索輸出 亞優(yōu)解能在有時間約束下運(yùn)用經(jīng)常能顯著加速反復(fù)規(guī)劃一切都基于ComputePathWithReuse函數(shù)動態(tài)環(huán)境中的自動真體ATRV機(jī)器人Segbot機(jī)器人2D地圖3D地圖規(guī)劃Planning規(guī)劃利用一個問題的構(gòu)造來構(gòu)造一個到達(dá)目的行動方案是以研討理性行動為己任的AI的中心部分途徑規(guī)劃：對求解問題的途

2、徑及其代價進(jìn)展規(guī)劃基于搜索的規(guī)劃離散化機(jī)器人對世界的認(rèn)識規(guī)劃圖基于搜索的規(guī)劃離散化規(guī)劃圖轉(zhuǎn)化成圖形搜索圖形得到一條從sstart到sgoal的最小代價途徑8向銜接網(wǎng)，為什么?機(jī)器人對世界的認(rèn)識基于高維搜索的規(guī)劃2Dx,y規(guī)劃54千個形狀規(guī)劃快執(zhí)行慢4Dx,y,V規(guī)劃超越2千萬個形狀規(guī)劃慢執(zhí)行快基于高維搜索的規(guī)劃6DOF機(jī)器人手臂3x109個形狀20DOF機(jī)器人手臂1026個形狀實(shí)踐規(guī)劃由于下面緣由，需多次再規(guī)劃環(huán)境變化導(dǎo)航時，有人在附近自動駕駛時，有其它車輛在路上環(huán)境模型不準(zhǔn)確位置估計(jì)有誤差需快速再規(guī)劃，來滿足時間約束。實(shí)踐規(guī)劃由于下面緣由，需多次再規(guī)劃環(huán)境變化導(dǎo)航時，有人在附近自動駕駛時，有

3、其它車輛在路上環(huán)境模型不準(zhǔn)確位置估計(jì)有誤差需快速再規(guī)劃，來滿足時間約束。用隨時D*即隨時動態(tài)A*來做4D規(guī)劃實(shí)踐規(guī)劃用隨時D*即隨時動態(tài)A*來做3D停車規(guī)劃用隨時D*即隨時動態(tài)A*來做4D規(guī)劃實(shí)踐規(guī)劃隨時規(guī)劃算法，例如， A*的隨時復(fù)用復(fù)用加權(quán)版，即ARA*快速找到第一個能夠的亞優(yōu)解，然后用其他時間來改良它。允許滿足時間約束。再規(guī)劃算法，例如， A*的遞增版，也即D*與D*精簡版復(fù)用以前規(guī)劃來加速再規(guī)劃很適宜于動態(tài)和/或部分知的環(huán)境。隨時再規(guī)劃算法，例如，隨時遞增A*，即隨時D*結(jié)合上述兩者的優(yōu)點(diǎn)。搜索最小代價途徑計(jì)算相關(guān)態(tài)的g值g(s)：一條從sstart到s的最小代價途徑的代價估值。最正確

4、值滿足： g(s)=minspred(s)(g(s)+c(s,s)由s3到sgoal邊的代價c(s3,sgoal)搜索最小代價途徑最小代價路經(jīng)是由回溯backtracking獲得的一條的貪婪途徑從sgoal開場，并且從任一形狀s移向其前任形狀s，使得：s=argminspred(s)(g(s)+c(s,s)A*搜索計(jì)算相關(guān)態(tài)的最正確g值在某一時辰：g(s)h(s)目前找到的一條從sstart到s最短途徑的代價一條從s到sgoal最短途徑的代價的(低)估值A(chǔ)*搜索計(jì)算相關(guān)態(tài)的最正確g值主函數(shù)：g(sstart)=0；一切其它g值是無窮；OPEN=sstart；ComputePath()；給出結(jié)果

5、；ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；擴(kuò)展s；注：OPEN是擴(kuò)展候選態(tài)的集。假設(shè)啟發(fā)方式是一致性的，那么每個擴(kuò)展態(tài)的g(s)都是最正確的。A*搜索計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展過)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；注：CLOSED是已擴(kuò)展形狀的集。if體中重新給g(s)(=)賦值，

6、是試圖用找到的從sstart到s的途徑來降低g(s)。A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=OPEN=sstart下一個擴(kuò)展形狀：sstartg(s2)g(sstart)+c(sstart,s2)A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f

7、(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstartOPEN=s2下一個擴(kuò)展形狀：s2A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2OPE

8、N=s1,s4下一個擴(kuò)展形狀：s1A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1OPEN=s4,sgoal下一個擴(kuò)展形狀：s4A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CL

9、OSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1,s4OPEN=sgoal,s3下一個擴(kuò)展形狀：sgoalA*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；CLOSED=sstart,s2,s1,s4,sgoal

10、OPEN=s3終了A*搜索：例子計(jì)算相關(guān)態(tài)的最正確g值ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；對每個已擴(kuò)展形狀，g(s)是最正確的。對每個其它形狀，g(s)是一個上限。如今能計(jì)算一條最小代價途徑。加權(quán)A*以f(s)= g(s)+h(s)(1)為次序來擴(kuò)展形狀。亞優(yōu)解：cost(解) cost(最正確解)。在解許多問題時，比A*快得多。A*最正確解的性質(zhì)f(s) =

11、 g(s) + h(s)為次序來擴(kuò)展形狀。C*為最正確途徑的代價，A*搜索：將擴(kuò)展f(s) C*的任何結(jié)點(diǎn)特例：h(s) = 0，f(s) = g(s) UCS搜索，需擴(kuò)展一切當(dāng)前態(tài)的后續(xù)態(tài)h(s) = h*(s)，f(s) = g(s) + h*(s)，只擴(kuò)展一個當(dāng)前態(tài)的最正確后續(xù)態(tài)加權(quán)A*：例如A*11,054次擴(kuò)展代價=168,204 =10的加權(quán)A*1,次擴(kuò)展代價=177,876構(gòu)建隨時搜索執(zhí)行一系列降低的加權(quán)A*搜索：置為大值；while 1，并且仍留有時間來進(jìn)展規(guī)劃執(zhí)行加權(quán)A*搜索；給出當(dāng)前亞優(yōu)解；降低 ； =2.513次擴(kuò)展解=11次挪動 =1.515次擴(kuò)展解=11次挪動 =1.

12、020次擴(kuò)展解=10次挪動構(gòu)建隨時搜索執(zhí)行一系列 降低的加權(quán)A*搜索： =2.513次擴(kuò)展解=11次挪動 =1.515次擴(kuò)展解=11次挪動 =1.020次擴(kuò)展解=10次挪動效率低，這是由于：不同搜索循環(huán)之間的許多形狀值堅(jiān)持不變。應(yīng)復(fù)用上一次搜索的結(jié)果。ARA*：有效隨時(復(fù)用加權(quán))搜索執(zhí)行一系列 降低的加權(quán)A*搜索。修正每次的加權(quán)A*搜索，使其復(fù)用上次搜索結(jié)果。繼續(xù)保證亞優(yōu)解。復(fù)用加權(quán)A*搜索置一切 的初值為無窮；ComputePath函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；(s)=g(s)；對s的每個不在CL

13、OSED中的后續(xù)態(tài)sif g(s)g(s)+c(s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；注： 值是一個形狀在其擴(kuò)展過程中的值。g(s)=minspred(s)(v(s)+c(s,s)OPEN：一個(s)(=)g(s)不一致性形狀的集。其它一切形狀有(s)=g(s) 一致性。復(fù)用加權(quán)A*搜索用一切的不一致性的形狀來初值化OPEN；ComputePathWithReuse函數(shù)：while (sgoal沒有被擴(kuò)展)從OPEN中移去f(s)( = g(s)+h(s)最小的s；把s插入CLOSED；(s)=g(s)；對s的每個不在CLOSED中的后續(xù)態(tài)sif g(s)g(s)+c(

14、s,s)g(s)=g(s)+c(s,s)；把s 插入OPEN；注： 值是一個形狀在其擴(kuò)展過程中的值。g(s)=minspred(s)(v(s)+c(s,s)OPEN：一個(s)g(s)不一致性形狀的集。其它一切形狀有(s)=g(s) 一致性。初始化OPEN時，運(yùn)用上次搜索結(jié)果。例如：復(fù)用A* =1CLOSED=OPEN=s4,sgoal下一個擴(kuò)展形狀：s4g(s)=minspred(s)(v(s)+c(s,s)初始的OPEN包含一切不一致性的形狀例如：復(fù)用A* =1CLOSED=s4OPEN=sgoal,s3下一個擴(kuò)展形狀：sgoal例如：復(fù)用A* =1CLOSED=s4,sgoalOPEN=

15、s3終了如今可以計(jì)算一個最小代價途徑當(dāng)ComputePathWithReuse終止后，一切形狀的g值都等于最終A*的g值?；氐綄?shí)例執(zhí)行一系列 降低的加權(quán)A*搜索： =2.513次擴(kuò)展，解=11次挪動 =1.515次擴(kuò)展，解=11次挪動 =1.020次擴(kuò)展，解=10次挪動ARA*：執(zhí)行一系列 降低的ComputePathWithReuse函數(shù)： =2.513次擴(kuò)展，解=11次挪動 =1.51次擴(kuò)展，解=11次挪動 =1.09次擴(kuò)展，解=10次挪動高維形狀空間的ARA*規(guī)劃0.05秒的ARA*規(guī)劃90秒的ARA*規(guī)劃添加再規(guī)劃功能在動態(tài)環(huán)境下，邊的代價會改動。假設(shè)邊的代價減小，那么可用與上面一樣的

16、ComputePathWithReuse函數(shù)來重新計(jì)算一條途徑；假設(shè)邊的代價添加，那么可用類似的函數(shù)來計(jì)算。最正確再規(guī)劃器：D*與D*精簡版置 為1；執(zhí)行直到到達(dá)目的為止：ComputePathWithReuse()；公布當(dāng)前亞優(yōu)解途徑；沿著該途徑挪動直到探測到某種地圖上沒有的物體為止；更新相應(yīng)的邊的代價；置sgoal為真體的當(dāng)前形狀；參考文獻(xiàn)：S. Koenig and M. Likhachev, “Fast Replanning for Navigation in Unknown Terrain, IEEE Trans. Robotics, 21, (3), 354-363, 2005 最

17、正確再規(guī)劃器：D*與D*精簡版置 為1；執(zhí)行直到到達(dá)目的為止：ComputePathWithReuse()；公布當(dāng)前亞優(yōu)解途徑；沿著該途徑挪動直到探測到某種地圖上沒有的物體為止；更新相應(yīng)的邊的代價；置sgoal為真體的當(dāng)前形狀；注：搜索是向后進(jìn)展的：sstart=真體的目的，sgoal=真體的當(dāng)前形狀，一切的邊是反向的。這樣，在兩次叫ComputePathWithReuse之間，sstart總是不變的，并且g值也很能夠不變。D*與D*精簡版：例如初始知識與初始目的間隔機(jī)器人挪動之后的知識與目的間隔灰色區(qū)域的g值改動D*與D*精簡版：例如初次A*搜索初次D*精簡版搜索二次A*搜索二次D*精簡版搜索隨時再規(guī)劃器：隨時D*置 為大值；執(zhí)行直到到達(dá)目的為止：ComputePathWithReuse()；公布當(dāng)前亞優(yōu)解途徑；沿著該途徑挪動直到探測到某種地圖上沒有的物體為止；更新相應(yīng)的邊的代價；置sgoal為真體的當(dāng)前形狀；if 察看到