Motion Planning

這個章節將會介紹 Motion Planning，包括 Path Planning、Curve Interpolation 和 Trajectory Planning 三部份：Path Planning 是將地圖轉換成以交叉點為節點或離散網格為節點的動作，以便在地圖上的行走；Curve Interpolation 是用一個 curve function 來連接 weight points 以達到路徑的平滑與光滑，同時也可以改變路徑的參數，如起點、終點、坡度等；Trajectory Planning 是考慮時間資訊，根據預測 obstacle 的未來行動來規劃每個時間點的動作，以及尋找最佳路徑，使得機器人可以安全且有效地完成任務。

📄️ 1 - Introduction

Motion planning 是一種解決移動問題的技術，它志在找出一連串動作序列，讓車子移動到終點，要求動作序列需要避免撞到障礙物、動作限制（如最大速度等）、移動路徑需要平滑以及最短路徑。Motion planning 可以分成三部分：Path Planning、Curve Interpolation 和 Trajectory Planning。

📄️ 2 - Path Planning

本文介紹 Path Planning，它是為了讓機器人知道如何從一個起點到達另一個終點的策略。它讓我們可以用 Graph G 來表示地圖，其中 G = (V, E)，V 是一組點，E 是一組邊。而另外也會有 weights 來求解 single-source shortest path，即給定起點的最短路徑。

📄️ 3 - Curve Interpolation I

Curve Interpolation 將會用一個曲線函數連接節點，使得路徑變得平滑。 這個章節會介紹幾種曲線函數，例如 Explicit、Implicit 和 Parametric，並針對 Parametric Cubic Polynomial Curves 和 Cubic Interpolating Curves 進行了深入解釋。

📄️ 4 - Curve Interpolation II

本文探討了三種不同的曲線插值技術，分別是 Hermite Curves、Bezier Curves 和 Cubic B-spline Curves，它們都可以使用控制點來產生出曲線，但本文突出了 Cubic B-spline Curves 的優點，它可以讓兩個區段在接點處，一階微分的值是相同的，甚至可以滿足接點處的二階微分也相同，為了更加平滑的曲線。

📄️ 5 - Trajectory Planning

本文將描述如何使用 State lattice planning 和 Frenet Coordinate 來計算自駕車的軌跡。State lattice planning 透過結合空間和時間，採樣軌跡並計算成本，再檢查軌跡是否可用，並選擇成本最低的軌跡。Frenet Coordinate 將車子位置投影到二維路徑，求取一階、二階微分和最低成本。最後，Trajectory Planning 考慮動態障礙物，計算每個時間點的運動資訊，找出最低成本的軌跡。