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