Differential dynamic programming
- 又稱: DDP
- 類別: Planning & manipulation › Trajectory optimisation
- 標籤: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods
一種軌跡最佳化方法，沿著目前軌跡使用剩餘成本（cost-to-go）的局部二次模型，透過反覆的反向與前向階段改進控制序列。
定義
微分動態規劃（Differential dynamic programming，DDP）是一種軌跡最佳化演算法：給定動力學模型、關於狀態與控制量的成本以及初始狀態，它會找出一個使總成本局部最小的控制序列。它由 David Mayne 於 1966 年提出，並在 Jacobson 與 Mayne 1970 年出版的同名著作中進一步發展。DDP 是一種射擊法：決策變數是控制量，在其經典形式中，狀態一律透過向前模擬動力學取得，因此每一次迭代的結果都是一條在動力學上可行的軌跡。
每次迭代包含兩個階段。反向階段從最後一個時間步開始往起點推進，在局部套用 Bellman 最佳性原理：它利用動力學與成本的一階和二階導數，在目前軌跡附近建立剩餘成本（cost-to-go）的二次近似，並在每一步求解一個仿射控制更新，該更新由前饋項 k 與回饋增益矩陣 K 組成。接著前向階段以更新後的控制量 u = ū + αk + K(x − x̄) 模擬系統，其中 α 是線搜尋步長。由於展開式包含動力學的二階項，DDP 在局部極小值附近會像牛頓法一樣二次收斂，而每次迭代的運算量只隨時域長度線性增加。
動力學的二階導數計算成本很高，因此最廣為使用的變體，也就是迭代線性二次調節器（iLQR），捨棄了這些導數，只保留動力學的一階模型，即 Gauss-Newton 近似。實用的求解器會對反向階段做正則化，使其維持良好條件，並將此方法延伸到控制量限制（控制受限 DDP）、一般約束（擴增拉格朗日法，例如 ALTRO）、不可行的初始猜測（Crocoddyl 中的可行性驅動 DDP），以及像 Parameterized DDP 那樣與控制量一起最佳化的非時變參數。DDP 只能找到局部最佳解，因此結果取決於初始猜測。一個有用的附帶產物是這組回饋增益，它們能讓機器人穩定在最佳化後的軌跡附近。
為何重要
DDP 與 iLQR 是機器人軌跡最佳化與非線性模型預測控制中最常用的求解器之一。它們利用問題的時間結構，運算量隨時域長度線性增加，並且在給出軌跡的同時回傳一個局部回饋策略，這正是足式機器人、人形機器人與無人機在機上即時執行它們的原因。
主要應用
- 足式機器人與人形機器人的非線性模型預測控制
- 無人機與敏捷載具的軌跡最佳化
- 機器手臂的力矩層級運動規劃
- 欠驅動系統的甩起與平衡
- 軌跡與模型參數或設計參數的聯合最佳化
實際應用
一個為四足機器人建構全身模型預測控制的團隊在 Crocoddyl 中建立問題。接觸序列來自固定的步態排程，因此每個階段的接觸都是已知的；成本結合了基座追蹤、落腳位置、控制量消耗，以及讓接觸力維持在摩擦錐內的懲罰項。在每個控制週期，求解器以前一次的解往後平移一步作為暖啟動，只執行一次或少數幾次迭代。第一個控制量及其回饋增益會送到底層的關節控制器，由它利用該增益修正兩次求解器更新之間的狀態變化。大部分調校工作集中在成本權重、正則化與時域長度上，它們在預見能力與求解時間之間取捨。
常見誤解
- DDP 能找到全域最佳軌跡 — 它是局部方法；結果取決於初始猜測，而且可能是很差的局部極小值
- iLQR 與 DDP 是同一個演算法 — iLQR 省略了動力學的二階項，讓每次迭代便宜許多，代價是在解附近收斂較慢
- DDP 無法處理約束 — 基本演算法沒有約束，但控制受限與擴增拉格朗日的變體已廣泛使用
- DDP 是在整個狀態空間上進行的動態規劃 — 它只沿著一條軌跡套用 Bellman 遞迴，這避開了維度詛咒，但只能給出局部結果
誰需要了解
- 為足式機器人與無人機建構模型預測控制器的控制工程師
- 軌跡最佳化研究人員
- 人形機器人與全身控制開發人員
- 學習最佳控制的機器人學學生
相關技術
- iLQR
- Crocoddyl
- ALTRO
- Riccati 遞迴（Riccati Recursion）
- 射擊法（Shooting Methods）
相關術語
- Direct Collocation
- Model Predictive Control
- Trajectory Planning
- Moving horizon estimation
- Underactuated system
- Hybrid system
相關專案
- PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
- MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
- python_simple_mppi: MPPI control derived and implemented in numpy, with four worked examples
- mjbatch: Runs thousands of MuJoCo simulations in parallel on the CPU
- Quadruped-PyMPC: Python MPC framework for quadruped locomotion with gradient and sampling control
- STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness