Differential dynamic programming

Definition

Let $F \colon \R^n \times \R^m \to \R^n$, $\ell \colon \R^n \times \R^m \to \R$ and $\ell_f \colon \R^n \to \R$ be twice continuously differentiable, and let $N \ge 1$. Consider the problem of minimising $\sum_{k=0}^{N-1} \ell(x_k, u_k) + \ell_f(x_N)$ over $u_0, \dots, u_{N-1} \in \R^m$, where $x_{k+1} = F(x_k, u_k)$ and $x_0$ is given. Subscripts denote partial derivatives, $\nabla^2$ a Hessian and $\nabla$ a gradient. One iteration of differential dynamic programming starts from controls $\bar u_k$ with states $\bar x_k$ and does the following.

1. Backward pass: set $V_x = \nabla \ell_f(\bar x_N)$ and $V_{xx} = \nabla^2 \ell_f(\bar x_N)$. For $k = N - 1, \dots, 0$, take all derivatives at $(\bar x_k, \bar u_k)$ and $V_x, V_{xx}$ from step $k + 1$. Compute $$Q_x = \ell_x + F_x^T V_x, \quad Q_u = \ell_u + F_u^T V_x,$$ $$Q_{xx} = \ell_{xx} + F_x^T V_{xx} F_x + V_x \cdot F_{xx}, \quad Q_{uu} = \ell_{uu} + F_u^T V_{xx} F_u + V_x \cdot F_{uu}, \quad Q_{ux} = \ell_{ux} + F_u^T V_{xx} F_x + V_x \cdot F_{ux},$$ where $V_x \cdot F_{xx}$ is the matrix $\sum_i (V_x)_i \nabla_x^2 F_i$ and similarly for the others. If $Q_{uu}$ is positive definite, set $d_k = -Q_{uu}^{-1} Q_u$, $K_k = -Q_{uu}^{-1} Q_{ux}$, and update $V_x \leftarrow Q_x - Q_{ux}^T Q_{uu}^{-1} Q_u$ and $V_{xx} \leftarrow Q_{xx} - Q_{ux}^T Q_{uu}^{-1} Q_{ux}$.
2. Forward pass: set $x_0^{\text{new}} = x_0$ and, for $k = 0, \dots, N - 1$, set $u_k^{\text{new}} = \bar u_k + d_k + K_k (x_k^{\text{new}} - \bar x_k)$ and $x_{k+1}^{\text{new}} = F(x_k^{\text{new}}, u_k^{\text{new}})$.

The new controls replace $\bar u_k$, and the iteration is repeated until the corrections $d_k$ are small.