快速隨機搜尋樹 (RRT)

快速隨機搜尋樹（Rapidly-exploring Random Tree，RRT） 係一種基於隨機採樣嘅路徑規劃演算法，喺空間中不斷隨機撒點並向外擴展一棵「樹」，嚟搜尋一條由起點到終點嘅可行路徑。

佢同我哋熟識嘅 A演算法係兩種唔同嘅思路。A需要將空間預先劃分成網格，好似喺一張精確嘅地圖搵路；而 RRT 更加好似一個探險家，喺未知或者複雜嘅地形度「邊行邊探」，特別擅長處理高維度、帶有關運動學約束嘅複雜環境。

💡 工作流程：一棵樹點樣「生長」出嚟

你可以將 RRT 想像喺空間度種一棵樹，呢棵樹會自己搵出路：

播種：將起點設定為樹嘅「根」。
隨機撒點：喺規劃空間中隨機生成一個採樣點。呢個點可能係任何位置，甚至可能落喺障礙物入面。
搵到最近嘅「枝幹」：喺現有嘅樹上面，搵到一個距離呢個隨機點最近嘅節點。
向目標「生長」：從呢個最近節點出發，朝著隨機點嘅方向，生長出固定長度嘅一小段「枝幹」，生成一個新嘅節點。需要留意嘅係，如果隨機點直接落喺障礙物上，呢個點會被放棄；如果超出步長限制，就會喺該方向上截取一段步長內嘅新點。
安全檢測：檢查新長出嘅呢段「枝幹」有冇碰到障礙物。如果沒有，就將呢個新節點加到樹上面。
不斷重複：循環進行步驟 2-5，直到新長出嘅「枝幹」抵達終點附近，咁就由終點沿緊「枝幹」一路回溯到起點，就搵到一條可行路徑。

呢個過程嘅精髓在於，佢透過隨機探索嘅方式，能夠好快咁覆蓋整個空間，特別喺障礙物複雜嘅場景中，比傳統網格演算法效率更高。

🚧 挑戰同改進：RRT 並唔完美

雖然 RRT 喺處理複雜問題上有一套，但佢都存在明顯嘅「短板」：

路徑唔「絲滑」：由於係隨機生長，RRT 搵到嘅路徑通常由許多折線組成，唔夠平滑，車輛實際行駛好難直接跟隨。
唔係最短路徑：佢傾向「搵到一條路」，而唔係「搵到最短嘅路」。演算法本身唔保證路徑係全局最優嘅。
規劃效率唔高：喺複雜環境中，好容易產生大量無效嘅搜索分支，導致計算量大，收斂速度慢。

因此，喺自動駕駛嘅實際應用中，工程師通常會對基礎 RRT 演算法做大咗改進。例如，引入目標偏置策略引導樹向目標點生長，採用雙向 RRT（從起點同終點同時生長兩棵樹）嚟加速搜索，或者同 A* 等演算法融合，以及透過路徑剪枝同平滑處理嚟優化最終路徑質量。一個較新嘅研究案例表明，經過優化嘅 RRT 演算法，喺計算耗時同規劃時間上可分別降低64% 至 78%。