Open Source Robotics

精選高品質的開源機器人專案、工具與軟體，推動機器人社群向前發展。

Rapidly-exploring random tree

  • 又稱: RRT
  • 類別: Planning & manipulation › Motion planning
  • 標籤: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

一種以取樣為基礎的運動規劃器，從起始狀態長出一棵樹，反覆隨機取樣一個狀態，並把最近的樹節點朝它延伸，以快速探索大型空間。

定義

快速探索隨機樹（Rapidly-exploring random tree，RRT）是一種以取樣為基礎的演算法，用來找出一條從起始狀態到目標區域的可行路徑。它由 Steven LaValle 於 1998 年提出。演算法會長出一棵以起點為根的樹：每次迭代時，它在組態空間或狀態空間中隨機取樣一個狀態，找出樹中最近的節點，並從該節點朝樣本延伸一小段距離。如果延伸沒有碰撞，新狀態就加入樹中。當樹到達目標區域時搜尋結束，再沿著每個節點的父節點回溯讀出路徑。

關鍵性質是 Voronoi 偏向。位於樹前緣的節點擁有最大的 Voronoi 區域，因此最可能是離隨機樣本最近的節點，於是樹會被拉往未探索的空間，而不是填滿已經涵蓋的區域。這讓 RRT 在高維空間中很有效，例如機器手臂的關節空間。RRT 具有機率完備性：若解存在，隨著樣本數增加，找到它的機率趨近於 1。常見的改良包括目標偏向，也就是有一部分樣本直接取在目標處，以及 RRT-Connect，它同時從起點與目標長出樹，並嘗試以貪婪方式把它們接起來。

由於延伸步驟只需要一種從某個狀態朝另一個狀態移動的方法，RRT 也能處理運動動力學規劃（kinodynamic planning），也就是機器人無法在其狀態空間中沿直線移動的情況。這時延伸步驟會施加取樣或最佳化得到的控制量，並向前模擬動力學，如 LaValle 與 Kuffner 的運動動力學 RRT，或是串接預先計算好的運動基元。這使它適用於車輛、足式機器人與富含接觸的操作，在這些情況中，距離度量與延伸步驟必須圍繞動力學來設計。RRT 的路徑通常曲折且非最佳，而且一旦找到路徑，增加樣本也不會改善它。RRT\ 加入了選擇父節點的步驟與重新連線的步驟，只要存在成本更低的路線，就重新連接附近的節點，這讓它具有漸近最佳性，代價是每個樣本需要更多運算。當需要快速得到可行路徑時，單純的 RRT 或 RRT-Connect 再加上捷徑化與平滑化，仍是常見的選擇。

為何重要

RRT 讓運動規劃在多自由度機器人與具有動力學的系統上變得實用，至今仍是 OMPL 與 MoveIt 等函式庫中的預設規劃器。許多後來的規劃器，包括 RRT*，都建立在它的結構之上。

主要應用

  • 雜亂工作空間中的機器手臂運動規劃
  • 汽車、無人機與足式機器人的運動動力學規劃
  • 使用自訂距離度量的富含接觸操作規劃
  • 在運動基元圖上為移動進行規劃
  • 探索未知環境

實際應用

一個團隊為從貨架上揀取物品的七軸機器手臂設定 MoveIt，把 OMPL 的 RRT-Connect 當作預設規劃器。碰撞檢查使用機器人模型與由深度攝影機建立的八元樹。他們依貨架開口的間隙設定規劃時間上限與延伸步長，再對每條路徑做捷徑化與時間參數化的後處理，讓手臂平順地移動。當規劃難以深入狹窄的貨架格位時，他們會提高目標偏向，或改試一個在狹窄通道表現較好的規劃器；而對於靜態工作單元中的重複查詢，他們會考慮改用機率路線圖。

常見誤解

  • RRT 會找到最短路徑 — 它找到的是一條可行路徑；要得到良好的路徑品質，需要 RRT* 或後處理
  • RRT 保證能在設定時間內找到路徑 — 它具有機率完備性，因此隨著取樣持續，找到路徑的機率趨近於 1，而狹窄通道可能要花很長時間
  • RRT* 一定是比較好的選擇 — 它會隨時間改善路徑，但得到第一個解較慢；在重視速度時，通常會優先使用 RRT-Connect 加上平滑化

誰需要了解

  • 運動規劃工程師
  • 使用 MoveIt 或 OMPL 的操作與移動機器人開發人員
  • 自駕車與無人機規劃工程師
  • 機器人學學生

相關技術

  • OMPL
  • MoveIt
  • RRT-Connect
  • 運動動力學 RRT（Kinodynamic RRT）
  • Informed RRT*
  • 路徑捷徑化（Path Shortcutting）

相關術語

  • Configuration Space
  • Motion Planning
  • Obstacle Avoidance
  • RRT*
  • Probabilistic Roadmap
  • Motion Primitive

相關專案

  • Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
  • ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
  • OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
  • MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
  • PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
  • mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

影片

  • Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering

本網站需要 JavaScript 才能正常運作。請啟用 JavaScript 以瀏覽我們的開源機器人專案。