智聯(lián)網(wǎng)汽車技術(shù) 課件 6.4基于采樣的路徑規(guī)劃算法

基于采樣的路徑規(guī)劃算法項目三汽車決策控制系統(tǒng)任務(wù)6路徑規(guī)劃系統(tǒng)主講人：楊時川智能網(wǎng)聯(lián)汽車技術(shù)課程導(dǎo)入想象一下，如果讓汽車在一個復(fù)雜動態(tài)環(huán)境中快速規(guī)劃出一條安全駕駛路徑，應(yīng)該如何高效實現(xiàn)呢?學(xué)習(xí)目標(biāo)學(xué)習(xí)基于采樣的路徑規(guī)劃的幾種算法01學(xué)會解釋基于采樣的路徑規(guī)劃算法及其效率優(yōu)勢02學(xué)習(xí)任務(wù)共同完成對幾種典型采樣算法的介紹01激活舊知隨機采樣搜索與傳統(tǒng)全局搜索有什么不同嗎?隨機采樣搜索更高效傳統(tǒng)全局搜索時間長探索新知基于隨機采樣的路徑規(guī)劃算法適用于高維度空間，由于求解時間是有限制的，大部分情況下只能得到一個概率層面上的最優(yōu)路徑，可提高搜索效率。基于隨機采樣的路徑規(guī)劃算法探索新知基于隨機采樣的路徑規(guī)劃算法基于隨機采樣的路徑規(guī)劃算法單查詢算法漸近最優(yōu)算法找到可行路徑，側(cè)重快速性找到的路徑進行逐步優(yōu)化達到最優(yōu)，側(cè)重最優(yōu)性探索新知基于隨機采樣的路徑規(guī)劃算法概率路圖法PRM(ProbabilisticRoadMap)算法隨機擴展樹法RRT(Rapidly-exploringRandomTrees)算法動態(tài)窗口法DWA算法探索新知隨機路圖法（PRM）以圖結(jié)構(gòu)為基礎(chǔ)的路徑規(guī)劃算法分為兩個階段：學(xué)習(xí)階段和查詢階段首先將連續(xù)空間轉(zhuǎn)換成離散空間，在規(guī)劃空間內(nèi)隨機選取N個節(jié)點。隨機路圖法（PRM）探索新知隨機路圖法（PRM）學(xué)習(xí)階段（構(gòu)建圖）在有起始點和目標(biāo)點的C-空間內(nèi)隨機撒下N個粒子刪除在障礙物中的點每個點連接到最近的點，得到無碰路徑圖距離太長或者連線有經(jīng)過障礙物的，不連接探索新知隨機路圖法（PRM）查詢階段（搜索路徑）在路線圖上搜索以找到從開始到目標(biāo)的路徑(使用Dijkstra's或A*)路線圖與網(wǎng)格圖（或簡化的網(wǎng)格圖相似）探索新知小貼士隨機路圖法（PRM）的算法過程？從構(gòu)建的圖上的起點使用圖搜索算法(A*、Dijkstra)規(guī)劃一條從起點到終點的路徑，然后將每個點與它相鄰的點(一定距離內(nèi))連接起來，剔除碰到障礙物的連接。連續(xù)空間轉(zhuǎn)換成離散空間構(gòu)建圖（紅色和綠色的線不連接）剔除碰到障礙物的連接搜索路徑探索新知隨機路圖法（PRM）在多數(shù)問題上，相對少的樣本足夠來覆蓋大分的可行空間，并且找到路徑的概率為百分之百。當(dāng)隨機采樣點太少或分布不合理時，PRM算法是不完備的，但隨著采用點的增加可以達到完備，所以PRM是概率完備且不最優(yōu)的。探索新知快速探索隨機樹路徑規(guī)劃方法（RRT）一種適用于多維空間中路徑規(guī)劃方法以一個初始點作為根節(jié)點，通過隨機對空間中的路徑點進行采樣來增添子節(jié)點，以此構(gòu)造一個隨機擴展樹。當(dāng)隨機樹中的子節(jié)點進入了目標(biāo)點所在的目標(biāo)區(qū)域內(nèi)時，已成功尋找到路徑。該方法得到的路徑是一條蜿蜒曲折的路徑?？焖偬剿麟S機樹路徑規(guī)劃方法（RRT）探索新知快速探索隨機樹路徑規(guī)劃方法（RRT）與PRM方法相似，該方法也是概率不完備的，利用該方法所求得的最終路徑往往不是最優(yōu)，而且當(dāng)面對狹窄通道型障礙物時，RRT算法往往需要花費很多時間進行隨機樹擴展才可以找到出口。探索新知快速探索隨機樹路徑規(guī)劃方法（RRT）PRM算法：在一開始就通過抽樣在地圖上構(gòu)建出完整的無向圖，再進行圖搜索RRT算法：從某個點出發(fā)一邊搜索，一邊抽樣并建圖探索新知動態(tài)窗口法根據(jù)機器人或自動駕駛汽車當(dāng)前的線速度和角速度，在速度空間中進行采樣，通過所設(shè)計的評價指標(biāo)對一定時間內(nèi)的運動軌跡進行評價，并選擇最優(yōu)軌跡所對應(yīng)的控制量對機器人或車輛進行控制。DWA算法（動態(tài)窗口法）探索新知動態(tài)窗口法DWA算法核心采樣動態(tài)規(guī)劃空間維度的采樣（軌跡采樣）時間維度的采樣（速度采樣）探索新知動態(tài)窗口法動態(tài)窗口法中，在不同場景下需要進行代價函數(shù)的選擇和設(shè)計DWA算法的仿真結(jié)果需考慮的因素01保證機器人或者自動駕駛汽車行進方向不會頻繁切換02不會與障礙物或者道路邊緣發(fā)生碰撞03航向角沒有突變04局部路徑方向與目標(biāo)點方向一致05速度在區(qū)間內(nèi)