Differential dynamic programming

Differential dynamic programming (DDP) is an optimal control algorithm of the trajectory optimization class.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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]

Contents

Finite-horizon discrete-time problems

edit edit source

The dynamics

𝐱i+1=𝐟(𝐱i,𝐮i) 1

describe the evolution of the state 𝐱 given the control 𝐮 from time i to time i+1. The total cost J0 is the sum of running costs ℓ and final cost ℓf, incurred when starting from state 𝐱 and applying the control sequence 𝐔≡{𝐮0,𝐮1…,𝐮N−1} until the horizon is reached:

J0(𝐱,𝐔)=∑i=0N−1ℓ(𝐱i,𝐮i)+ℓf(𝐱N),

where 𝐱0≡𝐱, and the 𝐱i for i>0 are given by Eq. 1. The solution of the optimal control problem is the minimizing control sequence 𝐔∗(𝐱)≡argmin𝐔J0(𝐱,𝐔). Trajectory optimization means finding 𝐔∗(𝐱) for a particular 𝐱0, rather than for all possible initial states.

Dynamic programming

edit edit source

Let 𝐔i be the partial control sequence 𝐔i≡{𝐮i,𝐮i+1…,𝐮N−1} and define the cost-to-go Ji as the partial sum of costs from i to N:

Ji(𝐱,𝐔i)=∑j=iN−1ℓ(𝐱j,𝐮j)+ℓf(𝐱N).

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

V(𝐱,i)≡min𝐔iJi(𝐱,𝐔i).

Setting V(𝐱,N)≡ℓf(𝐱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:

V(𝐱,i)=min𝐮[ℓ(𝐱,𝐮)+V(𝐟(𝐱,𝐮),i+1)]. 2

This is the Bellman equation.

Differential dynamic programming

edit edit source

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

ℓ(𝐱,𝐮)+V(𝐟(𝐱,𝐮),i+1)

is the argument of the min⁡[⋅] operator in Eq. 2, let Q be the variation of this quantity around the i-th (𝐱,𝐮) pair:

Q(δ𝐱,δ𝐮)≡ℓ(𝐱+δ𝐱,𝐮+δ𝐮)+V(𝐟(𝐱+δ𝐱,𝐮+δ𝐮),i+1)−ℓ(𝐱,𝐮)−V(𝐟(𝐱,𝐮),i+1)

and expand to second order

≈12[1δ𝐱δ𝐮]𝖳[0Q𝐱𝖳Q𝐮𝖳Q𝐱Q𝐱𝐱Q𝐱𝐮Q𝐮Q𝐮𝐱Q𝐮𝐮][1δ𝐱δ𝐮] 3

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

Q𝐱=ℓ𝐱+𝐟𝐱𝖳V'𝐱Q𝐮=ℓ𝐮+𝐟𝐮𝖳V'𝐱Q𝐱𝐱=ℓ𝐱𝐱+𝐟𝐱𝖳V'𝐱𝐱𝐟𝐱+V𝐱′⋅𝐟𝐱𝐱Q𝐮𝐮=ℓ𝐮𝐮+𝐟𝐮𝖳V'𝐱𝐱𝐟𝐮+V'𝐱⋅𝐟𝐮𝐮Q𝐮𝐱=ℓ𝐮𝐱+𝐟𝐮𝖳V'𝐱𝐱𝐟𝐱+V'𝐱⋅𝐟𝐮𝐱.

The last terms in the last three equations denote contraction of a vector with a tensor. Minimizing the quadratic approximation (3) with respect to δ𝐮 we have

δ𝐮∗=argminδ𝐮Q(δ𝐱,δ𝐮)=−Q𝐮𝐮−1(Q𝐮+Q𝐮𝐱δ𝐱), 4

giving an open-loop term 𝐤=−Q𝐮𝐮−1Q𝐮 and a feedback gain term 𝐊=−Q𝐮𝐮−1Q𝐮𝐱. Plugging the result back into (3), we now have a quadratic model of the value at time i:

ΔV(i)=−12Q𝐮TQ𝐮𝐮−1Q𝐮V𝐱(i)=Q𝐱−Q𝐱𝐮Q𝐮𝐮−1Q𝐮V𝐱𝐱(i)=Q𝐱𝐱−Q𝐱𝐮Q𝐮𝐮−1Q𝐮𝐱.

Recursively computing the local quadratic models of V(i) and the control modifications {𝐤(i),𝐊(i)}, from i=N−1 down to i=1, constitutes the backward pass. As above, the Value is initialized with V(𝐱,N)≡ℓf(𝐱N). Once the backward pass is completed, a forward pass computes a new trajectory:

𝐱̂(1)=𝐱(1)𝐮̂(i)=𝐮(i)+𝐤(i)+𝐊(i)(𝐱̂(i)−𝐱(i))𝐱̂(i+1)=𝐟(𝐱̂(i),𝐮̂(i))

The backward passes and forward passes are iterated until convergence. If the Hessians Q𝐱𝐱,Q𝐮𝐮,Q𝐮𝐱,Q𝐱𝐮 are replaced by their Gauss-Newton approximation, the method reduces to the iterative Linear Quadratic Regulator (iLQR).[6]

edit edit source

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 Q𝐮𝐮 matrix in Eq. 4 is positive definite. Line-search in DDP amounts to scaling the open-loop control modification 𝐤 by some 0<α<1.

Monte Carlo version

edit edit source

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.

Constrained problems

edit edit source

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]

See also

edit edit source

References

edit edit source
  1. ^ Mayne, D. Q. (1966). "A second-order gradient method of optimizing non-linear discrete time systems". Int J Control. 3: 85–95. doi:10.1080/00207176608921369. Wikipedia revision 1307759774, retrieved 2026-11-19
  2. ^ Mayne, David Q.; Jacobson, David H. (1970). Differential dynamic programming. New York: American Elsevier Pub. Co. ISBN 978-0-444-00070-5. Wikipedia revision 1307759774, retrieved 2026-11-19
  3. ^ de O. Pantoja, J. F. A. (1988). "Differential dynamic programming and Newton's method". International Journal of Control. 47 (5): 1539–1553. doi:10.1080/00207178808906114. ISSN 0020-7179. Wikipedia revision 1307759774, retrieved 2026-11-19
  4. ^ Liao, L. Z.; C. A Shoemaker (1992). "Advantages of differential dynamic programming over Newton's method for discrete-time optimal control problems". Cornell University. hdl:1813/5474. Wikipedia revision 1307759774, retrieved 2026-11-19
  5. ^ Morimoto, J.; G. Zeglin; C.G. Atkeson (2003). "Minimax differential dynamic programming: Application to a biped walking robot". Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on. Vol. 2. pp. 1927–1932. Wikipedia revision 1307759774, retrieved 2026-11-19
  6. ^ Baumgärtner, K. (2023). A Unified Local Convergence Analysis of Differential Dynamic Programming, Direct Single Shooting, and Direct Multiple Shooting. 2023 European Control Conference (ECC). pp. 1–7. doi:10.23919/ECC57647.2023.10178367. Wikipedia revision 1307759774, retrieved 2026-11-19
  7. ^ Liao, L. Z; C. A Shoemaker (1991). "Convergence in unconstrained discrete-time differential dynamic programming". IEEE Transactions on Automatic Control. 36 (6): 692. doi:10.1109/9.86943. Wikipedia revision 1307759774, retrieved 2026-11-19
  8. ^ Tassa, Y. (2011). Theory and implementation of bio-mimetic motor controllers (PDF) (Thesis). Hebrew University. Archived from the original (PDF) on 2016-03-04. Retrieved 2012-02-27. Wikipedia revision 1307759774, retrieved 2026-11-19
  9. ^ "Sampled differential dynamic programming". 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). doi:10.1109/IROS.2016.7759229. S2CID 1338737. Wikipedia revision 1307759774, retrieved 2026-11-19
  10. ^ Rajamäki, Joose; Hämäläinen, Perttu (June 2018). Regularizing Sampled Differential Dynamic Programming - IEEE Conference Publication. 2018 Annual American Control Conference (ACC). pp. 2182–2189. doi:10.23919/ACC.2018.8430799. S2CID 243932441. Retrieved 2018-10-19. Wikipedia revision 1307759774, retrieved 2026-11-19
  11. ^ Rajamäki, Joose (2018). Random Search Algorithms for Optimal Control. Aalto University. ISBN 978-952-60-8156-4. ISSN 1799-4942. Wikipedia revision 1307759774, retrieved 2026-11-19
  12. ^ Lefebvre, Tom; Crevecoeur, Guillaume (July 2019). "Path Integral Policy Improvement with Differential Dynamic Programming". 2019 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM). pp. 739–745. doi:10.1109/AIM.2019.8868359. hdl:1854/LU-8623968. ISBN 978-1-7281-2493-3. S2CID 204816072. Wikipedia revision 1307759774, retrieved 2026-11-19
  13. ^ Theodorou, Evangelos; Buchli, Jonas; Schaal, Stefan (May 2010). "Reinforcement learning of motor skills in high dimensions: A path integral approach". 2010 IEEE International Conference on Robotics and Automation. pp. 2397–2403. doi:10.1109/ROBOT.2010.5509336. ISBN 978-1-4244-5038-1. S2CID 15116370. Wikipedia revision 1307759774, retrieved 2026-11-19
  14. ^ Pavlov, Andrei; Shames, Iman; Manzie, Chris (2020). "Interior Point Differential Dynamic Programming". IEEE Transactions on Control Systems Technology. 29 (6): 2720. arXiv:2004.12710. Bibcode:2021ITCST..29.2720P. doi:10.1109/TCST.2021.3049416. Wikipedia revision 1307759774, retrieved 2026-11-19
edit edit source
  • The open-source software framework acados provides an efficient and embeddable implementation of DDP.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1307759774 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001307759774 · captured 2025-08-25 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Differential dynamic programming”, snapshot enwiki-001307759774. https://encyclopegia.org/a/differential-dynamic-programming