A set oriented approach to global optimal control

Oliver Junge; Hinke M. Osinga

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

  • Volume: 10, Issue: 2, page 259-270
  • ISSN: 1292-8119

Abstract

top
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.

How to cite

top

Junge, Oliver, and Osinga, Hinke M.. "A set oriented approach to global optimal control." ESAIM: Control, Optimisation and Calculus of Variations 10.2 (2004): 259-270. <http://eudml.org/doc/245320>.

@article{Junge2004,
abstract = {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.},
author = {Junge, Oliver, Osinga, Hinke M.},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
keywords = {global optimal control; value function; set oriented method; shortest path},
language = {eng},
number = {2},
pages = {259-270},
publisher = {EDP-Sciences},
title = {A set oriented approach to global optimal control},
url = {http://eudml.org/doc/245320},
volume = {10},
year = {2004},
}

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
PB - EDP-Sciences
VL - 10
IS - 2
SP - 259
EP - 270
AB - 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.
LA - eng
KW - global optimal control; value function; set oriented method; shortest path
UR - http://eudml.org/doc/245320
ER -

References

top
  1. [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. [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. Zbl0928.93024
  3. [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. Zbl0963.93059
  4. [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. Zbl0995.49021
  5. [5] T.H. Cormen, C.E. Leierson and R.L. Rivest, Introduction to Algorithms. Cambridge, Mass. MIT Press, New York McGraw-Hill (1990). Zbl1047.68161MR1066870
  6. [6] M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors. Numer. Math. 75 (1997) 293-317. Zbl0883.65060MR1427710
  7. [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. Zbl0998.65126
  8. [8] E.W. Dijkstra, A Note on Two Problems in Connection with Graphs. Numer. Math. 5 (1959) 269-271. Zbl0092.16002MR107609
  9. [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. [10] Z. Galias, Interval methods for rigorous investigations of periodic orbits. Int. J. Bifur. Chaos 11 (2001) 2427-2450. Zbl1091.65511MR1862915
  11. [11] L. Grüne, An Adaptive Grid Scheme for the discrete Hamilton-Jacobi-Bellman Equation. Numer. Math. 75 (1997) 319-337. Zbl0880.65045MR1427711
  12. [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. [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. [14] A. Jadbabaie, J. Yu and J. Hauser, Unconstrained receding horizon control of nonlinear systems. IEEE Trans. Automat. Control 46 (2001) 776-783. Zbl1009.93028MR1833035
  15. [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. Zbl0963.65536MR1870259
  16. [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. Zbl1032.49037MR1605994
  17. [17] K. Schiele, On the stabilization of a parametrically driven inverted double pendulum. Z. Angew. Math. Mech. 77 (1997) 143-146. Zbl0886.70015MR1442705
  18. [18] J.A. Sethian and A. Vladimirsky, Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Nat. Acad. Sci. USA 98 (2001) 11069-11074. Zbl1002.65112MR1854545
  19. [19] E.D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, Texts in Applied Mathematics 6, Springer (1998). Zbl0945.93001MR1640001
  20. [20] D. Szolnoki, Viability kernels and control sets. ESAIM: COCV 5 (2000) 175-185. Zbl0940.93009MR1744611
  21. [21] J.N. Tsitsiklis, Efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 40 (1995) 1528-1538. Zbl0831.93028MR1347833
  22. [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). 

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.