Differential Dynamic Programming (DDP)

✅ 本章定位：理解 DDP 如何在 iLQR 的基础上引入二阶动力学近似，实现更快的收敛速度；掌握 DDP 与 iLQR 的精确差异和各自的适用场景。

一、DDP 的核心思想

从 iLQR 到 DDP

iLQR 在每轮迭代中将非线性动力学做一阶泰勒展开，然后解一个 LQR 子问题。DDP 的做法几乎完全一样，唯一的区别在于：

对动力学也做二阶泰勒展开。

这意味着 DDP 在构造局部近似时，不仅考虑了动力学的梯度方向（一阶），还考虑了动力学的曲率信息（二阶），因此每步近似更精确，收敛更快。

iLQR：  δx_{t+1} ≈ A·δx + B·δu                          （一阶动力学）
DDP：   δx_{t+1} ≈ A·δx + B·δu + ½·[δx,δu]ᵀ·C·[δx,δu]   （二阶动力学）

其中 C 是动力学的 Hessian 张量。

二、与 iLQR 的精确差异

构造 LQR 子问题的三个操作

操作iLQRDDP
线性化动力学一阶泰勒：A = ∂f/∂x，B = ∂f/∂u二阶泰勒：额外计算 C = ∂²f/∂(x,u)²
二次化代价二阶泰勒：Q、R二阶泰勒：Q、R（与 iLQR 相同）
求解 Riccati 方程标准形式需要额外修正项来吸收二阶动力学项

二阶动力学带来的代价

DDP 在逆向传递中需要处理二阶动力学项。将二阶展开代入 Riccati 方程后，会多出一项涉及动力学 Hessian 的修正：

$$V_x'(x) = V_x(f(x,u)) + V_{xx}(f(x,u)) \cdot f_x(x,u)$$

$$V_{xx}'(x) = f_x(x,u)^T V_{xx} f(x,u) + V_{xx}(f(x,u)) \cdot f_{xx}(x,u) + l_{xx}(x,u)$$

其中 f_{xx} 就是动力学的二阶导数——iLQR 完全忽略了这一项。

梯度需求对比

导数iLQR 是否需要DDP 是否需要计算成本
∂f/∂x（雅可比）✅✅中
∂f/∂u（雅可比）✅✅中
∂²f/∂x²（Hessian）❌✅高
∂²f/∂u²（Hessian）❌✅高
∂²f/∂x∂u（交叉 Hessian）❌✅高

三、收敛性差异

理论保证

性质iLQRDDP
收敛阶数线性收敛（一阶）二次收敛（二阶）
每轮计算量较低（只算雅可比）较高（需算 Hessian）
总迭代次数较多较少（通常 2-3 倍差距）

直觉：iLQR 每步走的方向大致正确但步长受限于线性近似的精度；DDP 因为有曲率信息，不仅能走更精确的方向，还能自适应调整步长。

实际选择

问题特征 → 推荐方法
─────────────────────
动力学平滑、二阶导容易算 → DDP（总时间更短）
动力学复杂、二阶导计算昂贵 → iLQR（每轮更快）
对精度要求极高 → DDP
需要鲁棒性（不依赖精确二阶导） → iLQR

四、算法流程

DDP 的算法流程与 iLQR 几乎完全一致，区别仅在于逆向传递：

算法：DDP 轨迹优化

输入/输出：同 iLQR

步骤：
1. 初始化：设定初始轨迹 (x̄, ū)
2. Repeat until convergence:

   (a) 前向传递
       - 用当前控制 ū 仿真得到状态轨迹 x̄
       - 计算当前总代价 J

   (b) 计算 Jacobian 和 Hessian
       - 一阶：Aₜ = ∂f/∂x,  Bₜ = ∂f/∂u        ← 与 iLQR 相同
       - 二阶：Cₜ = ∂²f/∂(x,u)²                 ← DDP 额外需要

   (c) 逆向传递（含二阶修正）
       - 初始化：Vₓ = lₓ,  Vₓₓ = lₓₓ
       - 对 t = T-1, ..., 0:
         · 计算 Qₓ, Qᵤ, Qₓₓ, Qᵤᵤ, Qₓᵤ（含动力学二阶修正项）
         · 计算 kₜ（feedforward）, Kₜ（feedback gain）
         · 更新 Value 函数导数 Vₓ, Vₓₓ（含 fₓₓ 修正项）  ← DDP 的关键区别

   (d) 线搜索 + 更新控制
       - u_new = ū + α·(k + K·δx)

   (e) 收敛检查

与 iLQR 逆向传递的唯一区别：Vₓₓ 的更新公式中多了 Vₓₓ · fₓₓ 这一项（动力学 Hessian 对 Value 函数 Hessian 的贡献）。

五、iLQR 与 DDP 的关系总结

LQR（线性系统，一次求解）
 │
 ├─ 加一层迭代 + 一阶线性化 → iLQR（非线性系统，线性收敛）
 │
 └─ 加一层迭代 + 二阶线性化 → DDP（非线性系统，二次收敛）

两者的关系可以概括为：

LQRiLQRDDP
系统类型线性非线性非线性
动力学近似阶数精确（本身就是线性）一阶二阶
代价近似阶数精确（本身就是二次）二阶二阶
是否需要迭代❌✅✅
每轮闭式解✅✅✅（修正后）
收敛速度N/A线性二次
核心瓶颈仅限线性系统一阶近似的精度二阶导的计算成本

六、工程实践

DDP 的常见问题

1. Hessian 计算成本

  • 对于解析可微的动力学（如刚体），可以用自动微分或符号推导
  • 对于黑箱仿真器，需要用有限差分近似，成本随状态维度平方增长

2. 数值稳定性

  • 二阶项可能使 Hessian 不定（非正定），导致下降方向不可靠
  • 常用 Levenberg-Marquardt 正则化：在 Hessian 对角线加 λI

3. iLQR 实际上更常用

  • 在角色动画领域，iLQR 的使用频率远高于 DDP
  • 原因：大多数物理仿真器的二阶导数难以获取，而 iLQR 的一阶近似在大多数场景下已经足够

七、深入学习

前置知识

相关方法

  • CMA-ES - 无梯度优化，适用于不可微问题
  • MPC - 在线优化框架

参考资料

  • Mayne, D. Q. (1966). A Second-Order Solution of the Optimal Control Problem. (DDP 的原始论文)
  • Tassa, Y., Mansard, N., & Todorov, E. (2012). Control-Limited Differential Dynamic Programming. (带控制约束的 DDP)

本文出自 CaterpillarStudyGroup，转载请注明出处。 https://caterpillarstudygroup.github.io/GAMES105_mdbook/