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/272861>.

@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},
language = {eng},
number = {2},
pages = {322-352},
publisher = {EDP-Sciences},
title = {Discrete mechanics and optimal control: An analysis},
url = {http://eudml.org/doc/272861},
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
PY - 2011
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
UR - http://eudml.org/doc/272861
ER -

References

top
  1. [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. Zbl0407.65035MR521281
  2. [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. [3] J.T. Betts, Survey of numerical methods for trajectory optimization. AIAA J. Guid. Control Dyn. 21 (1998) 193–207. Zbl1158.49303
  4. [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. MR1623173
  5. [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. Zbl0965.70025MR1720528
  6. [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. Zbl0945.70010MR1705669
  7. [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. Zbl0383.65053MR507663
  8. [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. [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. Zbl1112.65063MR2207612
  10. [10] N. Bou-Rabee and H. Owhadi, Stochastic variational integrators. IMA J. Numer. Anal.29 (2008) 421–443. Zbl1171.37027MR2491434
  11. [11] A.E. Bryson and Y.C. Ho, Applied Optimal Control. Hemisphere (1975). 
  12. [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. [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. Zbl0963.65070MR1781710
  14. [14] J.A. Cadzow, Discrete calculus of variations. Int. J. Control11 (1970) 393–407. Zbl0193.07601
  15. [15] J.A. Cadzow, Discrete-Time Systems: An Introduction With Interdisciplinary Applications. Prentice-Hall (1973). MR490243
  16. [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. [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. Zbl0485.49003
  18. [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. Zbl0313.65070MR351093
  19. [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. [20] A.L. Dontchev and W.W. Hager, The Euler Approximation in State Constrained Optimal Control, in Mathematics of Computation 70, American Mathematical Society, USA (2001) 173–203. Zbl0987.49017MR1681116
  21. [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. Zbl0968.49022MR1770350
  22. [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. Zbl1088.37045MR2031279
  23. [23] L. Flatto, Advanced calculus. Williams & Wilkins (1976). Zbl0314.26002MR387501
  24. [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). Zbl0100.12602MR114302
  25. [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. [26] A. Griewank, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM (2000). Zbl1159.65026MR1753583
  27. [27] W.W. Hager, Convex control and dual approximations, in Constructive Approaches to Mathematical Models, Academic Press, New York, USA (1979) 189–202. Zbl0443.49007MR641919
  28. [28] W.W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system. Numer. Math.87 (2000) 247–282. Zbl0991.49020MR1804658
  29. [29] W.W. Hager, Numerical analysis in optimal control, in International Series of Numerical Mathematics 139, Birkhäuser Verlag, Basel, Switzerland (2001) 83–93. Zbl1024.49026MR1901632
  30. [30] E. Hairer, C. Lubich and G. Wanner, Geometric numerical integration. Springer (2002). Zbl0994.65135MR1904823
  31. [31] S.P. Han, Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program.11 (1976) 263–282. Zbl0364.90097MR483440
  32. [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). Zbl0709.65062
  33. [33] C.L. Hwang and L.T. Fan, A discrete version of Pontryagin's maximum principle. Oper. Res.15 (1967) 139–146. Zbl0155.42504MR205726
  34. [34] B.W. Jordan and E. Polak, Theory of a class of discrete optimal control systems. J. Elec. Ctrl.17 (1964) 697–711. MR179019
  35. [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. [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). Zbl05908225
  37. [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. [38] C. Kane, J.E. Marsden and M. Ortiz, Symplectic energy-momentum integrators. Math. Phys.40 (1999) 3353–3371. Zbl0983.70014MR1697008
  39. [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. Zbl0969.70004MR1805500
  40. [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. [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. [42] H.B. Keller, Numerical methods for two-point boundary value problems. Blaisdell, Waltham, USA (1968). Zbl0172.19503MR230476
  43. [43] H.J. Kelley, Gradient theory of optimal flight paths. Journal of the American Rocket Society30 (1960) 947–953. Zbl0096.42002
  44. [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. [45] M. Kobilarov, Discrete geometric motion control of autonomous vehicles. Ph.D. Thesis, University of Southern California, USA (2008). 
  46. [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. [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 Systems 3 (2007) 1–8. Zbl05501694
  48. [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. Zbl0572.49015MR820046
  49. [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). Zbl0044.05903MR47303
  50. [50] T.D. Lee, Can time be a discrete dynamical variable? Phys. Lett. B121 (1983) 217–220. 
  51. [51] T.D. Lee, Difference equations and conservation laws. J. Stat. Phys.46 (1987) 843–860. MR893121
  52. [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. [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. [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, Verfahrenstechnik 613, VDI-Verlag (1999). Zbl0997.65502
  55. [55] A. Lew, J.E. Marsden, M. Ortiz and M. West, Asynchronous variational integrators. Arch. Ration. Mech. Anal.167 (2003) 85–146. Zbl1055.74041MR1971150
  56. [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). Zbl1211.49039
  57. [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: 10.1002/oca.912. Zbl1211.49039
  58. [58] J.D. Logan, First integrals in the discrete calculus of variation. Aequ. Math.9 (1973) 210–220. Zbl0268.49022MR328397
  59. [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. Zbl0764.58009MR1173232
  60. [60] S. Maeda, Canonical structure and symmetries for discrete systems. Math. Jap.25 (1980) 405–420. Zbl0446.70022MR594539
  61. [61] S. Maeda, Extension of discrete Noether theorem. Math. Jap.26 (1981) 85–90. Zbl0458.70002MR613471
  62. [62] S. Maeda, Lagrangian formulation of discrete systems and concept of difference space. Math. Jap.27 (1981) 345–356. Zbl0531.70020MR663162
  63. [63] J.E. Marsden and S. Shkoller, Multisymplectic geometry, covariant Hamiltonians, and water waves. Math. Proc. Camb. Phil. Soc.125 (1999) 553–575. Zbl0922.58029MR1656833
  64. [64] J.E. Marsden and M. West, Discrete mechanics and variational integrators. Acta Numer.10 (2001) 357–514. Zbl1123.37327MR2009697
  65. [65] J.E. Marsden, G.W. Patrick and S. Shkoller, Multisymplectic geometry, variational integrators, and nonlinear PDEs. Commun. Math. Phys.199 (1998) 351–395. Zbl0951.70002MR1666871
  66. [66] J.E. Marsden, S. Pekarsky and S. Shkoller, Discrete Euler-Poincaré and Lie Poisson equations. Nonlinearity12 (1999) 1647-1662. Zbl0978.37045MR1726670
  67. [67] J.E. Marsden, S. Pekarsky and S. Shkoller, Symmetry reduction of discrete Lagrangian mechanics on Lie groups. Geometry and Physics36 (1999) 140–151. Zbl0976.70011MR1783688
  68. [68] J. Martin, Discrete mechanics and optimal control. Master's Thesis, Department of Control and Dynamical Systems, California Institute of Technology, USA (2006). 
  69. [69] R.I. McLachlan and S. Marsland, Discrete mechanics and optimal control for image registration, in Computational Techniques and Applications Conference (CTAC) (2006). Zbl1334.94035MR2318548
  70. [70] A. Miele, Gradient algorithms for the optimization of dynamic systems, in Control and Dynamic Systems 60, C.T. Leondes Ed. (1980) 1–52. 
  71. [71] S. Ober-Blöbaum, Discrete mechanics and optimal control. Ph.D. Thesis, University of Paderborn, Germany (2008). Zbl05908225
  72. [72] G.W. Patrick and C. Cuell, Error analysis of variational integrators of unconstrained lagrangian systems. Numer. Math.113 (2009) 243–264. Zbl1177.65119MR2529508
  73. [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). Zbl05908225
  74. [74] L.S. Pontryagin, V.G. Boltyanski, R.V. Gamkrelidze and E.F. Miscenko, The mathematical theory of optimal processes. John Wiley & Sons (1962). MR166037
  75. [75] M.J.D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in Numerical Analysis Lecture Notes in Mathematics 630, G.A. Watson Ed., Springer (1978) 261–280. Zbl0374.65032MR483447
  76. [76] R. Pytlak, Numerical methods for optimal control problems with state constraints. Springer (1999). Zbl0928.49002MR1713434
  77. [77] L.B. Rall, Automatic Differentiation: Techniques and Applications, Lect. Notes Comput. Sci. 120. Springer Verlag, Berlin, Germany (1981). Zbl0473.68025
  78. [78] S.D. Ross, Optimal flapping strokes for self-propulsion in a perfect fluid, in American Control Conference, Minneapolis, USA (2006) 4118–4122. 
  79. [79] B. Sendov and V.A. Popov, The averaged moduli of smoothness. John Wiley (1988). Zbl0653.65002MR995672
  80. [80] Y.B. Suris, Hamiltonian methods of Runge-Kutta type and their variational interpretation. Math. Model.2 (1990) 78–87. Zbl0972.70500MR1064467
  81. [81] H. Tolle, Optimization methods. Springer (1975). Zbl0312.49001
  82. [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 Mathematics 111, Birkhäuser (1993) 129–143. Zbl0790.49024MR1298003
  83. [83] O. von Stryk, Numerical hybrid optimal control and related topics. Habilitation Thesis, TU München, Germany (2000). 
  84. [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. Zbl0884.65015
  85. [85] J.M. Wendlandt and J.E. Marsden, Mechanical integrators derived from a discrete variational principle. Physica D106 (1997) 223–246. Zbl0963.70507MR1462313
  86. [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. Zbl0936.70004MR1445103
  87. [87] R.E. Wengert, A simple automatic derivative evaluation program. Commun. ACM7 (1964) 463–464. Zbl0131.34602

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.