RRT 論文導讀：路徑規劃的經典演算法

Steven M. LaValle · 1998原文連結

論文資訊卡

問題背景

在高維、含障礙物的組態空間（configuration space）中規劃一條可行路徑，傳統的網格搜尋演算法（如 A*）會隨維度增加而迅速失去效率。

方法核心

RRT 從起點開始，透過隨機取樣組態空間中的點，並朝取樣點方向從樹上最近的節點延伸一小步，逐漸長出一棵覆蓋整個可行空間的樹。這種「隨機探索 + 局部延伸」的策略讓 RRT 能快速涵蓋高維空間，而不需要對整個空間做網格化。

實驗結果摘要

LaValle 在論文中展示 RRT 在多種高自由度的組態空間規劃問題中，相較傳統方法有更好的擴展性，尤其適合非完整（nonholonomic）系統的路徑規劃。

影響與局限

RRT 後續衍生出 RRT*（具漸進最優性）、Informed RRT* 等變形，是現今機械手臂與自駕車路徑規劃的基礎工具之一。其局限在於原始版本不保證找到最短路徑，僅保證機率完備性（probabilistic completeness）。

相關論文推薦

  • RRT*：Karaman & Frazzoli, 2011