論文導讀：RRT*——用重新佈線讓隨機樹收斂到最佳路徑

論文資訊卡

標題：Sampling-based Algorithms for Optimal Motion Planning
作者：Sertac Karaman、Emilio Frazzoli（MIT）
發表：The International Journal of Robotics Research (IJRR), 2011

問題背景

RRT 只保證機率完備性（probabilistic completeness）——只要有解，取樣次數趨於無限時幾乎必定能找到一條可行路徑，但完全不保證這條路徑的品質。Karaman 與 Frazzoli 在這篇論文裡先給出一個嚴謹的理論證明：包括原始 RRT 在內，多數當時廣泛使用的取樣式規劃演算法，即使取樣次數趨於無限，回傳解的路徑成本也會機率上收斂到一個非最佳的數值，而不是真正的最短路徑——換句話說，「多跑幾次取樣」本身並不會讓 RRT 的路徑品質趨近最佳解，這是一個結構性的限制，不是取樣次數不夠的問題。

方法核心：選擇父節點與重新佈線

RRT* 在 RRT 原本的「取樣、找最近節點、往取樣點方向延伸」流程上，額外加入兩個關鍵步驟：

選擇最佳父節點（Choose Parent）：當一個新節點要加入樹時，RRT 只會把它接到樹上距離最近的既有節點；RRT* 則會在新節點的鄰域範圍內，搜尋所有可能的候選父節點，選擇那個能讓新節點「從起點算起的累積路徑成本」最小的節點作為父節點，而不是單純選距離最近的。

重新佈線（Rewire）：新節點加入之後，RRT* 進一步檢查鄰域內的既有節點——如果某個既有節點透過新節點連接，能得到比它目前路徑更低的累積成本，就把該節點的父節點重新指定成新節點，讓樹的連接結構動態調整。這個步驟讓樹不是只能單向生長，還能持續把已經長出來的分支「修剪重接」到更好的路徑上。

這兩個步驟合起來，讓 RRT* 在每次新增節點時都持續朝更低成本的路徑結構逼近，論文證明了這套機制能讓 RRT* 具備漸進最佳性（asymptotic optimality）——取樣次數趨於無限時，回傳路徑的成本會幾乎必定收斂到真正的最佳解，這是原始 RRT 完全不具備的性質。論文同時提出了 PRM* 這個對應的機率路徑圖（Probabilistic Roadmap）版本，用同樣的鄰域重新連接思路達到漸進最佳性，兩者共享同一套理論分析框架。

影響與定位

RRT* 提出的「重新佈線」概念，直接催生了後續一整個系列的改良演算法——Informed RRT*（把取樣範圍限縮在已知能改善路徑的橢圓區域，加快收斂速度）、RRT#、BIT*（Batch Informed Trees）等，都是在 RRT* 的漸進最佳性基礎上，進一步優化收斂速度或計算效率。時至今日，RRT* 系列演算法仍然是機械手臂運動規劃、自駕車路徑規劃裡最常被實際部署的取樣式規劃方法之一，是連接「理論上保證找得到解」與「實務上要找到品質夠好的解」這兩個目標的關鍵橋樑。

常見誤解

RRT* 的漸進最佳性是一個極限性質——它保證的是取樣次數趨於無限時收斂到最佳解，不代表在有限、實務可接受的計算時間預算內，RRT* 找到的路徑就一定接近最佳。在即時性要求高、取樣預算有限的應用場景，RRT* 收斂到可接受路徑品質所需要的節點數量，仍然可能是實務上的效能瓶頸，這也是為什麼 Informed RRT* 這類加速收斂速度的變形持續有研究價值，而不是 RRT* 提出之後這個問題就徹底解決了。