Probabilistic RoadMap(RPM) Planner是機器人領域一個經典的運動規劃算法，它可以有效解決高維空間和複雜約束中的路徑規劃問題。
PRM本質上是一種圖搜索算法，它通過隨機採樣將連續空間轉換成離散空間，再利用A*、Dijkstra等搜索算法在路線圖上尋找有效路徑。對於絕大多數問題而言，用相對較少的樣本足可以覆蓋大部分可行空間，並且找到一條可行路徑，當然當採樣點太少，或者分佈不合理時，PRM算法是不完備的，隨著採樣點的增加，也可以達到概率完備的狀態。
Probabilistic RoadMap(RPM) 包含兩個階段： construction 和 query phase
圖構建階段(construction)
在給定的自由空間裡隨機撒點
剔除無效的採樣點
採用某種策略構建圖結構
去除無效連接
得到一份概率路線圖
查詢(query)階段
採用圖搜索算法獲取start到end的路徑。
算法描述
圖構建算法
圖搜索算法
可以基於Dijkstra或者A*算法做路徑搜索。
分享到:
閱讀更多 半杯茶的小酒杯 的文章
