RRT*

• 又稱: RRT star, RRT-star, optimal RRT
• 類別: Planning & manipulation › Motion planning
• 標籤: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

快速探索隨機樹規劃器的一種漸近最佳版本，會在成長過程中重新連接樹，讓它傳回的路徑持續朝成本最低的路徑改進。

定義

RRT\（讀作「RRT star」）是一種以取樣為基礎的運動規劃演算法，能找出無碰撞路徑，並在樣本足夠多時收斂到最佳路徑。它由 Sertac Karaman 與 Emilio Frazzoli 於 2011 年提出，是 Steven LaValle 於 1998 年提出之快速探索隨機樹（Rapidly-exploring Random Tree，RRT）演算法的延伸。

原始的 RRT 從起點組態長出一棵樹：反覆在組態空間中隨機取樣一個點，找出樹中最近的節點，若朝該樣本的運動沒有碰撞，就往它延伸一小步。RRT 能很快找到可行路徑，即使在機器手臂關節空間這類高維空間中也一樣，但它的路徑通常曲折、遠非最短，而且不會隨著樣本增加而改善。

RRT* 改變了兩件事。加入新節點時，它會檢查鄰域半徑內的所有樹節點，並連接到從起點出發成本最低的那一個，而不只是最近的那一個。接著它會重新連線：對每個鄰居而言，若經過新節點能得到更便宜的路徑，就更換該鄰居的父節點。Karaman 與 Frazzoli 證明，只要鄰域半徑隨樹的成長適當縮小，當樣本數趨近無限時，解的成本就會收斂到最佳值，這項性質稱為漸近最佳性。

代價是每個樣本都需要額外的運算，因此 RRT 找到第一個解的速度比 RRT 慢。Informed RRT 與 BIT* 等變體會集中取樣以加快收斂。

為何重要

許多機器人需要的不只是任意一條路徑，而是一條好的路徑：更短、更平滑或更節能。RRT* 為能擴展到高維組態空間的取樣式規劃器提供了有理論根據的路徑品質提升途徑，也是運動規劃研究與軟體中的標準基準方法。

主要應用

• 雜亂工作空間中機器手臂的無碰撞運動規劃
• 移動機器人與無人機的全域路徑規劃
• 在網格搜尋不切實際的高維組態空間中進行規劃
• 為軌跡最佳化產生參考路徑

實際應用

機器人團隊通常透過規劃函式庫使用 RRT，而不是自己撰寫。MoveIt 用於機器手臂的開放運動規劃函式庫（Open Motion Planning Library，OMPL）包含 RRT 及其數種變體，以及 RRT、RRT-Connect 與 PRM。常見的做法是以固定的時間預算執行 RRT，在時間用完時取已找到的最佳路徑，接著做捷徑化與平滑處理，再轉換成帶時間參數的軌跡。對於移動機器人與無人機，團隊也會在 2D 或 3D 占據地圖上把 RRT 當作全域規劃器使用，並藉由選擇規劃時間與步長，在路徑品質與反應時間之間取捨。

常見誤解

• RRT* 會傳回最佳路徑 — 它是漸近最佳的，因此只有在樣本數無限增加時，路徑成本才會趨近最佳值
• RRT* 的路徑是平滑的 — 它們是分段線性的，執行前通常需要捷徑化與平滑處理
• RRT* 一定比 RRT 好 — 當只需要快速得到一條可行路徑時，單純的 RRT 或 RRT-Connect 往往是更好的選擇

誰需要了解

• 運動規劃工程師
• 機器手臂與操作軟體開發者
• 自主無人機與移動機器人開發者
• 學習規劃演算法的機器人學生

相關技術

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• 碰撞檢查（Collision Checking）

相關術語

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

相關專案

• 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

影片

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB