Differential dynamic programming

The dynamics

{{NumBlk|:|$\backslash mathbf\{x\}\_\{i+1\}\; =\; \backslash mathbf\{f\}(\backslash mathbf\{x\}\_i,\backslash mathbf\{u\}\_i)$|{{EquationRef|1}}}}

describe the evolution of the state $\backslash textstyle\backslash mathbf\{x\}$ given the control $\backslash mathbf\{u\}$ from time $i$ to time $i+1$. The total cost $J\_0$ is the sum of running costs $\backslash textstyle\backslash ell$ and final cost $\backslash ell\_f$, incurred when starting from state $\backslash mathbf\{x\}$ and applying the control sequence $\backslash mathbf\{U\}\; \backslash equiv\; \backslash \{\backslash mathbf\{u\}\_0,\backslash mathbf\{u\}\_1\backslash dots,\backslash mathbf\{u\}\_\{N-1\}\backslash \}$ until the horizon is reached:

:$J\_0(\backslash mathbf\{x\},\backslash mathbf\{U\})=\backslash sum\_\{i=0\}^\{N-1\}\backslash ell(\backslash mathbf\{x\}\_i,\backslash mathbf\{u\}\_i)\; +\; \backslash ell\_f(\backslash mathbf\{x\}\_N),$

where $\backslash mathbf\{x\}\_0\backslash equiv\backslash mathbf\{x\}$, and the $\backslash mathbf\{x\}\_i$ for $i>0$ are given by {{EquationNote|1|Eq. 1}}. The solution of the optimal control problem is the minimizing control sequence

$\backslash mathbf\{U\}^*(\backslash mathbf\{x\})\backslash equiv\; \backslash operatorname\{argmin\}\_\{\backslash mathbf\{U\}\}\; J\_0(\backslash mathbf\{x\},\backslash mathbf\{U\}).$

Trajectory optimization means finding $\backslash mathbf\{U\}^*(\backslash mathbf\{x\})$ for a particular $\backslash mathbf\{x\}\_0$, rather than for all possible initial states.

Let $\backslash mathbf\{U\}\_i$ be the partial control sequence $\backslash mathbf\{U\}\_i\; \backslash equiv\; \backslash \{\backslash mathbf\{u\}\_i,\backslash mathbf\{u\}\_\{i+1\}\backslash dots,\backslash mathbf\{u\}\_\{N-1\}\backslash \}$ and define the cost-to-go $J\_i$ as the partial sum of costs from $i$ to $N$:

:$J\_i(\backslash mathbf\{x\},\backslash mathbf\{U\}\_i)=\backslash sum\_\{j=i\}^\{N-1\}\backslash ell(\backslash mathbf\{x\}\_j,\backslash mathbf\{u\}\_j)\; +\; \backslash ell\_f(\backslash mathbf\{x\}\_N).$

The optimal cost-to-go or value function at time $i$ is the cost-to-go given the minimizing control sequence:

:$V(\backslash mathbf\{x\},i)\backslash equiv\; \backslash min\_\{\backslash mathbf\{U\}\_i\}J\_i(\backslash mathbf\{x\},\backslash mathbf\{U\}\_i).$

Setting $V(\backslash mathbf\{x\},N)\backslash equiv\; \backslash ell\_f(\backslash mathbf\{x\}\_N)$, the dynamic programming principle reduces the minimization over an entire sequence of controls to a sequence of minimizations over a single control, proceeding backwards in time:

{{NumBlk|:|$V(\backslash mathbf\{x\},i)=\; \backslash min\_\{\backslash mathbf\{u\}\}[\backslash ell(\backslash mathbf\{x\},\backslash mathbf\{u\})\; +\; V(\backslash mathbf\{f\}(\backslash mathbf\{x\},\backslash mathbf\{u\}),i+1)].$|{{EquationRef|2}}}}

This is the Bellman equation.

DDP proceeds by iteratively performing a backward pass on the nominal trajectory to generate a new control sequence, and then a forward-pass to compute and evaluate a new nominal trajectory. We begin with the backward pass. If

:$\backslash ell(\backslash mathbf\{x\},\backslash mathbf\{u\})\; +\; V(\backslash mathbf\{f\}(\backslash mathbf\{x\},\backslash mathbf\{u\}),i+1)$

is the argument of the $\backslash min[\backslash cdot]$ operator in {{EquationNote|2|Eq. 2}}, let $Q$ be the variation of this quantity around the $i$-th $(\backslash mathbf\{x\},\backslash mathbf\{u\})$ pair:

:

\\

-&\ell(\mathbf{x},\mathbf{u})&&{}-V(\mathbf{f}(\mathbf{x},\mathbf{u}),i+1)

\end{align}

and expand to second order

{{NumBlk|:|$$

\approx\frac{1}{2}

\begin{bmatrix}

1\\

\delta\mathbf{x}\\

\delta\mathbf{u}

\end{bmatrix}^\mathsf{T}

\begin{bmatrix}

0 & Q_\mathbf{x}^\mathsf{T} & Q_\mathbf{u}^\mathsf{T}\\

Q_\mathbf{x} & Q_{\mathbf{x}\mathbf{x}} & Q_{\mathbf{x}\mathbf{u}}\\

Q_\mathbf{u} & Q_{\mathbf{u}\mathbf{x}} & Q_{\mathbf{u}\mathbf{u}}

\end{bmatrix}

\begin{bmatrix}

1\\

\delta\mathbf{x}\\

\delta\mathbf{u}

\end{bmatrix}

|{{EquationRef|3}}}}

The $Q$ notation used here is a variant of the notation of Morimoto where subscripts denote differentiation in denominator layout.{{Cite conference

| volume = 2

| pages = 1927–1932

| last = Morimoto

| first = J. |author2=G. Zeglin |author3=C.G. Atkeson

| title = Minimax differential dynamic programming: Application to a biped walking robot

| book-title = Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on

| date = 2003

}}

Dropping the index $i$ for readability, primes denoting the next time-step $V\text{'}\backslash equiv\; V(i+1)$, the expansion coefficients are

:$$

\begin{alignat}{2}

Q_\mathbf{x} &= \ell_\mathbf{x}+ \mathbf{f}_\mathbf{x}^\mathsf{T} V'_\mathbf{x} \\

Q_\mathbf{u} &= \ell_\mathbf{u}+ \mathbf{f}_\mathbf{u}^\mathsf{T} V'_\mathbf{x} \\

Q_{\mathbf{x}\mathbf{x}} &= \ell_{\mathbf{x}\mathbf{x}} + \mathbf{f}_\mathbf{x}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{x}+V_\mathbf{x}'\cdot\mathbf{f}_{\mathbf{x}\mathbf{x}}\\

Q_{\mathbf{u}\mathbf{u}} &= \ell_{\mathbf{u}\mathbf{u}} + \mathbf{f}_\mathbf{u}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{u}+{V'_\mathbf{x}} \cdot\mathbf{f}_{\mathbf{u} \mathbf{u}}\\

Q_{\mathbf{u}\mathbf{x}} &= \ell_{\mathbf{u}\mathbf{x}} + \mathbf{f}_\mathbf{u}^\mathsf{T} V'_{\mathbf{x}\mathbf{x}}\mathbf{f}_\mathbf{x} + {V'_\mathbf{x}} \cdot \mathbf{f}_{\mathbf{u} \mathbf{x}}.

\end{alignat}

The last terms in the last three equations denote contraction of a vector with a tensor. Minimizing the quadratic approximation {{EquationNote|3|(3)}} with respect to $\backslash delta\backslash mathbf\{u\}$ we have

{{NumBlk|:|$$

{\delta \mathbf{u}}^* = \operatorname{argmin}\limits_{\delta \mathbf{u}}Q(\delta \mathbf{x},\delta

\mathbf{u})=-Q_{\mathbf{u}\mathbf{u}}^{-1}(Q_\mathbf{u}+Q_{\mathbf{u}\mathbf{x}}\delta \mathbf{x}),

|{{EquationRef|4}}}}

giving an open-loop term $\backslash mathbf\{k\}=-Q\_\{\backslash mathbf\{u\}\backslash mathbf\{u\}\}^\{-1\}Q\_\backslash mathbf\{u\}$ and a feedback gain term $\backslash mathbf\{K\}=-Q\_\{\backslash mathbf\{u\}\backslash mathbf\{u\}\}^\{-1\}Q\_\{\backslash mathbf\{u\}\backslash mathbf\{x\}\}$. Plugging the result back into {{EquationNote|3|(3)}}, we now have a quadratic model of the value at time $i$:

:$$

\begin{alignat}{2}

\Delta V(i) &= &{} -\tfrac{1}{2}Q^T_\mathbf{u} Q_{\mathbf{u}\mathbf{u}}^{-1}Q_\mathbf{u}\\

V_\mathbf{x}(i) &= Q_\mathbf{x} & {}- Q_\mathbf{xu} Q_{\mathbf{u}\mathbf{u}}^{-1}Q_{\mathbf{u}}\\

V_{\mathbf{x}\mathbf{x}}(i) &= Q_{\mathbf{x}\mathbf{x}} &{} - Q_{\mathbf{x}\mathbf{u}}Q_{\mathbf{u}\mathbf{u}}^{-1}Q_{\mathbf{u}\mathbf{x}}.

\end{alignat}

Recursively computing the local quadratic models of $V(i)$ and the control modifications $\backslash \{\backslash mathbf\{k\}(i),\backslash mathbf\{K\}(i)\backslash \}$, from $i=N-1$ down to $i=1$, constitutes the backward pass. As above, the Value is initialized with $V(\backslash mathbf\{x\},N)\backslash equiv\; \backslash ell\_f(\backslash mathbf\{x\}\_N)$. Once the backward pass is completed, a forward pass computes a new trajectory:

:$$

\begin{align}

\hat{\mathbf{x}}(1)&=\mathbf{x}(1)\\

\hat{\mathbf{u}}(i)&=\mathbf{u}(i) + \mathbf{k}(i) +\mathbf{K}(i)(\hat{\mathbf{x}}(i) - \mathbf{x}(i))\\

\hat{\mathbf{x}}(i+1)&=\mathbf{f}(\hat{\mathbf{x}}(i),\hat{\mathbf{u}}(i))

\end{align}

The backward passes and forward passes are iterated until convergence.

If the Hessians $Q\_\{\backslash mathbf\{x\}\backslash mathbf\{x\}\},\; Q\_\{\backslash mathbf\{u\}\backslash mathbf\{u\}\},\; Q\_\{\backslash mathbf\{u\}\backslash mathbf\{x\}\},\; Q\_\{\backslash mathbf\{x\}\backslash mathbf\{u\}\}$ are replaced by their Gauss-Newton approximation, the method reduces to the iterative Linear Quadratic Regulator (iLQR).{{Cite conference

| pages = 1-7

| last = Baumgärtner

| first = K.

| title = A Unified Local Convergence Analysis of Differential Dynamic Programming, Direct Single Shooting, and Direct Multiple Shooting

| conference = 2023 European Control Conference (ECC)

| year = 2023

| doi = 10.23919/ECC57647.2023.10178367

| url = https://ieeexplore.ieee.org/abstract/document/10178367

| url-access = subscription

}}

Differential dynamic programming is a second-order algorithm like Newton's method. It therefore takes large steps toward the minimum and often requires regularization and/or line-search to achieve convergence.

{{Cite journal |last=Liao |first=L. Z |author2=C. A Shoemaker |author2-link=Christine Shoemaker |year=1991 |title=Convergence in unconstrained discrete-time differential dynamic programming |journal=IEEE Transactions on Automatic Control |volume=36 |issue=6 |page=692 |doi=10.1109/9.86943}}

{{Cite thesis

| publisher = Hebrew University

| last = Tassa

| first = Y.

| title = Theory and implementation of bio-mimetic motor controllers

| date = 2011

| url = http://icnc.huji.ac.il/phd/theses/files/YuvalTassa.pdf

| access-date = 2012-02-27

| archive-url = https://web.archive.org/web/20160304023026/http://icnc.huji.ac.il/phd/theses/files/YuvalTassa.pdf

| archive-date = 2016-03-04

}} Regularization in the DDP context means ensuring that the $Q\_\{\backslash mathbf\{u\}\backslash mathbf\{u\}\}$ matrix in {{EquationNote|4|Eq. 4}} is positive definite. Line-search in DDP amounts to scaling the open-loop control modification $\backslash mathbf\{k\}$ by some .

Sampled differential dynamic programming (SaDDP) is a Monte Carlo variant of differential dynamic programming.{{Cite conference |title=Sampled differential dynamic programming |book-title=2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) |language=en-US|doi=10.1109/IROS.2016.7759229|s2cid=1338737}}{{Cite conference|last1=Rajamäki|first1=Joose|first2=Perttu|last2=Hämäläinen|url=https://ieeexplore.ieee.org/document/8430799|title=Regularizing Sampled Differential Dynamic Programming - IEEE Conference Publication|conference=2018 Annual American Control Conference (ACC)|date=June 2018 |pages=2182–2189 |doi=10.23919/ACC.2018.8430799 |s2cid=243932441 |language=en-US|access-date=2018-10-19|url-access=subscription}}{{Cite book|first=Joose|last=Rajamäki|date=2018|title=Random Search Algorithms for Optimal Control|url=http://urn.fi/URN:ISBN:978-952-60-8156-4|language=en|issn=1799-4942|isbn=978-952-60-8156-4|publisher=Aalto University}} It is based on treating the quadratic cost of differential dynamic programming as the energy of a Boltzmann distribution. This way the quantities of DDP can be matched to the statistics of a multidimensional normal distribution. The statistics can be recomputed from sampled trajectories without differentiation.

Sampled differential dynamic programming has been extended to Path Integral Policy Improvement with Differential Dynamic Programming.{{Cite book|last1=Lefebvre|first1=Tom|last2=Crevecoeur|first2=Guillaume|title=2019 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM) |chapter=Path Integral Policy Improvement with Differential Dynamic Programming |date=July 2019|chapter-url=https://ieeexplore.ieee.org/document/8868359|pages=739–745|doi=10.1109/AIM.2019.8868359|hdl=1854/LU-8623968|isbn=978-1-7281-2493-3|s2cid=204816072|url=https://biblio.ugent.be/publication/8623968 |hdl-access=free}} This creates a link between differential dynamic programming and path integral control,{{Cite book|last1=Theodorou|first1=Evangelos|last2=Buchli|first2=Jonas|last3=Schaal|first3=Stefan|title=2010 IEEE International Conference on Robotics and Automation |chapter=Reinforcement learning of motor skills in high dimensions: A path integral approach |date=May 2010|chapter-url=https://ieeexplore.ieee.org/document/5509336|pages=2397–2403|doi=10.1109/ROBOT.2010.5509336|isbn=978-1-4244-5038-1|s2cid=15116370}} which is a framework of stochastic optimal control.

Interior Point Differential dynamic programming (IPDDP) is an interior-point method generalization of DDP that can address the optimal control problem with nonlinear state and input constraints.{{cite arXiv |last1=Pavlov |first1=Andrei|last2=Shames|first2=Iman| last3=Manzie|first3=Chris|date=2020 |title=Interior Point Differential Dynamic Programming |eprint=2004.12710 |class=math.OC}}

• Optimal control

{{Reflist}}

• [http://www.ros.org/wiki/color_DDP A Python implementation of DDP]
• [http://www.mathworks.com/matlabcentral/fileexchange/52069-ilqg-ddp-trajectory-optimization A MATLAB implementation of DDP]

• The open-source software framework [https://github.com/acados/acados acados] provides an efficient and embeddable implementation of DDP.

Category:Dynamic programming