概率路圖

機率路圖，通常簡稱 PRM，是一張可重複使用的「安全位置道路網」：機器人只建一次，之後卻能反覆在上面行駛。可以類比一座城市的道路地圖——只需測繪和繪製一次，之後任何司機都能在上面規劃任意兩個地址之間的行程。PRM 為機器人做的也是同一件事：在較慢的第一階段，它在「機器人所有可能動作」所構成的空間裡隨機撒下許多姿態，只保留不發生碰撞的那些，再把附近的安全姿態用短連線連起來，而這些連線同樣會被檢查為無碰撞。最終得到的是一張圖——由一個個點（安全姿態）和連接它們的邊（安全動作）組成——它刻畫出了自由空間裡可通行的形狀。

這張路圖一旦建好，回應一次規劃請求就很快了。要從某個起始姿態走到某個目標姿態，規劃器只需把它們各自連到路圖上最近的點，然後在這張網路上跑一次普通的圖搜尋（比如戴克斯特拉演算法或 A*）來找出一條路線。由於取樣和碰撞檢查這些費時的工作已經在前期一次做完，之後每一次新的查詢都很便宜——這正是為什麼 PRM 被稱為「多查詢」規劃器：地圖建一次，卻能為許多不同的起點—目標對反覆複用。

它的價值，恰恰體現在世界保持靜止、而機器人必須在其中往返許多趟的時候——比如一隻整天從固定料箱裡取件的機械臂，或是一台在不變的樓宇裡巡邏的移動機器人。它的缺點正是這份長處的反面：一旦障礙物移動了，路圖上的某些邊可能就不再無碰撞，其中很大一部分就必須重建。對於在變化或未知空間裡做一次性規劃而言，像快速擴展隨機樹那樣「一次成型」的方法，通常更為合適。