Differential dynamic programming

From Wikipedia, the free encyclopedia

Differential dynamic programming (DDP) is an optimal control algorithm of the trajectory optimization class. The algorithm was introduced in 1966 by Mayne ^[1] and subsequently analysed in Jacobson and Mayne's eponymous book.^[2] The algorithm uses locally-quadratic models of the dynamics and cost functions, and displays quadratic convergence. It is closely related to Pantoja's step-wise Newton's method.^{[3] [4]}

The dynamics

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

${\displaystyle J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),}${\displaystyle J_{0}(\mathbf {x} ,\mathbf {U} )=\sum _{i=0}^{N-1}\ell (\mathbf {x} _{i},\mathbf {u} _{i})+\ell _{f}(\mathbf {x} _{N}),}

where ${\displaystyle \mathbf {x} _{0}\equiv \mathbf {x} }${\displaystyle \mathbf {x} _{0}\equiv \mathbf {x} }, and the ${\displaystyle \mathbf {x} _{i}}${\displaystyle \mathbf {x} _{i}} for ${\displaystyle i>0}${\displaystyle i>0} are given by Eq. 1 . The solution of the optimal control problem is the minimizing control sequence ${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).}${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )\equiv \operatorname {argmin} _{\mathbf {U} }J_{0}(\mathbf {x} ,\mathbf {U} ).} Trajectory optimization means finding ${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )}${\displaystyle \mathbf {U} ^{*}(\mathbf {x} )} for a particular ${\displaystyle \mathbf {x} _{0}}${\displaystyle \mathbf {x} _{0}}, rather than for all possible initial states.

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

${\displaystyle J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).}${\displaystyle J_{i}(\mathbf {x} ,\mathbf {U} _{i})=\sum _{j=i}^{N-1}\ell (\mathbf {x} _{j},\mathbf {u} _{j})+\ell _{f}(\mathbf {x} _{N}).}

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

${\displaystyle V(\mathbf {x} ,i)\equiv \min _{\mathbf {U} _{i}}J_{i}(\mathbf {x} ,\mathbf {U} _{i}).}${\displaystyle V(\mathbf {x} ,i)\equiv \min _{\mathbf {U} _{i}}J_{i}(\mathbf {x} ,\mathbf {U} _{i}).}

Setting ${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\mathbf {x} _{N})}${\displaystyle V(\mathbf {x} ,N)\equiv \ell _{f}(\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:

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

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

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

${\displaystyle {\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}}${\displaystyle {\begin{aligned}Q(\delta \mathbf {x} ,\delta \mathbf {u} )\equiv &\ell (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} )&&{}+V(\mathbf {f} (\mathbf {x} +\delta \mathbf {x} ,\mathbf {u} +\delta \mathbf {u} ),i+1)\\-&\ell (\mathbf {x} ,\mathbf {u} )&&{}-V(\mathbf {f} (\mathbf {x} ,\mathbf {u} ),i+1)\end{aligned}}}

and expand to second order

The ${\displaystyle Q}${\displaystyle Q} notation used here is a variant of the notation of Morimoto where subscripts denote differentiation in denominator layout.^[5] Dropping the index ${\displaystyle i}${\displaystyle i} for readability, primes denoting the next time-step ${\displaystyle V'\equiv V(i+1)}${\displaystyle V'\equiv V(i+1)}, the expansion coefficients are

${\displaystyle {\begin{alignedat}{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{alignedat}}}${\displaystyle {\begin{alignedat}{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{alignedat}}}

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

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

${\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }^{T}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{alignedat}}}${\displaystyle {\begin{alignedat}{2}\Delta V(i)&=&{}-{\tfrac {1}{2}}Q_{\mathbf {u} }^{T}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{alignedat}}}

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

${\displaystyle {\begin{aligned}{\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{aligned}}}${\displaystyle {\begin{aligned}{\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{aligned}}}

The backward passes and forward passes are iterated until convergence. If the Hessians ${\displaystyle Q_{\mathbf {x} \mathbf {x} },Q_{\mathbf {u} \mathbf {u} },Q_{\mathbf {u} \mathbf {x} },Q_{\mathbf {x} \mathbf {u} }}${\displaystyle Q_{\mathbf {x} \mathbf {x} },Q_{\mathbf {u} \mathbf {u} },Q_{\mathbf {u} \mathbf {x} },Q_{\mathbf {x} \mathbf {u} }} are replaced by their Gauss-Newton approximation, the method reduces to the iterative Linear Quadratic Regulator (iLQR).^[6]

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.^{[7] [8]} Regularization in the DDP context means ensuring that the ${\displaystyle Q_{\mathbf {u} \mathbf {u} }}${\displaystyle Q_{\mathbf {u} \mathbf {u} }} matrix in Eq. 4 is positive definite. Line-search in DDP amounts to scaling the open-loop control modification ${\displaystyle \mathbf {k} }${\displaystyle \mathbf {k} } by some ${\displaystyle 0<\alpha <1}${\displaystyle 0<\alpha <1}.

Sampled differential dynamic programming (SaDDP) is a Monte Carlo variant of differential dynamic programming.^{[9] [10] [11]} 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.^[12] This creates a link between differential dynamic programming and path integral control,^[13] 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.^[14]

• Optimal control

• A Python implementation of DDP
• A MATLAB implementation of DDP

• The open-source software framework acados provides an efficient and embeddable implementation of DDP.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Differential_dynamic_programming&oldid=1307759774"

Category:

• Dynamic programming

Hidden categories:

• Articles with short description
• Short description is different from Wikidata