概率性路線圖

概率性路線圖 （英文：probabilistic roadmap, PRM）係機械人學當中嘅一種運動規劃演算法，確定到條路徑喺機械人個起始位形戥目標位形之間嘅（「位形」即「位置」撈「形態」，又譯「組態」，英文：configuration），同時又可以避埋啲碰撞（collisions）。

概率性隨機地圖演算法個示例，探索緊啲圍繞多個多邊形厏埞嘢嘅路徑。

PRM 背後嘅基本思想係從個機械人嘅位形空間裏頭隨機抽到一啲樣本，測試佢哋係咪喺自由空間入便，並且運用本地規劃器（local planner）嘗試捉啲位形連埋其他啲位形喺附近嘅。起始位形同目標位形得到添加之後，對個結果圖形應用圖搜索演算法就確定到起始位形同目標位形之間條路徑。

概率性路線圖規劃器由兩動組成：構建階段同查詢階段。喺構建階段構建一幅路線圖（圖）嚟逼近啲運動係可以喺環境入便達成嘅。詳細嚟講首先，創建一個隨機位形。然之後，連佢到一啲相鄰位形，通常係連嗮 k 個至近嘅鄰居或者某距離範圍內嘅所有鄰居。啲位形同埋啲連接一路着添加到幅圖裏便直到幅路線圖夠密。喺查詢階段，開始同目標位形着連到幅圖上，條最短路徑就可以透過Dijkstra演算法查得到。

畀定某啲相對較弱嘅條件畀個自由空間形狀嘅話，PRM 可以着證明得到係概率完備嘅，意思係隨住啲採樣點嘅數量冇限制噉增加上去，演算法搵唔到路徑（若果條路徑存在）嘅概率接近於零。個收斂速度取決於自由空間嘅某啲可見性性質、由本地規劃器確定嘅。粗粗噉講，若果每粒點都睇得到個空間嘅好大一柵，而且空間嘅每柵子集入便，其中一大柵又可以睇到個補集柵嘅一大柵（一路牐開、細分），係噉個規劃器就好快搵得到一條路徑。

PRM 方法嘅發明歸功於Lydia E. Kavraki。喺基本嘅 PRM 方法基礎上有好多變體，其中一啲複雜之極，係改唨採樣策略同埋連接策略嚟追求實現得到更加快嘅速度；參睇 Geraerts & Overmars (2002) 相關討論。

睇埋

• 快速探索隨機樹（RRT）