×

A set oriented approach to global optimal control. (English) Zbl 1072.49014

Summary: 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.

MSC:

49J53 Set-valued and variational analysis
49M25 Discrete approximations in optimal control
90C39 Dynamic programming
65K10 Numerical optimization and variational techniques

Software:

NPSOL; GAIO; DIRCOL
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[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 0928.93024 · Zbl 0928.93024
[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 0963.93059 · Zbl 0963.93059
[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 0995.49021 · Zbl 0995.49021
[5] T.H. Cormen , C.E. Leierson and R.L. Rivest , Introduction to Algorithms . Cambridge, Mass. MIT Press, New York McGraw-Hill ( 1990 ). MR 1066870 | Zbl 1047.68161 · Zbl 1047.68161
[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 1427710 | Zbl 0883.65060 · Zbl 0883.65060 · doi:10.1007/s002110050240
[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 0998.65126 · Zbl 0998.65126
[8] E.W. Dijkstra , A Note on Two Problems in Connection with Graphs . Numer. Math. 5 ( 1959 ) 269 - 271 . Article | MR 107609 | Zbl 0092.16002 · Zbl 0092.16002 · doi:10.1007/BF01386390
[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 1862915 | Zbl 1091.65511 · Zbl 1091.65511 · doi:10.1142/S0218127401003516
[11] L. Grüne , An Adaptive Grid Scheme for the discrete Hamilton-Jacobi-Bellman Equation . Numer. Math. 75 ( 1997 ) 319 - 337 . MR 1427711 | Zbl 0880.65045 · Zbl 0880.65045 · doi:10.1007/s002110050241
[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 1833035 | Zbl 1009.93028 · Zbl 1009.93028 · doi:10.1109/9.920800
[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 1870259 | Zbl 0963.65536 · Zbl 0963.65536
[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 1605994 | Zbl 1032.49037 · Zbl 1032.49037 · doi:10.1109/9.661081
[17] K. Schiele , On the stabilization of a parametrically driven inverted double pendulum . Z. Angew. Math. Mech. 77 ( 1997 ) 143 - 146 . MR 1442705 | Zbl 0886.70015 · Zbl 0886.70015 · doi:10.1002/zamm.19970770212
[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 1854545 | Zbl 1002.65112 · Zbl 1002.65112 · doi:10.1073/pnas.201222998
[19] E.D. Sontag , Mathematical Control Theory: Deterministic Finite Dimensional Systems , Texts in Applied Mathematics 6, Springer ( 1998 ). MR 1640001 | Zbl 0945.93001 · Zbl 0945.93001
[20] D. Szolnoki , Viability kernels and control sets . ESAIM: COCV 5 ( 2000 ) 175 - 185 . Numdam | MR 1744611 | Zbl 0940.93009 · Zbl 0940.93009 · doi:10.1051/cocv:2000106
[21] J.N. Tsitsiklis , Efficient algorithms for globally optimal trajectories . IEEE Trans. Automat. Control 40 ( 1995 ) 1528 - 1538 . MR 1347833 | Zbl 0831.93028 · Zbl 0831.93028 · doi:10.1109/9.412624
[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 ).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.