Approximation of reachable sets using optimal control algorithms

Robert Baier; Matthias Gerdts; Ilaria Xausa

doi:10.3934/naco.2013.3.519

Article Contents

2013, Volume 3, Issue 3: 519-548. Doi: 10.3934/naco.2013.3.519

This issue Previous Article Deflating irreducible singular M-matrix algebraic Riccati equations Next Article Another note on some quadrature based three-step iterative methods for non-linear equations

Approximation of reachable sets using optimal control algorithms

1.
Applied Mathematics, Department of Mathematics, University of Bayreuth, 95440 Bayreuth
2.
Institute of Mathematics and Applied Computing (LRT), University of the Federal Armed Forces at Munich, Werner-Heisenberg-Weg 39, 85577 Neubiberg

Received: October 2011

Revised: February 2013

Published: July 2013

Abstract / Introduction Related Papers Cited by

Abstract

We investigate and analyze a computational method for the approximation of reachable sets for nonlinear dynamic systems. The method uses grids to cover the region of interest and the distance function to the reachable set evaluated at grid points. A convergence analysis is provided and shows the convergence of three different types of discrete set approximations to the reachable set. The distance functions can be computed numerically by suitable optimal control problems in combination with direct discretization techniques which allows adaptive calculations of reachable sets. Several numerical examples with nonconvex reachable sets are presented.

Keywords:

Mathematics Subject Classification: Primary: 49J15, 49M25, 93B03, 93C10; Secondary: 90C30.

Citation:

Related Papers

Cited by

References

[1]	H. Attouch and R. J.-B. Wets, Isometries for the Legendre-Fenchel transform, Trans. Amer. Math. Soc., 296 (1986), 33-60.doi: 10.1090/S0002-9947-1986-0837797-X.
[2]	J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, "Viability Theory. New Directions," Second edition, Springer, Heidelberg, 2011.doi: 10.1007/978-3-642-16684-6.
[3]	J.-P. Aubin, T. Bernado and P. Saint-Pierre, A viability approach to global climate change issues, in "The Coupling of Climate and Economic Dynamics. Essays on Integrated Assessment" (eds. A. Haurie and L. Viguier), volume 22 of "Advances in Global Change Research," Springer, Dordrecht-Berlin-Heidelberg-New York, (2005), 113-143.
[4]	R. Baier, "Mengenwertige Integration und die diskrete Approximation erreichbarer Mengen," Bayreuth. Math. Schr., 50 (1995).
[5]	R. Baier, Selection strategies for set-valued Runge-Kutta methods, in "Numerical Analysis and Its Applications" (eds. Z. Li, L. G. Vulkov, and J. Wasniewski), Third International Conference, NAA 2004, Rousse, Bulgaria, June 29 - July 3, 2004, Revised Selected Papers, volume 3401 of "Lecture Notes in Computer Science," Springer, Berlin-Heidelberg, (2005), 149-157.
[6]	R. Baier, Ch. Büskens, I. A. Chahma and M. Gerdts, Approximation of reachable sets by direct solution methods of optimal control problems, Optim. Methods Softw., 22 (2007), 433-452.doi: 10.1080/10556780600604999.
[7]	R. Baier, I. A. Chahma and F. Lempio, Stability and convergence of Euler's method for state-constrained differential inclusions, SIAM J. Optim., 18 (2007), 1004-1026.doi: 10.1137/060661867.
[8]	R. Baier and M. Gerdts, A computational method for non-convex reachable sets using optimal control, in "Proceedings of the European Control Conference (ECC) 2009, Budapest (Hungary), August 23-26, 2009," EUCA, Budapest, (2009), 97-102.
[9]	W.-J. Beyn and J. Rieger, Numerical fixed grid methods for differential inclusions, Computing, 81 (2007), 91-106.doi: 10.1007/s00607-007-0240-4.
[10]	W.-J. Beyn and J. Rieger, The implicit Euler scheme for one-sided Lipschitz differential inclusions, Dyn. Contin. Discrete Impuls. Syst. Ser. B Appl. Algorithms, 14 (2010), 409-428.doi: 10.3934/dcdsb.2010.14.409.
[11]	H. G. Bock, "Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen," Bonner Mathematische Schriften, 183 (1987).
[12]	O. Bokanowski, N. Forcadel and H. Zidani, Reachability and minimal times for state constrained nonlinear problems without any controllability assumption, SIAM J. Control Optim., 48 (2010), 4292-4316.doi: 10.1137/090762075.
[13]	O. Bokanowski, A. Désilles, and H. Zidani, HJB approach for motion planning and reachabilty analysis, in "Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools, VALUETOOLS'11," ICST, Brussels, Belgium, (2011), 28-36.
[14]	N. Bonneuil, Computing the viability kernel in large state dimension, J. Math. Anal. Appl., 323 (2006), 1444-1454.doi: 10.1016/j.jmaa.2005.11.076.
[15]	N. Bonneuil, Maximum under continuous-discrete-time dynamic with target and viability constraints, Optimization, 61 (2012), 901-913.doi: 10.1080/02331934.2011.605127.
[16]	Y. Cao, S. Li, L. R. Petzold and R. Serban, Adjoint sensitivity analysis for differential-algebraic equations: the adjoint DAE system and its numerical solution, SIAM J. Sci. Comput., 24 (2003), 1076-1089.doi: 10.1137/S1064827501380630.
[17]	M. Caracotsios and W. E. Stewart, Sensitivity analysis of initial-boundary-value problems with mixed PDEs and algebraic equations, Computers chem. Engng., 19 (1985), 1019-1030.
[18]	I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-162.
[19]	F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, "Nonsmooth Analysis and Control Theory," Graduate Texts in Mathematics, Springer-Verlag, New York, 178 (1998).
[20]	D. Cohen-Or, D. Levin and A. Solomovici, Three-dimensional distance field metamorphosis, ACM Trans. Graph., 17 (1998), 116-141.
[21]	E. Crück, A. Désilles and H. Zidani, Collision analysis for an UAV, in "AIAA Guidance, Navigation, and Control Conference 2012," (GNC-12) Minneapolis, Minnesota, American Institute of Aeronautics and Astronautics, (August 2012), 20 pages.
[22]	M. C. Delfour and J.-P. Zolésio, "Shapes and Geometries. Metrics, Analysis, Differential Calculus, and Optimization,'' Second edition, volume 22 of "Advances in Design and Control,'' Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2011.
[23]	M. Dellnitz and O. Junge, Set oriented numerical methods for dynamical systems, in "Handbook of Dynamical Systems," North-Holland, Amsterdam, 2 (2002), 221-264.
[24]	M. Dellnitz, O. Junge, M. Post and B. Thiere, On target for Venus-set oriented computation of energy efficient low thrust trajectories, Celestial Mech. Dynam. Astronom., 95 (2006), 357-370.
[25]	A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358.
[26]	A. L. Dontchev, W. W. Hager and V. M. Veliov, Second-order Runge-Kutta approximations in control constrained optimal control, SIAM J. Numer. Anal., 38 (2000), 202-226.doi: 10.1137/S0036142999351765.
[27]	W. F. Feehery, J. E. Tolsma and P. I. Barton, Efficient sensitivity analysis of large-scale differential-algebraic systems, Appl. Numer. Math., 25 (1997), 41-54.doi: 10.1016/S0168-9274(97)00050-0.
[28]	T. F. Filippova and E. V. Berezina, On state estimation approaches for uncertain dynamical systems with quadratic nonlinearity: theory and computer simulations, in "Large-Scale Scientific Computing," volume 4818 of "Lecture Notes in Comput. Sci.,'' Springer, Berlin, (2008), 326-333.
[29]	H. Frankowska and F. Rampazzo, Filippov's and Filippov-Wa.zewski's theorems on closed domains, J. Differ. Equ., 161 (2000), 449-478.doi: 10.1006/jdeq.2000.3711.
[30]	J. E. Gayek, Approximating reachable sets for a class of linear control systems, Internat. J. Control, 43 (1986), 441-453.doi: 10.1080/00207178608933477.
[31]	M. Gerdts, "User manual for OCPID-DAE1," User manual, University of the German Federal Armed Forces in Munich, 2010, Available from: http://www.unibw.de/lrt1/gerdts/software/ocpiddae1.pdf.
[32]	M. Gerdts, "Optimal Control of ODEs and DAEs," DeGruyter, Berlin, 2011.
[33]	A. Girard and C. Le Guernic, Zonotope/hyperplane intersection for hybrid systems reachability analysis, in "Hybrid systems: Computation and Control. 11th International Workshop, HSCC 2008, St. Louis, MO, USA, April 22-24, 2008" (eds. M. Egerstedt et al.), volume 4981 of "Lecture Notes in Comput. Sci.," Springer, Berlin, (2008), 215-228.
[34]	A. Griewank, "Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation," volume 19 of "Frontiers in Applied Mathematics,'' SIAM, Philadelphia, 2000.
[35]	L. Grüne, "Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization,'' volume 1783 of "Lecture Notes in Math,'' Springer-Verlag, Berlin, 2002.
[36]	G. Häckl, "Reachable Sets, Control Sets and Their Computation. With a Preface by F. Colonius," volume 7 of "Augsburger Mathematisch-Naturwissenschaftliche Schriften [Augsburg Mathematical-Scientific Texts],'' Dissertation (1995), Dr. Bernd Wiß ner-Verlag, Universität Augsburg, Augsburg, 1996.
[37]	W. W. Hager, Runge-Kutta methods in optimal control and the transformed adjoint system, Numer. Math., 87 (2000), 247-282.doi: 10.1007/s002110000178.
[38]	O. Hájek, "Control Theory in the Plane,'' Second edition, volume 153 of "Lecture Notes in Control and Inform. Sci.,'' Springer, Berlin, 2008.
[39]	H. Hermes and J. P. Lasalle, Functional Analysis and Time Optimal Control, in "Mathematics in Science and Engineering 56," Academic Press, New York-San Francisco-London, (1969).
[40]	P. Kenderov, Dense strong continuity of pointwise continuous mappings, Pacific J. Math., 89 (1980), 111-130.doi: 10.2140/pjm.1980.89.111.
[41]	N. Kirov and M. Krastanov, Volterra series and numerical approximations of ODEs, in "Numerical Analysis and Its Applications" (eds. Z. Li, L. G. Vulkov, and J. Wasniewski), Third International Conference, NAA 2004, Rousse, Bulgaria, June 29 - July 3, 2004, Revised Selected Papers, "Lecture Notes in Comput. Sci.,'' Springer, Berlin-Heidelberg, 3401 (2005), 337-344.
[42]	E. K. Kostousova, State estimation for dynamic systems via parallelotopes: optimization and parallel computations, Optim. Methods Softw., 9 (1998), 269-306.doi: 10.1080/10556789808805696.
[43]	E. K. Kostousova, State estimation for control systems with a multiplicative uncertainty through polyhedral techniques, in "25th Conference on System Modeling and Optimization" (eds. D. Hömberg and F. Tröltzsch), September 12-16, 2011 in Berlin, Springer, (2012), 10 pages.
[44]	M. I. Krastanov and V. M. Veliov, High-order approximations to nonholonomic affine control systems, in "Large-Scale Scientific Computing 7th International Conference," LSSC 2009, Sozopol, Bulgaria, June 4-8, 2009, Revised Papers, volume 5910 of "Lecture Notes in Comput. Sci.,'' Sozopol, Bulgaria, (2010), 294-301.
[45]	A. B. Kurzhanski, I. M. Mitchell and P. Varaiya, Optimization techniques for state-constrained control and obstacle problems, J. Optim. Theory Appl., 128 (2006), 499-521.doi: 10.1007/s10957-006-9029-4.
[46]	A. B. Kurzhanski and P. Varaiya, Ellipsoidal techniques for reachability analysis: internal approximation, Systems Control Lett., 41 (2000), 201-211.doi: 10.1016/S0167-6911(00)00059-1.
[47]	A. B. Kurzhanski and P. Varaiya, Dynamic optimization for reachability problems, J. Optim. Theory Appl., 108 (2001), 227-251.doi: 10.1023/A:1026497115405.
[48]	A. B. Kurzhanski and P. Varaiya, On ellipsoidal techniques for reachability analysis. Part I: external approximations, Optim. Methods Softw., 17 (2002), 177-206.doi: 10.1080/1055678021000012426.
[49]	A. B. Kurzhanski and P. Varaiya, Ellipsoidal techniques for reachability under state constraints, SIAM J. Control Optim., 45 (2006), 1369-1394.doi: 10.1137/S0363012903437605.
[50]	D. Levin, Multidimensional reconstruction by set-valued approximations, IMA J. Numer. Anal., 6 (1986), 173-184.doi: 10.1093/imanum/6.2.173.
[51]	T. Lorenz, Epi-Lipschitzian reachable sets of differential inclusions, Syst. Control Lett., 57 (2008), 703-707.doi: 10.1016/j.sysconle.2008.01.007.
[52]	K. Malanowski, Ch. Büskens, and H. Maurer, Convergence of approximations to nonlinear optimal control problems, in "Mathematical Programming with Data Perturbations'' (ed. A. Fiacco), volume 195, "Lecture Notes in Pure and Appl. Math.,'' Dekker, New York, (1997), 253-284.
[53]	T. Maly and L. R. Petzold, Numerical methods and software for sensitivity analysis of differential-algebraic systems, Appl. Numer. Math., 20 (1996), 57-79.doi: 10.1016/0168-9274(95)00117-4.
[54]	I. M. Mitchell, Comparing forward and backward reachability as tools for safety analysis, in "Hybrid Systems: Computation and Control,'' volume 4416 of "Lecture Notes in Comput. Sci.,'' Springer, Berlin, (2007), 428-443.
[55]	I. M. Mitchell and C. J. Tomlin, Overapproximating reachable sets by Hamilton-Jacobi projections, J. Sci. Comput., 19 (2003), 323-346.doi: 10.1023/A:1025364227563.
[56]	J. Nocedal and S. J. Wright, "Numerical Optimization,'' Springer Series in Operations Research, New York, 1999.doi: 10.1007/b98874.
[57]	A. Pietrus and V. M. Veliov, On the discretization of switched linear systems, System Control Lett., 58 (2009), 395-399.doi: 10.1016/j.sysconle.2009.01.005.
[58]	A. Puri, V. Borkar, and P. Varaiya, $\epsilon$-Approximations of differential inclusions, in "Hybrid Systems III. Verification and Control'' (eds. R. Alur, T. A. Henzinger, and E. D. Sontag), 6th International Conference, NMA 2006 Borovets, Bulgaria, August 20-24, 2006, Revised Papers, volume 1066 of "Lecture Notes in Control and Inform. Sci.,'' Springer, Berlin-Heidelberg-New York, NY, (1996), 362-376.
[59]	M. Quincampoix and V. M. Veliov, Optimal control of uncertain systems with incomplete information for the disturbances, SIAM J. Control Optim., 43 (2004/05), 1373-1399. doi: 10.1137/S0363012903420863.
[60]	J. Rieger, Shadowing and the viability kernel algorithm, Appl. Math. Optim., 60 (2009), 429-441.doi: 10.1007/s00245-009-9083-z.
[61]	R. T. Rockafellar and R. J.-B. Wets, "Variational Analysis,'' volume 317 of "Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences],'' Springer-Verlag, Berlin, 1998.
[62]	P. Saint-Pierre, Approximation of the viability kernel, Appl. Math. Optim., 29 (1994), 187-209.doi: 10.1007/BF01204182.
[63]	M. Sandberg, Convergence of the forward Euler method for nonconvex differential inclusions, SIAM J. Numer. Anal., 47 (2008/09), 308-320. doi: 10.1137/070686093.
[64]	P. Varaiya, Reach set computation using optimal control, in "Verification of Digital and Hybrid Systems" (eds. M. K. Inan and R. P. Kurshan), proceedings of the NATO ASI, Antalya, Turkey, May 26-June 6, 1997, volume 170 of "NATO Sci. Ser. F Comput. Syst. Sci.,'' Springer, Berlin, (2000), 323-331.
[65]	V. M. Veliov, Second order discrete approximations to strongly convex differential inclusions, Systems Control Lett., 13 (1989), 263-269.doi: 10.1016/0167-6911(89)90073-X.
[66]	V. M. Veliov, Second order discrete approximation to linear differential inclusions, SIAM J. Numer. Anal., 29 (1992), 439-451.doi: 10.1137/0729026.
[67]	P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28 (1990), 1148-1161.doi: 10.1137/0328062.