20世紀90年代初期M.H.Overmars等人提出的Probabilistic Roadmap Method。此方法是基於採樣算法的一種，很好的解決了在高維空間中構造出有效路徑圖的困難。該算法通過在構形空間中進行採樣、對採樣點進行碰撞檢測、測試相鄰採樣點是否能夠連線來表示路徑圖的連通性。此方法的一個巨大優點是，其複雜度主要依賴於尋找路徑的難度，跟整個規劃場景的大小和構形空間的維數關係不大。 然而當規劃的路徑需要通過密集的障礙物或者需要經過狹窄的通道時，PRM方法的效率變的低下。
路線圖算法（probabilistic roadmap method，PRM）主要分為兩個階段，離線學習階段中隨機採樣大量的機器人位姿點，為每個節點搜尋鄰居節點並建立連線，構建出路標地圖；線上查詢階段中根據起始點，目標點，路標地圖信息，採用啟發式搜尋算法從路標圖中搜尋出一條可行路徑。路線圖算法可以有效避免對位姿空間中障礙物進行精確建模，能夠有效解決複雜的運動動力學約束下的路徑規劃問題。
