快速擴展隨機樹（RRT/RRT*）

快速擴展隨機樹，幾乎總是被叫做 RRT，是一種透過從機器人的起始姿態向外生長出一棵分叉的樹、直到某根枝條觸及目標來尋找路徑的方法。它靠不斷重複的小步驟運作：在機器人所有可能姿態構成的空間裡隨機選一個目標點，找到樹上離這個目標最近的那個點，再從那個點朝目標方向邁出一小步——只有當這一步的動作不發生碰撞時，才長出一根新的小枝。由於隨機目標會落在空間各處，這棵樹會被牽引著，最快地朝它尚未探索過的開闊區域生長，迅速地鋪展開來填滿自由空間——這正是它名字的由來。

RRT 是為「在一個可能未知或雜亂的空間裡做一次性查詢」而設計的：你只從一個起點生長出一棵樹，直到它碰到目標，然後沿枝條回溯，就讀出了路徑。這讓它天然適合那些必須當場規劃出一段新動作的移動機器人和機械臂。最樸素的版本速度快、擅長找到「某一條」可行路徑，但它並不保證這條路徑是短的——它返回的路線往往曲折迂迴，是「一條能走通的路」，而不是「一條好路」。

RRT*（讀作「RRT 星」）就是修正這一點的升級版。每當它新增一個點，它還會查看樹裡附近已有的那些點，只要經由這個新點去到它們會更省代價，就重新連接它們的連線。在許多次迭代裡，這種悄悄進行的重連會不斷把樹上的路徑拉直、縮短，因此 RRT* 是「漸近最優」的：它運行得越久，找到的路徑就越逼近真正的最短路徑。你用額外的計算換來穩步變好的路徑——只需要快速拿到「任何一條」安全路徑時就用樸素的 RRT，當你有餘裕讓它打磨路線時就用 RRT*。