ESAIM: Control, Optimisation and Calculus of Variations

Table of Contents - April 2004 - Volume 10 - Issue02

Research Article

A set oriented approach to global optimal control

Junge, Olivera1 and Osinga, Hinke M.a2

a1 Institute for Mathematics, University of Paderborn, 33095 Paderborn, Germany; junge@upb.de.

a2 Engineering Mathematics, University of Bristol, Bristol BS8 1TR, UK; H.M.Osinga@bristol.ac.uk.

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.

(Received July 22 2003)

(Revised October 30 2003)

(Online publication March 15 2004)

Key Words:

  • Global optimal control;
  • value function;
  • set oriented method;
  • shortest path.

Mathematics Subject Classification:

  • 49J53;
  • 49M25;
  • 65K10;
  • 90C39
  • [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. [Google Scholar]
  • [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. [Google Scholar]
  • [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. [Google Scholar]
  • [5] T.H. Cormen, C.E. Leierson and R.L. Rivest, Introduction to Algorithms. Cambridge, Mass. MIT Press, New York McGraw-Hill (1990). [Google Scholar]
  • [6] M. Dellnitz and A. Hohmann , A subdivision algorithm for the computation of unstable manifolds and global attractors. Numer. Math. 75 (1997) 293-317. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [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. [Google Scholar]
  • [8] E.W. Dijkstra , A Note on Two Problems in Connection with Graphs. Numer. Math. 5 (1959) 269-271. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [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). [Google Scholar]
  • [10] Z. Galias , Interval methods for rigorous investigations of periodic orbits. Int. J. Bifur. Chaos 11 (2001) 2427-2450. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [11] L. Grüne , An Adaptive Grid Scheme for the discrete Hamilton-Jacobi-Bellman Equation. Numer. Math. 75 (1997) 319-337. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [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. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [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.
  • [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. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [17] K. Schiele , On the stabilization of a parametrically driven inverted double pendulum. Z. Angew. Math. Mech. 77 (1997) 143-146. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [18] J.A. Sethian and A. Vladimirsky , Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Nat. Acad. Sci. USA 98 (2001) 11069-11074. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [19] E.D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, Texts in Applied Mathematics 6, Springer (1998).
  • [20] D. Szolnoki , Viability kernels and control sets. ESAIM: COCV 5 (2000) 175-185. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [21] J.N. Tsitsiklis , Efficient algorithms for globally optimal trajectories. IEEE Trans. Automat. Control 40 (1995) 1528-1538. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • [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).