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.
Mots-clés : optimal control, discrete mechanics, discrete variational principle, convergence
@article{COCV_2011__17_2_322_0,
author = {Ober-Bl\"obaum, Sina and Junge, Oliver and Marsden, Jerrold E.},
title = {Discrete mechanics and optimal control: {An} analysis},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
pages = {322--352},
publisher = {EDP-Sciences},
volume = {17},
number = {2},
year = {2011},
doi = {10.1051/cocv/2010012},
mrnumber = {2801322},
language = {en},
url = {http://www.numdam.org/articles/10.1051/cocv/2010012/}
}
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 SP - 322 EP - 352 VL - 17 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/cocv/2010012/ DO - 10.1051/cocv/2010012 LA - en ID - COCV_2011__17_2_322_0 ER -
%0 Journal Article %A Ober-Blöbaum, Sina %A Junge, Oliver %A Marsden, Jerrold E. %T Discrete mechanics and optimal control: An analysis %J ESAIM: Control, Optimisation and Calculus of Variations %D 2011 %P 322-352 %V 17 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/cocv/2010012/ %R 10.1051/cocv/2010012 %G en %F COCV_2011__17_2_322_0
Ober-Blöbaum, Sina; Junge, Oliver; Marsden, Jerrold E. Discrete mechanics and optimal control: An analysis. ESAIM: Control, Optimisation and Calculus of Variations, Tome 17 (2011) no. 2, pp. 322-352. doi : 10.1051/cocv/2010012. http://www.numdam.org/articles/10.1051/cocv/2010012/
[1] , and , A collocation solver for mixed order systems of boundary value problems. Math. Comput. 33 (1979) 659-679. | MR | Zbl
[2] , 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] , Survey of numerical methods for trajectory optimization. AIAA J. Guid. Control Dyn. 21 (1998) 193-207. | Zbl
[4] and , Mesh refinement in direct transcription methods for optimal control. Optim. Control Appl. Meth. 19 (1998) 1-21. | MR
[5] and , Discrete Lagrangian reduction, discrete Euler-Poincaré equations, and semidirect products. Lett. Math. Phys. 49 (1999) 79-93. | MR | Zbl
[6] and , Discrete time Lagrangian mechanics on Lie groups, with an application to the Lagrange top. Comm. Math. Phys. 204 (1999) 147-188. | MR | Zbl
[7] , Numerical solutions of nonlinear multipoint boundary value problems with applications to optimal control. Z. Angew. Math. Mech. 58 (1978) T407-T409. | MR | Zbl
[8] and , A multiple shooting algorithm for direct solution of optimal control problems, in 9th IFAC World Congress, Budapest, Hungary, Pergamon Press (1984) 242-247.
[9] and , Computation of order conditions for symplectic partitioned Runge-Kutta schemes with application to optimal control. Numer. Math. 103 (2006) 1-10. | MR | Zbl
[10] and , Stochastic variational integrators. IMA J. Numer. Anal. 29 (2008) 421-443. | MR | Zbl
[11] and , Applied Optimal Control. Hemisphere (1975).
[12] , 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] and , 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. | MR | Zbl
[14] , Discrete calculus of variations. Int. J. Control 11 (1970) 393-407. | Zbl
[15] , Discrete-Time Systems: An Introduction With Interdisciplinary Applications. Prentice-Hall (1973). | MR
[16] , 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] and , Method of successive approximations for optimal control problems (survey paper). Opt. Control Appl. Meth. 3 (1982) 101-114. | Zbl
[18] , 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. | MR | Zbl
[19] and , Approximate solution of optimal control problems using third order hermite polynomial functions. Lect. Notes Comput. Sci. 27 (1975) 158-166.
[20] and , The Euler Approximation in State Constrained Optimal Control, in Mathematics of Computation 70, American Mathematical Society, USA (2001) 173-203. | MR | Zbl
[21] , and , Second order Runge-Kutta approximations in control constrained optimal control. SIAM J. Numer. Anal. 38 (2000) 202-226. | MR | Zbl
[22] , , and , Nonsmooth Lagrangian mechanics and variational collision integrators. SIAM J. Appl. Dyn. Syst. 2 (2003) 381-416. | MR | Zbl
[23] , Advanced calculus. Williams & Wilkins (1976). | MR | Zbl
[24] , Some numerical experiments with eigenvalue problems in ordinary differential equations, in Boundary value problems in differential equations, R.E. Langer Ed. (1960). | MR | Zbl
[25] , and , Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. Robot. 21 (2005) 1077-1091.
[26] , Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM (2000). | MR | Zbl
[27] , Convex control and dual approximations, in Constructive Approaches to Mathematical Models, Academic Press, New York, USA (1979) 189-202. | MR | Zbl
[28] , Runge-Kutta methods in optimal control and the transformed adjoint system. Numer. Math. 87 (2000) 247-282. | MR | Zbl
[29] , Numerical analysis in optimal control, in International Series of Numerical Mathematics 139, Birkhäuser Verlag, Basel, Switzerland (2001) 83-93. | MR | Zbl
[30] , and , Geometric numerical integration. Springer (2002). | MR | Zbl
[31] , Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program. 11 (1976) 263-282. | MR | Zbl
[32] , 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] and , A discrete version of Pontryagin's maximum principle. Oper. Res. 15 (1967) 139-146. | MR | Zbl
[34] and , Theory of a class of discrete optimal control systems. J. Elec. Ctrl. 17 (1964) 697-711. | MR
[35] and , Optimal reconfiguration of formation flying satellites, in IEEE Conference on Decision and Control and European Control Conference ECC, Seville, Spain (2005).
[36] , and , Discrete mechanics and optimal control, in 16th IFAC World Congress, Prague, Czech Republic (2005).
[37] , and , 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] , and , Symplectic energy-momentum integrators. Math. Phys. 40 (1999) 3353-3371. | MR | Zbl
[39] , , and , Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. Int. J. Numer. Meth. Eng. 49 (2000) 1295-1325. | MR | Zbl
[40] and , 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] , Minima of functions of several variables with inequalities as side constraints. Master's thesis, Department of Mathematics, University of Chicago, USA (1939).
[42] , Numerical methods for two-point boundary value problems. Blaisdell, Waltham, USA (1968). | MR | Zbl
[43] , Gradient theory of optimal flight paths. Journal of the American Rocket Society 30 (1960) 947-953. | Zbl
[44] , , , , and , Robust time-adaptive integrators for computer animation (in preparation).
[45] , Discrete geometric motion control of autonomous vehicles. Ph.D. Thesis, University of Southern California, USA (2008).
[46] and , Optimal control using nonholonomic integrators, in IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy (2007) 1832-1837.
[47] , , and , A discrete geometric optimal control framework for systems with symmetries. Robotics: Science and Systems 3 (2007) 1-8.
[48] , 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. | MR | Zbl
[49] and , Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statisics and Probability, J. Neyman Ed., University of California Press, Berkeley, USA (1951). | MR | Zbl
[50] , Can time be a discrete dynamical variable? Phys. Lett. B 121 (1983) 217-220.
[51] , Difference equations and conservation laws. J. Stat. Phys. 46 (1987) 843-860. | MR
[52] , and , Attitude maneuvers of a rigid spacecraft in a circular orbit, in American Control Conference, Minneapolis, USA (2006) 1742-1747.
[53] , and , 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] , 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). | Zbl
[55] , , and , Asynchronous variational integrators. Arch. Ration. Mech. Anal. 167 (2003) 85-146. | MR | Zbl
[56] , , and , 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] , and , Discrete mechanics and optimal control for constrained systems. Optim. Contr. Appl. Meth. (2009) DOI: 10.1002/oca.912. | Zbl
[58] , First integrals in the discrete calculus of variation. Aequ. Math. 9 (1973) 210-220. | MR | Zbl
[59] , 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. | MR | Zbl
[60] , Canonical structure and symmetries for discrete systems. Math. Jap. 25 (1980) 405-420. | MR | Zbl
[61] , Extension of discrete Noether theorem. Math. Jap. 26 (1981) 85-90. | MR | Zbl
[62] , Lagrangian formulation of discrete systems and concept of difference space. Math. Jap. 27 (1981) 345-356. | MR | Zbl
[63] and , Multisymplectic geometry, covariant Hamiltonians, and water waves. Math. Proc. Camb. Phil. Soc. 125 (1999) 553-575. | MR | Zbl
[64] and , Discrete mechanics and variational integrators. Acta Numer. 10 (2001) 357-514. | MR | Zbl
[65] , and , Multisymplectic geometry, variational integrators, and nonlinear PDEs. Commun. Math. Phys. 199 (1998) 351-395. | MR | Zbl
[66] , and , Discrete Euler-Poincaré and Lie Poisson equations. Nonlinearity 12 (1999) 1647-1662. | MR | Zbl
[67] , and , Symmetry reduction of discrete Lagrangian mechanics on Lie groups. Geometry and Physics 36 (1999) 140-151. | MR | Zbl
[68] , Discrete mechanics and optimal control. Master's Thesis, Department of Control and Dynamical Systems, California Institute of Technology, USA (2006).
[69] and , Discrete mechanics and optimal control for image registration, in Computational Techniques and Applications Conference (CTAC) (2006). | MR
[70] , Gradient algorithms for the optimization of dynamic systems, in Control and Dynamic Systems 60, C.T. Leondes Ed. (1980) 1-52.
[71] , Discrete mechanics and optimal control. Ph.D. Thesis, University of Paderborn, Germany (2008).
[72] and , Error analysis of variational integrators of unconstrained lagrangian systems. Numer. Math. 113 (2009) 243-264. | MR | Zbl
[73] , and , 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] , , and , The mathematical theory of optimal processes. John Wiley & Sons (1962). | MR
[75] , A fast algorithm for nonlinearly constrained optimization calculations, in Numerical Analysis Lecture Notes in Mathematics 630, G.A. Watson Ed., Springer (1978) 261-280. | MR | Zbl
[76] , Numerical methods for optimal control problems with state constraints. Springer (1999). | MR | Zbl
[77] , Automatic Differentiation: Techniques and Applications, Lect. Notes Comput. Sci. 120. Springer Verlag, Berlin, Germany (1981). | Zbl
[78] , Optimal flapping strokes for self-propulsion in a perfect fluid, in American Control Conference, Minneapolis, USA (2006) 4118-4122.
[79] and , The averaged moduli of smoothness. John Wiley (1988). | MR | Zbl
[80] , Hamiltonian methods of Runge-Kutta type and their variational interpretation. Math. Model. 2 (1990) 78-87. | MR | Zbl
[81] , Optimization methods. Springer (1975). | Zbl
[82] , 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. | MR | Zbl
[83] , Numerical hybrid optimal control and related topics. Habilitation Thesis, TU München, Germany (2000).
[84] , and , ADOL-C: a package for the automatic differentiation of algorithms written in C/C++. ACM TOMS 22 (1996) 131-167. | Zbl
[85] and , Mechanical integrators derived from a discrete variational principle. Physica D 106 (1997) 223-246. | MR | Zbl
[86] and , 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. | MR | Zbl
[87] , A simple automatic derivative evaluation program. Commun. ACM 7 (1964) 463-464. | Zbl
Cité par Sources :
