Construction of the minimum time function for linear systems via higher-order set-valued methods. (English) Zbl 1425.93030

Baier, Robert; Le, Thuy T. T.

Math. Control Relat. Fields 9, No. 2, 223-255 (2019).

Summary: The paper is devoted to introducing an approach to compute the approximate minimum time function of control problems which is based on reachable set approximation and uses arithmetic operations for convex compact sets. In particular, in this paper the theoretical justification of the proposed approach is restricted to a class of linear control systems. The error estimate of the fully discrete reachable set is provided by employing the Hausdorff distance to the continuous-time reachable set. The detailed procedure solving the corresponding discrete set-valued problem is described. Under standard assumptions, by means of convex analysis and knowledge of the regularity of the true minimum time function, we estimate the error of its approximation. Higher-order discretization of the reachable set of the linear control problem can balance missing regularity (e.g., if only Hölder continuity holds) of the minimum time function for smoother problems. To illustrate the error estimates and to demonstrate differences to other numerical approaches we provide a collection of numerical examples which either allow higher order of convergence with respect to time discretization or where the continuity of the minimum time function cannot be sufficiently granted, i.e., we study cases in which the minimum time function is Hölder continuous or even discontinuous.

MSC:

93B03	Attainable sets, reachability
93C05	Linear systems in control theory

Keywords:

minimum time function; reachable sets; linear control problems; higher-order set-valued methods; direct discretization methods

References:

[1]	W. Alt; R. Baier; M. Gerdts; F. Lempio, Approximations of linear control problems with bang-bang solutions, Optimization, 62, 9-32 (2013) · Zbl 1263.49028 · doi:10.1080/02331934.2011.568619
[2]	M. Althoff, Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, PhD thesis, Fakultät für Elektrotechnik und Informationstechnik, Technische Universität München, Munich, Germany, 2010, 221 S.
[3]	J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, Viability Theory. New Directions, 2nd edition, Springer, Heidelberg, 2011. · Zbl 1238.93001
[4]	J.-P. Aubin and A. Cellina, Differential Inclusions, vol. 264 of Grundlehren der mathematischen Wissenschaften, Springer-Verlag, Berlin-Heidelberg-New York-Tokyo, 1984. · Zbl 0538.34007
[5]	R. J. Aumann, Integrals of set-valued functions, J. Math. Anal. Appl., 12, 1-12 (1965) · Zbl 0163.06301 · doi:10.1016/0022-247X(65)90049-1
[6]	R. Baier, Mengenwertige Integration und die diskrete Approximation erreichbarer Mengen, [Set-valued Integration and the Discrete Approximation of Reachable Sets], PhD thesis, Universität Bayreuth, 1994. · Zbl 0841.65013
[7]	R. Baier, Selection strategies for set-valued Runge-Kutta methods, in Numerical Analysis and Its Applications, Third International Conference, NAA 2004, Rousse, Bulgaria, June 29 - July 3, 2004, Revised Selected Papers (eds. Z. Li, L. G. Vulkov and J. Wasniewski), vol. 3401 of Lecture Notes in Comput. Sci., Springer, Berlin-Heidelberg, 2005, 149-157. · Zbl 1118.65342
[8]	R. Baier; C. Büskens; I. A. Chahma; M. Gerdts, Approximation of reachable sets by direct solution methods of optimal control problems, Optim. Methods Softw., 22, 433-452 (2007) · Zbl 1129.93003 · doi:10.1080/10556780600604999
[9]	R. Baier and F. Lempio, Approximating reachable sets by extrapolation methods, in Curves and Surfaces in Geometric Design. Papers from the Second International Conference on Curves and Surfaces, held in Chamonix-Mont-Blanc, France, July 10-16, 1993 (eds. P. J. Laurent, A. L. Méhauteé and L. L. Schumaker), A K Peters, Wellesley, 1994, 9-18. · Zbl 0813.65099
[10]	R. Baier and T. T. T. Le, Construction of the minimum time function via reachable sets of linear control systems. Part 1: error estimates, part 2: numerical computations, preprint, Dec 2015. arXiv: 1512.08630 and arXiv: 1512.08617.
[11]	R. Baier and F. Lempio, Computing Aumann’s integral, in Modeling Techniques for Uncertain Systems, Proceedings of a Conference held in Sopron, Hungary, July 6-10, 1992 (eds. A. B. Kurzhanski and V. M. Veliov), vol. 18 of Progress in Systems and Control Theory, Birkhäuser, Basel, 1994, 71-92. · Zbl 0828.65021
[12]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1997, with appendices by Maurizio Falcone and Pierpaolo Soravia. · Zbl 0890.49011
[13]	M. Bardi; M. Falcone, An approximation scheme for the minimum time function, SIAM J. Control Optim., 28, 950-965 (1990) · Zbl 0723.49024 · doi:10.1137/0328053
[14]	M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories, in Analysis and Optimization of Systems. Proceedings of the 9th International Conference Antibes, June 12-15, 1990 (eds. A. Bensoussan and J. L. Lions), vol. 144 of Lecture Notes in Control and Inform. Sci., Springer, Berlin-Heidelberg, 1990, 103-112. · Zbl 0708.49012
[15]	M. Bardi, M. Falcone and P. Soravia, Numerical methods for pursuit-evasion games via viscosity solutions, in Stochastic and Differential Games, vol. 4 of Ann. Internat. Soc. Dynam. Games, Birkhäuser Boston, Boston, MA, 1999, 105-175. · Zbl 1018.49027
[16]	O. Bokanowski; A. Briani; H. Zidani, Minimum time control problems for non-autonomous differential equations, Systems Control Lett., 58, 742-746 (2009) · Zbl 1181.49034 · doi:10.1016/j.sysconle.2009.08.003
[17]	O. Bokanowski; N. Forcadel; H. Zidani, Reachability and minimal times for state constrained nonlinear problems without any controllability assumption, SIAM J. Control Optim., 48, 4292-4316 (2010) · Zbl 1214.49025 · doi:10.1137/090762075
[18]	F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer-Verlag, New York, 1998. · Zbl 1047.49500
[19]	G. Colombo; T. T. T. Le, Higher order discrete controllability and the approximation of the minimum time function, Discrete Contin. Dyn. Syst., 35, 4293-4322 (2015) · Zbl 1338.49059 · doi:10.3934/dcds.2015.35.4293
[20]	G. Colombo; A. Marigonda; P. R. Wolenski, Some new regularity properties for the minimal time function, SIAM J. Control Optim., 44, 2285-2299 (2006) · Zbl 1126.49032 · doi:10.1137/050630076
[21]	G. Colombo; K. T. Nguyen; L. V. Nguyen, Non-Lipschitz points and the SBV regularity of the minimum time function, Calc. Var. Partial Differential Equations, 51, 439-463 (2014) · Zbl 1297.49065 · doi:10.1007/s00526-013-0682-9
[22]	B. D. Doitchinov; V. M. Veliov, Parametrizations of integrals of set-valued mappings and applications, J. Math. Anal. Appl., 179, 483-499 (1993) · Zbl 0862.28011 · doi:10.1006/jmaa.1993.1363
[23]	T. D. Donchev; E. M. Farkhi, Moduli of smoothness of vector valued functions of a real variable and applications, Numer. Funct. Anal. Optim., 11, 497-509 (1990) · Zbl 0699.65039 · doi:10.1080/01630569008816385
[24]	A. L. Dontchev; E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41, 349-358 (1989) · Zbl 0667.65067 · doi:10.1007/BF02241223
[25]	M. Falcone, Numerical Solution of Dynamic Programming Equations. Appendix A, in Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations (eds. M. Bardi and I. Capuzzo-Dolcetta), Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1997, 471-504. · Zbl 0890.49011
[26]	M. Gerdts, Optimal control of ODEs and DAEs, de Gruyter Textbook, Walter de Gruyter & Co., Berlin, 2012. · Zbl 1275.49001
[27]	A. Girard, C. Le Guernic and O. Maler, Efficient computation of reachable sets of linear time-invariant systems with inputs, in Hybrid Systems: Computation and Control, vol. 3927 of Lecture Notes in Comput. Sci., Springer, Berlin, 2006, 257-271. · Zbl 1178.93024
[28]	L. Grüne; T. T. T. Le, A double-sided dynamic programming approach to the minimum time problem and its numerical approximation, Applied Numerical Mathematics, 121, 68-81 (2017) · Zbl 1372.65193 · doi:10.1016/j.apnum.2017.06.008
[29]	H. Hermes and J. LaSalle, Functional Analysis and Time Optimal Control, vol. 56 of Mathematics in science and engineering, Academic Press, New York, 1969. · Zbl 0203.47504
[30]	A. B. Kurzhanski and P. Varaiya, Dynamics and Control of Trajectory Tubes. Theory and Computation, Systems & Control: Foundations & Applications, Springer, Cham-Heidelberg-New York-Dordrecht-London, 2014. · Zbl 1336.93004
[31]	T. T. T. Le, Results on Controllability and Numerical Approximation of the Minimum Time Function, PhD thesis, Dipartimento di Matematica, Padova, Italy, 2016.
[32]	C. Le Guernic, Reachability Analysis of Hybrid Systems with Linear Continuous Dynamics, PhD thesis, École Doctorale Mathématiques, Sciences et Technologies de l’Information, Informatique, Grenoble, France, 2009, 169 pages. · Zbl 1242.93059
[33]	E. Lee and L. Markus, Foundations of Optimal Control Theory, SIAM Series in Applied Mathematics, John Wiley & Sons, Inc., New York-London-Sydney, 1967. · Zbl 0159.13201
[34]	A. Marigonda, Second order conditions for the controllability of nonlinear systems with drift, Commun. Pure Appl. Anal., 5, 861-885 (2006) · Zbl 1175.93038 · doi:10.3934/cpaa.2006.5.861
[35]	D. Pallaschke and R. Urbański, Pairs of Compact Convex Sets, vol. 548 of Mathematics and Its Applications, Kluwer Academic Publishers, Dordrecht, 2002. · Zbl 1025.52003
[36]	N. N. Petrov, On the Bellman function for the time-optimality process problem, Prikl. Mat. Meh., 34, 820-826 (1970) · Zbl 0253.49012
[37]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, vol. 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer Science & Business Media, Berlin, 2009.
[38]	P. Saint-Pierre, Approximation of the viability kernel, Appl. Math. Optim., 29, 187-209 (1994) · Zbl 0790.65081 · doi:10.1007/BF01204182
[39]	A. Tolstonogov, Differential Inclusions in a Banach Space, vol. 524 of Mathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 2000, translated from the 1986 Russian original and revised by the author. · Zbl 1021.34002
[40]	V. M. Veliov, Discrete approximations of integrals of multivalued mappings, C. R. Acad. Bulgare Sci., 42, 51-54 (1989) · Zbl 0697.41019
[41]	V. M. Veliov, Second order discrete approximation to linear differential inclusions, SIAM J. Numer. Anal., 29, 439-451 (1992) · Zbl 0754.65070 · doi:10.1137/0729026
[42]	M. D. Wills, Hausdorff distance and convex sets, J. Convex Anal., 14, 109-117 (2007) · Zbl 1134.46006
[43]	P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28, 1148-1161 (1990) · Zbl 0736.34015 · doi:10.1137/0328062