Probabilistic Roadmap

• 又稱: PRM, probabilistic roadmap method
• 類別: Planning & manipulation › Motion planning
• 標籤: motion-planning, sampling-based-planning, path-planning, graph-search, manipulation

一種以取樣為基礎的運動規劃器，建立一張可重複使用的圖，包含隨機的無碰撞組態以及它們之間的可行路徑，再以圖搜尋回答規劃查詢。

定義

機率路線圖（Probabilistic Roadmap，PRM）是一種以取樣為基礎的運動規劃方法，由 Kavraki、Švestka、Latombe 與 Overmars 於 1996 年提出。PRM 不會針對每個請求重新搜尋組態空間，而是先建立一張捕捉機器人自由空間連通性的圖，也就是路線圖，再用這張圖回答任意數量的起點到目標查詢。

規劃分為兩個階段。在建構階段，規劃器隨機取樣機器人的組態，把無碰撞的組態保留為節點，並嘗試以簡單的局部規劃器把每個節點與附近的節點相連；局部規劃器通常是組態空間中的一條直線，並以細小的間隔做碰撞檢查。成功的連線就成為邊。在查詢階段，起點與目標組態會連接到路線圖上，再以 Dijkstra 演算法或 A* 等圖搜尋在其中找出一條路徑。

PRM 適合多查詢問題，也就是環境是靜態的、機器人必須在同一空間中規劃許多動作的情況，因為成本高昂的路線圖建構只需做一次。它具有機率完備性：若路徑存在，路線圖包含一條路徑的機率會隨樣本數增加而趨近 1。

它的主要弱點是狹窄通道。均勻的隨機樣本很少落在自由空間中狹窄的區域，因此路線圖可能無法連通實際上相連的區域。為了解決這個問題，人們發展出偏向取樣的策略，例如在障礙物邊界附近取樣。PRM* 是一種變體，它藉由選擇連線半徑使路線圖具有漸近最佳性。

為何重要

PRM 證明了隨機取樣能讓運動規劃在多自由度的機器人上變得實際可行，而在這類機器人上，精確方法難以處理。只要機器人在同一環境中反覆工作，例如固定的工業工作站，它的路線圖概念就依然有用。

主要應用

• 固定工作站中機器手臂的多查詢運動規劃
• 靜態地圖中移動機器人的路徑規劃
• 人形機器人與雙臂機器人等高自由度系統的規劃
• 以取樣為基礎之規劃的教學與基準測試

實際應用

團隊通常透過 OMPL 使用 PRM，在機器手臂規劃上則常經由 MoveIt 使用，在那裡 PRM 與 PRM* 和 RRT-Connect 等以樹為基礎的規劃器並列。由於路線圖可以儲存並重複使用，PRM 適合固定的工作站，在其中機器手臂圍繞同一批治具在許多姿態之間移動：路線圖離線建立、在執行時查詢，只在物體可能已移動之處重新做碰撞檢查。工程師會調整樣本數與連線半徑，並留意路線圖中不連通的部分，這通常表示有一個需要更多或更有針對性之樣本的狹窄通道。

常見誤解

• 只要路徑存在，PRM 就一定找得到 — 它是機率完備的，因此這項保證只在樣本數趨近無限的極限下成立
• PRM 主要用於 2D 地圖 — 它主要用在高維組態空間，例如機器手臂的關節空間
• 路線圖永遠有效 — 如果障礙物移動，受影響的邊必須重新檢查，或重新建立路線圖

誰需要了解

• 運動規劃工程師
• 工業機器人工作站整合商
• 操作研究人員
• 學習以取樣為基礎之規劃的機器人學生

相關技術

• OMPL
• MoveIt
• RRT
• PRM*
• A 搜尋（A Search）
• 組態空間（Configuration Space）

相關術語

• Motion Planning
• RRT*
• Configuration Space

相關專案

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

影片

• Modern Robotics, Chapter 10.5: Sampling Methods for Motion Planning (Part 1 of 2): Northwestern Robotics