PRM（Probabilistic Road Map）算法，機率路線圖算法，是一種用於路徑規劃的算法，特別適用於高維空間和具有複雜障礙物環境的情況。該算法的主要優點是能夠處理高維空間中的路徑規劃問題，且在處理這類問題時具有機率完備性，這意味著隨著採樣點的增加，找到路徑的可能性趨近於1。PRM算法的主要階段包括：
離線學習階段。在這個階段，算法會在機器人工作空間中隨機生成一系列路標點，並進行碰撞檢測以確保這些點是安全的（即不在障礙物上）。然後，算法會建立這些路標點之間的連線，形成一張機率路網圖。
線上查詢階段。給定起始點和目標點，算法使用圖搜尋算法（如Dijkstra算法或A*算法）在機率路網圖中尋找一條從起始點到目標點的路徑。這一階段的目標是在已經建立的路網圖中找到一條從起點到終點的可行路徑。
PRM算法的關鍵參數包括採樣點的數量和採樣點間的最大距離，這些參數會影響路徑規劃的成功率。如果採樣點太少，可能導致無法覆蓋所有可行的空間；而如果採樣點間的最大距離設定得太小，也可能導致無法生成完整的路網圖。此外，PRM算法不需要對環境中的障礙物進行精確建模，能夠有效地解決具有複雜運動動力學約束的路徑規劃問題。然而，該算法在處理需要通過密集障礙物或狹窄通道的情況時效率較低。