Discrete mechanics and optimal control: An analysis*

Sina Ober-Blöbaum; Oliver Junge; Jerrold E. Marsden

ESAIM: Control, Optimisation and Calculus of Variations (2011)

  • Volume: 17, Issue: 2, page 322-352
  • ISSN: 1292-8119

Abstract

top
The optimal control of a mechanical system is of crucial importance in many application areas. Typical examples are the determination of a time-minimal path in vehicle dynamics, a minimal energy trajectory in space mission design, or optimal motion sequences in robotics and biomechanics. In most cases, some sort of discretization of the original, infinite-dimensional optimization problem has to be performed in order to make the problem amenable to computations. The approach proposed in this paper is to directly discretize the variational description of the system's motion. The resulting optimization algorithm lets the discrete solution directly inherit characteristic structural properties from the continuous one like symmetries and integrals of the motion. We show that the DMOC (Discrete Mechanics and Optimal Control) approach is equivalent to a finite difference discretization of Hamilton's equations by a symplectic partitioned Runge-Kutta scheme and employ this fact in order to give a proof of convergence. The numerical performance of DMOC and its relationship to other existing optimal control methods are investigated.

How to cite

top

Ober-Blöbaum, Sina, Junge, Oliver, and Marsden, Jerrold E.. "Discrete mechanics and optimal control: An analysis*." ESAIM: Control, Optimisation and Calculus of Variations 17.2 (2011): 322-352. <http://eudml.org/doc/197266>.

@article{Ober2011,
abstract = { The optimal control of a mechanical system is of crucial importance in many application areas. Typical examples are the determination of a time-minimal path in vehicle dynamics, a minimal energy trajectory in space mission design, or optimal motion sequences in robotics and biomechanics. In most cases, some sort of discretization of the original, infinite-dimensional optimization problem has to be performed in order to make the problem amenable to computations. The approach proposed in this paper is to directly discretize the variational description of the system's motion. The resulting optimization algorithm lets the discrete solution directly inherit characteristic structural properties from the continuous one like symmetries and integrals of the motion. We show that the DMOC (Discrete Mechanics and Optimal Control) approach is equivalent to a finite difference discretization of Hamilton's equations by a symplectic partitioned Runge-Kutta scheme and employ this fact in order to give a proof of convergence. The numerical performance of DMOC and its relationship to other existing optimal control methods are investigated. },
author = {Ober-Blöbaum, Sina, Junge, Oliver, Marsden, Jerrold E.},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {Optimal control; discrete mechanics; discrete variational principle; convergence; optimal control},
language = {eng},
month = {5},
number = {2},
pages = {322-352},
publisher = {EDP Sciences},
title = {Discrete mechanics and optimal control: An analysis*},
url = {http://eudml.org/doc/197266},
volume = {17},
year = {2011},
}

TY - JOUR
AU - Ober-Blöbaum, Sina
AU - Junge, Oliver
AU - Marsden, Jerrold E.
TI - Discrete mechanics and optimal control: An analysis*
JO - ESAIM: Control, Optimisation and Calculus of Variations
DA - 2011/5//
PB - EDP Sciences
VL - 17
IS - 2
SP - 322
EP - 352
AB - The optimal control of a mechanical system is of crucial importance in many application areas. Typical examples are the determination of a time-minimal path in vehicle dynamics, a minimal energy trajectory in space mission design, or optimal motion sequences in robotics and biomechanics. In most cases, some sort of discretization of the original, infinite-dimensional optimization problem has to be performed in order to make the problem amenable to computations. The approach proposed in this paper is to directly discretize the variational description of the system's motion. The resulting optimization algorithm lets the discrete solution directly inherit characteristic structural properties from the continuous one like symmetries and integrals of the motion. We show that the DMOC (Discrete Mechanics and Optimal Control) approach is equivalent to a finite difference discretization of Hamilton's equations by a symplectic partitioned Runge-Kutta scheme and employ this fact in order to give a proof of convergence. The numerical performance of DMOC and its relationship to other existing optimal control methods are investigated.
LA - eng
KW - Optimal control; discrete mechanics; discrete variational principle; convergence; optimal control
UR - http://eudml.org/doc/197266
ER -

References

top
  1. U. Ascher, J. Christiansen and R.D. Russell, A collocation solver for mixed order systems of boundary value problems. Math. Comput.33 (1979) 659–679.  
  2. V. Bär, Ein Kollokationsverfahren zur numerischen Lösung allgemeiner Mehrpunktrandwertaufgaben mit Schalt- und Sprungbedingungen mit Anwendungen in der Optimalen Steuerung und der Parameteridentifizierung. Diploma Thesis, Bonn, Germany (1983).  
  3. J.T. Betts, Survey of numerical methods for trajectory optimization. AIAA J. Guid. Control Dyn.21 (1998) 193–207.  
  4. J.T. Betts and W.P. Huffmann, Mesh refinement in direct transcription methods for optimal control. Optim. Control Appl. Meth.19 (1998) 1–21.  
  5. A.I. Bobenko and Y.B. Suris, Discrete Lagrangian reduction, discrete Euler-Poincaré equations, and semidirect products. Lett. Math. Phys.49 (1999) 79–93.  
  6. A.I. Bobenko and Y.B. Suris, Discrete time Lagrangian mechanics on Lie groups, with an application to the Lagrange top. Comm. Math. Phys.204 (1999) 147–188.  
  7. H.G. Bock, Numerical solutions of nonlinear multipoint boundary value problems with applications to optimal control. Z. Angew. Math. Mech.58 (1978) T407–T409.  
  8. H.G. Bock and K.J. Plitt, A multiple shooting algorithm for direct solution of optimal control problems, in 9th IFAC World Congress, Budapest, Hungary, Pergamon Press (1984) 242–247.  
  9. J.F. Bonnans and J. Laurent-Varin, Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control. Numer. Math.103 (2006) 1–10.  
  10. N. Bou-Rabee and H. Owhadi, Stochastic variational integrators. IMA J. Numer. Anal.29 (2008) 421–443.  
  11. A.E. Bryson and Y.C. Ho, Applied Optimal Control. Hemisphere (1975).  
  12. R. Bulirsch, Die Mehrzielmethode zur numerischen Lösung von nichtlinearen Randwertproblemen und Aufgaben der optimalen Steuerung. Report of the Carl-Cranz-Gesellschaft e.V., DLR, Oberpfaffenhofen, Germany (1971).  
  13. C. Büskens and H. Maurer, SQP-methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control. J. Comput. Appl. Math.120 (2000) 85–108.  
  14. J.A. Cadzow, Discrete calculus of variations. Int. J. Control11 (1970) 393–407.  
  15. J.A. Cadzow, Discrete-Time Systems: An Introduction With Interdisciplinary Applications. Prentice-Hall (1973).  
  16. A.L. Cauchy, Méthode générale pour la résolution des systèmes d'équations simultanées. C. R. Acad. Sci.25 (1847) 536–538.  
  17. F.L. Chernousko and A.A. Luybushin, Method of successive approximations for optimal control problems (survey paper). Opt. Control Appl. Meth.3 (1982) 101–114.  
  18. P. Deuflhard, A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting. Numer. Math.22 (1974) 289–315.  
  19. E.D. Dickmanns and K.H. Well, Approximate solution of optimal control problems using third order hermite polynomial functions. Lect. Notes Comput. Sci.27 (1975) 158–166.  
  20. A.L. Dontchev and W.W. Hager, The Euler Approximation in State Constrained Optimal Control, in Mathematics of Computation70, American Mathematical Society, USA (2001) 173–203.  
  21. A.L. Dontchev, W.W. Hager and V.M. Veliov, Second order Runge-Kutta approximations in control constrained optimal control. SIAM J. Numer. Anal.38 (2000) 202–226.  
  22. R.C. Fetecau, J.E. Marsden, M. Ortiz and M. West, Nonsmooth Lagrangian mechanics and variational collision integrators. SIAM J. Appl. Dyn. Syst.2 (2003) 381–416.  
  23. L. Flatto, Advanced calculus. Williams & Wilkins (1976).  
  24. L. Fox, Some numerical experiments with eigenvalue problems in ordinary differential equations, in Boundary value problems in differential equations, R.E. Langer Ed. (1960).  
  25. E. Frazzoli, M.A. Dahleh and E. Feron, Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. Robot.21 (2005) 1077–1091.  
  26. A. Griewank, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM (2000).  
  27. W.W. Hager, Convex control and dual approximations, in Constructive Approaches to Mathematical Models, Academic Press, New York, USA (1979) 189–202.  
  28. W.W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system. Numer. Math.87 (2000) 247–282.  
  29. W.W. Hager, Numerical analysis in optimal control, in International Series of Numerical Mathematics139, Birkhäuser Verlag, Basel, Switzerland (2001) 83–93.  
  30. E. Hairer, C. Lubich and G. Wanner, Geometric numerical integration. Springer (2002).  
  31. S.P. Han, Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program.11 (1976) 263–282.  
  32. P. Hiltmann, Numerische Lösung von Mehrpunkt-Randwertproblemen und Aufgaben der optimalen Steuerung über endlichdimensionalen Räumen. Ph.D. Thesis, Fakultät für Mathematik und Informatik, Technische Universität München, Germany (1990).  
  33. C.L. Hwang and L.T. Fan, A discrete version of Pontryagin's maximum principle. Oper. Res.15 (1967) 139–146.  
  34. B.W. Jordan and E. Polak, Theory of a class of discrete optimal control systems. J. Elec. Ctrl.17 (1964) 697–711.  
  35. O. Junge and S. Ober-Blöbaum, Optimal reconfiguration of formation flying satellites, in IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain (2005).  
  36. O. Junge, J.E. Marsden and S. Ober-Blöbaum, Discrete mechanics and optimal control, in 16th IFAC World Congress, Prague, Czech Republic (2005).  
  37. O. Junge, J.E. Marsden and S. Ober-Blöbaum, Optimal reconfiguration of formation flying spacecraft - a decentralized approach, in IEEE Conference on Decision and Control and European Control Conference ECC, San Diego, USA (2006) 5210–5215.  
  38. C. Kane, J.E. Marsden and M. Ortiz, Symplectic energy-momentum integrators. Math. Phys.40 (1999) 3353–3371.  
  39. C. Kane, J.E. Marsden, M. Ortiz and M. West, Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Int. J. Numer. Meth. Eng.49 (2000) 1295–1325.  
  40. E. Kanso and J.E. Marsden, Optimal motion of an articulated body in a perfect fluid, in IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain (2005).  
  41. W. Karush, Minima of functions of several variables with inequalities as side constraints. Master's thesis, Department of Mathematics, University of Chicago, USA (1939).  
  42. H.B. Keller, Numerical methods for two-point boundary value problems. Blaisdell, Waltham, USA (1968).  
  43. H.J. Kelley, Gradient theory of optimal flight paths. Journal of the American Rocket Society30 (1960) 947–953.  
  44. L. Kharevych, P. Mullen, S. Leyendecker, Y. Tong, J.E. Marsden and M. Desbrun, Robust time-adaptive integrators for computer animation (in preparation).  
  45. M. Kobilarov, Discrete geometric motion control of autonomous vehicles. Ph.D. Thesis, University of Southern California, USA (2008).  
  46. M. Kobilarov and G.S. Sukhatme, Optimal control using nonholonomic integrators, in IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy (2007) 1832–1837.  
  47. M. Kobilarov, M. Desbrun, J.E. Marsden and G.S. Sukhatme, A discrete geometric optimal control framework for systems with symmetries. Robotics: Science and Systems3 (2007) 1–8.  
  48. D. Kraft, On converting optimal control problems into nonlinear programming problems, in Computational Mathematical Programming F15 of NATO ASI series, K. Schittkowsky Ed., Springer (1985) 261–280.  
  49. H.W. Kuhn and A.W. Tucker, Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statisics and Probability, J. Neyman Ed., University of California Press, Berkeley, USA (1951).  
  50. T.D. Lee, Can time be a discrete dynamical variable? Phys. Lett. B121 (1983) 217–220.  
  51. T.D. Lee, Difference equations and conservation laws. J. Stat. Phys.46 (1987) 843–860.  
  52. T. Lee, N.H. McClamroch and M. Leok, Attitude maneuvers of a rigid spacecraft in a circular orbit, in American Control Conference, Minneapolis, USA (2006) 1742–1747.  
  53. T. Lee, N.H. McClamroch and M. Leok, Optimal control of a rigid body using geometrically exact computations on SE(3), in IEEE CDC and ECC, San Diego, USA (2006) 2710–2715.  
  54. D.B. Leineweber, Efficient reduced SQP methods for the optimization of chemical processes described by large sparse DAE models, in Fortschr.-Bericht VDI Reihe 3, Verfahrenstechnik613, VDI-Verlag (1999).  
  55. A. Lew, J.E. Marsden, M. Ortiz and M. West, Asynchronous variational integrators. Arch. Ration. Mech. Anal.167 (2003) 85–146.  
  56. S. Leyendecker, S. Ober-Blöbaum, J.E. Marsden and M. Ortiz, Discrete mechanics and optimal control for constrained multibody dynamics, in 6th International Conference on Multibody Systems, Nonlinear Dynamics, and Control, ASME International Design Engineering Technical Conferences, Las Vegas, USA (2007).  
  57. S. Leyendecker, S. Ober-Blöbaum and J.E. Marsden, Discrete mechanics and optimal control for constrained systems. Optim. Contr. Appl. Meth. (2009) DOI: .  DOI10.1002/oca.912
  58. J.D. Logan, First integrals in the discrete calculus of variation. Aequ. Math.9 (1973) 210–220.  
  59. R. MacKay, Some aspects of the dynamics of Hamiltonian systems, in The dynamics of numerics and the numerics of dynamics, D.S. Broomhead and A. Iserles Eds., Clarendon Press, Oxford, UK (1992) 137–193.  
  60. S. Maeda, Canonical structure and symmetries for discrete systems. Math. Jap.25 (1980) 405–420.  
  61. S. Maeda, Extension of discrete Noether theorem. Math. Jap.26 (1981) 85–90.  
  62. S. Maeda, Lagrangian formulation of discrete systems and concept of difference space. Math. Jap.27 (1981) 345–356.  
  63. J.E. Marsden and S. Shkoller, Multisymplectic geometry, covariant Hamiltonians, and water waves. Math. Proc. Camb. Phil. Soc.125 (1999) 553–575.  
  64. J.E. Marsden and M. West, Discrete mechanics and variational integrators. Acta Numer.10 (2001) 357–514.  
  65. J.E. Marsden, G.W. Patrick and S. Shkoller, Multisymplectic geometry, variational integrators, and nonlinear PDEs. Commun. Math. Phys.199 (1998) 351–395.  
  66. J.E. Marsden, S. Pekarsky and S. Shkoller, Discrete Euler-Poincaré and Lie Poisson equations. Nonlinearity12 (1999) 1647-1662.  
  67. J.E. Marsden, S. Pekarsky and S. Shkoller, Symmetry reduction of discrete Lagrangian mechanics on Lie groups. Geometry and Physics36 (1999) 140–151.  
  68. J. Martin, Discrete mechanics and optimal control. Master's Thesis, Department of Control and Dynamical Systems, California Institute of Technology, USA (2006).  
  69. R.I. McLachlan and S. Marsland, Discrete mechanics and optimal control for image registration, in Computational Techniques and Applications Conference (CTAC) (2006).  
  70. A. Miele, Gradient algorithms for the optimization of dynamic systems, in Control and Dynamic Systems60, C.T. Leondes Ed. (1980) 1–52.  
  71. S. Ober-Blöbaum, Discrete mechanics and optimal control. Ph.D. Thesis, University of Paderborn, Germany (2008).  
  72. G.W. Patrick and C. Cuell, Error analysis of variational integrators of unconstrained lagrangian systems. Numer. Math.113 (2009) 243–264.  
  73. D. Pekarek, A.D. Ames and J.E. Marsden, Discrete mechanics and optimal control applied to the compass gait biped, in IEEE Conference on Decision and Control and European Control Conference ECC, New Orleans, USA (2007).  
  74. L.S. Pontryagin, V.G. Boltyanski, R.V. Gamkrelidze and E.F. Miscenko, The mathematical theory of optimal processes. John Wiley & Sons (1962).  
  75. M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in Numerical AnalysisLecture Notes in Mathematics630, G.A. Watson Ed., Springer (1978) 261–280.  
  76. R. Pytlak, Numerical methods for optimal control problems with state constraints. Springer (1999).  
  77. L.B. Rall, Automatic Differentiation: Techniques and Applications, Lect. Notes Comput. Sci.120. Springer Verlag, Berlin, Germany (1981).  
  78. S.D. Ross, Optimal flapping strokes for self-propulsion in a perfect fluid, in American Control Conference, Minneapolis, USA (2006) 4118–4122.  
  79. B. Sendov and V.A. Popov, The averaged moduli of smoothness. John Wiley (1988).  
  80. Y.B. Suris, Hamiltonian methods of Runge-Kutta type and their variational interpretation. Math. Model.2 (1990) 78–87.  
  81. H. Tolle, Optimization methods. Springer (1975).  
  82. O. von Stryk, Numerical solution of optimal control problems by direct collocation, in Optimal Control - Calculus of Variation, Optimal Control Theory and Numerical Methods, R. Bulirsch, A. Miele, J. Stoer and K.H. Well Eds., International Series of Numerical Mathematics111, Birkhäuser (1993) 129–143.  
  83. O. von Stryk, Numerical hybrid optimal control and related topics. Habilitation Thesis, TU München, Germany (2000).  
  84. A. Walther, A. Kowarz and A. Griewank, ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM TOMS22 (1996) 131–167.  
  85. J.M. Wendlandt and J.E. Marsden, Mechanical integrators derived from a discrete variational principle. Physica D106 (1997) 223–246.  
  86. J.M. Wendlandt and J.E. Marsden, Mechanical systems with symmetry, variational principles and integration algorithms, in Current and Future Directions in Applied Mathematics, M. Alber, B. Hu and J. Rosenthal Eds., Birkhäuser (1997) 219–261.  
  87. R.E. Wengert, A simple automatic derivative evaluation program. Commun. ACM7 (1964) 463–464.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.