PRM

20世紀90年代初期M.H.Overmars等人提出的Probabilistic Roadmap Method。此方法是基於採樣演演算法的一種，很好的解決了在高維空間中構造出有效路徑圖的困難。該演演算法通過在構形空間中進行採樣、對採樣點進行碰撞檢測、測試相鄰採樣點是否能夠連接來表示路徑圖的連通性。此方法的一個巨大優點是，其複雜度主要依賴於尋找路徑的難度，跟整個規劃場景的大小和構形空間的維數關係不大。然而當規劃的路徑需要通過密集的障礙物或者需要經過狹窄的通道時，PRM方法的效率變的低下。

路線圖演演算法（probabilistic roadmap method，PRM）主要分為兩個階段，離線學習階段中隨機採樣大量的機器人位姿點，為每個節點搜索鄰居節點並建立連接，構建出路標地圖；在線查詢階段中根據起始點，目標點，路標地圖信息，採用啟髮式搜索演演算法從路標圖中搜索出一條可行路徑。路線圖演演算法可以有效避免對位姿空間中障礙物進行精確建模，能夠有效解決複雜的運動動力學約束下的路徑規劃問題。