A set oriented approach to global optimal control
ESAIM: Control, Optimisation and Calculus of Variations, Tome 10 (2004) no. 2, pp. 259-270.

We describe an algorithm for computing the value function for “all source, single destination” discrete-time nonlinear optimal control problems together with approximations of associated globally optimal control strategies. The method is based on a set oriented approach for the discretization of the problem in combination with graph-theoretic techniques. The central idea is that a discretization of phase space of the given problem leads to an (all source, single destination) shortest path problem on a finite graph. The method is illustrated by two numerical examples, namely a single pendulum on a cart and a parametrically driven inverted double pendulum.

DOI : 10.1051/cocv:2004006
Classification : 49J53, 49M25, 65K10, 90C39
Mots clés : global optimal control, value function, set oriented method, shortest path
@article{COCV_2004__10_2_259_0,
     author = {Junge, Oliver and Osinga, Hinke M.},
     title = {A set oriented approach to global optimal control},
     journal = {ESAIM: Control, Optimisation and Calculus of Variations},
     pages = {259--270},
     publisher = {EDP-Sciences},
     volume = {10},
     number = {2},
     year = {2004},
     doi = {10.1051/cocv:2004006},
     mrnumber = {2083487},
     zbl = {1072.49014},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/cocv:2004006/}
}
TY  - JOUR
AU  - Junge, Oliver
AU  - Osinga, Hinke M.
TI  - A set oriented approach to global optimal control
JO  - ESAIM: Control, Optimisation and Calculus of Variations
PY  - 2004
SP  - 259
EP  - 270
VL  - 10
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/cocv:2004006/
DO  - 10.1051/cocv:2004006
LA  - en
ID  - COCV_2004__10_2_259_0
ER  - 
%0 Journal Article
%A Junge, Oliver
%A Osinga, Hinke M.
%T A set oriented approach to global optimal control
%J ESAIM: Control, Optimisation and Calculus of Variations
%D 2004
%P 259-270
%V 10
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/cocv:2004006/
%R 10.1051/cocv:2004006
%G en
%F COCV_2004__10_2_259_0
Junge, Oliver; Osinga, Hinke M. A set oriented approach to global optimal control. ESAIM: Control, Optimisation and Calculus of Variations, Tome 10 (2004) no. 2, pp. 259-270. doi : 10.1051/cocv:2004006. http://archive.numdam.org/articles/10.1051/cocv:2004006/

[1] R.A. Brooks and T. Lozano-Pérez, A subdivision algorithm in configuration space for findpath with rotation. IEEE Systems, Man and Cybernetics 15 (1985) 224-233.

[2] M. Broucke, A geometric approach to bisimulation and verification of hybrid systems, in HSCC 1999, LNCS, F.W. Vaandragerand and J.H. van Schuppen Eds., Springer 1569 (1999) 61-75. | Zbl

[3] M. Broucke, M.D. Di Benedetto, S. Di Gennaro and A. Sangiovanni-Vincentelli, Theory of optimal control using bisimulations, in HSCC 2000, LNCS, N. Lynch and B. Krogh Eds., Springer 1790 (2000) 89-102. | Zbl

[4] M. Broucke, M.D. Di Benedetto, S. Di Gennaro and A. Sangiovanni-Vincentelli, Optimal control using bisimulations: Implementation, in HSCC 2001, LNCS, M.D. Di Benedetto and A. Sangiovanni-Vincentelli Eds., Springer 2034 (2001) 175-188. | Zbl

[5] T.H. Cormen, C.E. Leierson and R.L. Rivest, Introduction to Algorithms. Cambridge, Mass. MIT Press, New York McGraw-Hill (1990). | MR | Zbl

[6] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors. Numer. Math. 75 (1997) 293-317. | MR | Zbl

[7] M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIO - Set oriented numerical methods for dynamical systems, in Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, B. Fiedler Ed., Springer (2001) 145-174. | Zbl

[8] E.W. Dijkstra, A Note on Two Problems in Connection with Graphs. Numer. Math. 5 (1959) 269-271. | MR | Zbl

[9] M. Falcone, Numerical solution of Dynamic Programming equations, in Viscosity solutions and deterministic optimal control problems, M. Bardi and I. Capuzzo Dolcetta Eds., Birkhäuser (1997).

[10] Z. Galias, Interval methods for rigorous investigations of periodic orbits. Int. J. Bifur. Chaos 11 (2001) 2427-2450. | MR | Zbl

[11] L. Grüne, An Adaptive Grid Scheme for the discrete Hamilton-Jacobi-Bellman Equation. Numer. Math. 75 (1997) 319-337. | MR | Zbl

[12] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, User's Guide for NPSOL (Version 4.0): a Fortran package for nonlinear programming, Report SOL 86-2, Systems Optimization Laboratory, Stanford University (1986).

[13] J. Hauser and H.M. Osinga, On the geometry of optimal control: the inverted pendulum example, in Proc. Amer. Control Conf., Arlington VA (2001) 1721-1726.

[14] A. Jadbabaie, J. Yu and J. Hauser, Unconstrained receding horizon control of nonlinear systems. IEEE Trans. Automat. Control 46 (2001) 776-783. | MR | Zbl

[15] O. Junge, Rigorous discretization of subdivision techniques, in Proc. Int. Conf. Differential Equations Equadiff 99, B. Fiedler, K. Gröger and J. Sprekels Eds., World Scientific 2 (2000) 916-918. | MR | Zbl

[16] L.C. Polymenakos, D.P. Bertsekas and J.N. Tsitsiklis, Implementation of efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 43 (1998) 278-283. | MR | Zbl

[17] K. Schiele, On the stabilization of a parametrically driven inverted double pendulum. Z. Angew. Math. Mech. 77 (1997) 143-146. | MR | Zbl

[18] J.A. Sethian and A. Vladimirsky, Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Nat. Acad. Sci. USA 98 (2001) 11069-11074. | MR | Zbl

[19] E.D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, Texts in Applied Mathematics 6, Springer (1998). | MR | Zbl

[20] D. Szolnoki, Viability kernels and control sets. ESAIM: COCV 5 (2000) 175-185. | Numdam | MR | Zbl

[21] J.N. Tsitsiklis, Efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 40 (1995) 1528-1538. | MR | Zbl

[22] O. Von Stryk, User's Guide for DIRCOL (Version 2.1): a direct collocation method for the numerical solution of optimal control problems. TU Darmstadt (2000).

Cité par Sources :