Towards optimal space-time discretization for reachable sets of nonlinear control systems

Janosch Rieger; Kyria Wawryk

doi:10.3934/jcd.2023013

Article Contents

2024, Volume 11, Issue 2: 153-173. Doi: 10.3934/jcd.2023013

This issue Previous Article Conservative integrators for piecewise smooth systems with transversal dynamics Next Article Stability analysis of time–varying perturbed descriptor systems

Towards optimal space-time discretization for reachable sets of nonlinear control systems

Janosch Rieger and
Kyria Wawryk^,

Monash University, Australia

^*Corresponding author: Kyria Wawryk
^*Corresponding author: Kyria Wawryk

Received: August 2023

Revised: November 2023

Early access: December 2023

Published: April 2024

Abstract / Introduction Full Text(HTML) Figure(6) / Table(3) Related Papers Cited by

Abstract

Reachable sets of nonlinear control systems can in general only be approximated numerically, and these approximations are typically very expensive to compute. In this paper, we explore a strategy for choosing the temporal and spatial discretizations of Euler's method for reachable set computation in a non-uniform way to improve the performance of the method.

Keywords:

Mathematics Subject Classification: 93B03, 65L50.

Citation:

FullText(HTML)

Figure 1. Step-sizes for system (42) with parameters (44). Discretization produced by Algorithm 1 shown in the dashed line, and Algorithm 2 in the solid line

Download: Full-size image PowerPoint slide

Figure 2. Cumulative contributions $ \sigma_E $ (dashed line) and $ \sigma_C $ (solid line) from (45) and (46) for system (42) with parameters (44)

Download: Full-size image PowerPoint slide

Figure 3. Relative error $ \delta_C $ from (47) plotted against error $ E $ from (5) when Algorithm 2 is applied to system (42). Values for $ L = 1, 2, 3, 4 $ marked using circles, squares, triangles and diamonds, respectively

Download: Full-size image PowerPoint slide

Figure 4. Reachable sets generated by Algorithm 2 applied to system (48) with $ \varepsilon_{\ell_{max}} = 2^{-7} $. Resolution adjusted for printing purposes

Download: Full-size image PowerPoint slide

Figure 5. Stepsizes for system (48) with $ \varepsilon = 2^{-7} $. Discretization produced by Algorithm 1 shown in the dashed line, and Algorithm 2 in the solid line

Download: Full-size image PowerPoint slide

Figure 6. Cumulative contributions $ \sigma_E $ (dashed line) and $ \sigma_C $ (solid line) from (45) and (46) for system (48) with $ \varepsilon = 2^{-7} $

Download: Full-size image PowerPoint slide

Table 1. Time to run Algorithm 2 for system (42) with parameters (44) and $ \ell_{\max} = 15 $ split based on use

$ \boldsymbol{\ell} $	11	12	13	14	15
$ \varepsilon_\ell $	6.4E1	3.2E1	1.6E1	8.0E0	4.0E0
time [s] for reachable set computation (lines 5-17)	4.4E-1	2.7E0	7.0E1	2.8E3	2.4E5
time [s] for refinement of discretization (lines 19-26)	7.0E-4	1.4E-3	4.3E-3	1.4E-2	8.0E-2

| Show Table

DownLoad: CSV

Table 2. Number of grid points computed by Algorithms 1 and 2 to achieve error tolerance (5) when applied to system (42). The high complexity of Algorithm 1 forced us to infer the values in the cells coloured in red using a workaround

L=1	$ \boldsymbol{ \varepsilon} $	2.50E-1	1.25E-1	6.25E-2	3.13E-2	1.56E-2
d=1	Alg1	5.8E3	8.3E4	1.2E6	2.0E7	3.1E8
d=1	Alg2	1.7E3	1.9E4	2.5E5	3.6E6	5.4E7
d=2	Alg1	2.7E6	2.8E8	3.3E10	4.1E12	5.1E14
d=2	Alg2	1.1E5	6.2E6	5.5E8	5.7E10	6.6E12

L=2	$\varepsilon $	2.00E0	1.00E0	5.00E-1	2.50E-1	1.25E-1
d=1	Alg1	1.8E6	2.9E7	4.7E8	7.6E9	1.2E11
d=1	Alg2	4.1E3	5.0E4	6.1E5	8.7E6	1.3E8
d=2	Alg1	1.7E11	2.3E13	3.1E15	4.0E17	5.1E19
d=2	Alg2	2.5E5	1.7E7	1.4E9	1.4E11	1.5E13

L=3	$ \varepsilon $	1.60E1	8.00E0	4.00E0	2.00E0	1.00E0
d=1	Alg1	9.4E7	1.6E9	2.6E10	4.3E11	6.9E12
d=1	Alg2	2.6E3	2.9E4	3.3E5	4.2E6	5.8E7
d=2	Alg1	4.2E14	6.1E16	8.4E18	1.1E21	1.5E23
d=2	Alg2	1.5E5	3.9E6	2.8E8	2.3E10	2.2E12

L=4	$ \varepsilon $	6.40E1	3.20E1	1.60E1	8.00E0	4.00E0
d=1	Alg1	3.8E10	6.4E11	1.0E13	1.7E14	2.7E15
d=1	Alg2	1.2E4	1.1E5	1.2E6	1.5E7	2.1E8
d=2	Alg1	3.5E19	4.9E21	6.6E23	8.7E25	1.1E28
d=2	Alg2	6.6E5	2.8E7	1.7E9	1.3E11	1.3E13

| Show Table

DownLoad: CSV

Table 3. Number of grid points computed by Algorithms 1 and 2 to achieve error tolerance $ \varepsilon $ for system (48)

$ \boldsymbol{ \varepsilon} $	1.25E-1	6.25E-2	3.13E-2	1.56E-2	7.81E-3
Algorithm 1	7.8E5	3.3E7	1.9E9	1.1E11	7.0E12
Algorithm 2	9.6E4	4.8E6	1.6E8	8.4E9	4.6E11

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	T. Alamo, J. Bravo and E. Camacho, Guaranteed state estimation by zonotopes, Automatica J. IFAC, 41 (2005), 1035-1043. doi: 10.1016/j.automatica.2004.12.008.
[2]	M. Althoff, O. Stursberg and M. Buss, Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization, Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 4042-4048. doi: 10.1109/CDC.2008.4738704.
[3]	M. Althoff, O. Stursberg and M. Buss, Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes, Nonlinear Analysis: Hybrid Systems, 4 (2010), 233-249. doi: 10.1016/j.nahs.2009.03.009.
[4]	J.-P. Aubin and A. Cellina, Differential Inclusions, Grundlehren Math. Wiss., 264. Springer-Verlag Berlin, Heidelberg, 1984. doi: 10.1007/978-3-642-69512-4.
[5]	R. Baier, Mengenwertige Integration und Die Diskrete Approximation Erreichbarer Mengen [Set-Valued Integration and the Discrete Approximation of Attainable Sets], PhD thesis, Universität Bayreuth, 1995.
[6]	R. Baier, C. Büskens, I. Chahma and M. Gerdts, Approximation of reachable sets by direct solution methods for optimal control problems, Optim. Methods Softw., 22 (2007), 433-452. doi: 10.1080/10556780600604999.
[7]	R. Baier, I. 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, M. Gerdts and I. Xausa, Approximation of reachable sets using optimal control algorithms, Numer. Algebra Control Optim., 3 (2013), 519-548. doi: 10.3934/naco.2013.3.519.
[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, Discrete Contin. Dyn. Syst. Ser. B, 14 (2010), 409-428. doi: 10.3934/dcdsb.2010.14.409.
[11]	R. Colombo, T. Lorenz and N. Pogodaev, On the modeling of moving populations through set evolution equations, Discrete Contin. Dyn. Syst., 35 (2015), 73-98. doi: 10.3934/dcds.2015.35.73.
[12]	R. Colombo and N. Pogodaev, On the control of moving sets: Positive and negative confinement results, SIAM J. Control Optim., 51 (2013), 380-401. doi: 10.1137/12087791X.
[13]	T. Donchev and E. Farkhi, Stability and Euler approximation of one-sided Lipschitz differential inclusions, SIAM J. Control Optim., 36 (1998), 780-796. doi: 10.1137/S0363012995293694.
[14]	A. Dontchev and E. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223.
[15]	M. Gerdts and I. Xausa, Avoidance trajectories using reachable sets and parametric sensitivity analysis, System Modeling and Optimization, IFIP Adv. Inf. Commun. Technol., Springer Berlin Heidelberg, 391 (2013), 491-500. doi: 10.1007/978-3-642-36062-6_49.
[16]	A. Girard, C. Le Guernic and O. Maler, Efficient computation of reachable sets of linear time-invariant systems with inputs, Hybrid Systems: Computation and Control, Lecture Notes in Comput. Sci., 3927 (2006), 257-271. doi: 10.1007/11730637_21.
[17]	E. Goubault and S. Putot, Robust under-approximations and application to reachability of non-linear control systems with disturbances, IEEE Control Systems Letters, 4 (2020), 928-933. doi: 10.1109/LCSYS.2020.2997261.
[18]	N. Kochdumper and M. Althoff, Sparse polynomial zonotopes: A novel set representation for reachability analysis, IEEE Trans. Automat. Control, 66 (2021), 4043-4058. doi: 10.1109/TAC.2020.3024348.
[19]	V. Komarov and K. Pevchikh, A method for the approximation of attainability sets of differential inclusions with given accuracy, Zh. Vychisl. Mat. i Mat. Fiz., 31 (1991), 153-157.
[20]	E. Lakatos and M. P. H. Stumpf, Control mechanisms for stochastic biochemical systems via computation of reachable sets, R. Soc. open sci., 4 (2017), 160790, 14 pp. doi: 10.1098/rsos.160790.
[21]	Y. Meng, Z. Qiu, M. Waez and C. Fan, Case studies for computing density of reachable states for safe autonomous motion planning, NASA Formal Methods: 14th International Symposium, (2022), 251-271. doi: 10.1007/978-3-031-06773-0_13.
[22]	B. Mordukhovich and Y. Tian, Implicit Euler approximation and optimization of one-sided Lipschitzian differential inclusions, Nonlinear Analysis and Optimization, Contemp. Math., Amer. Math. Soc., Providence, RI, 659 (2016), 165-188. doi: 10.1090/conm/659/13152.
[23]	F. Parise, M. Valcher and J. Lygeros, Computing the projected reachable set of stochastic biochemical reaction networks modeled by switched affine systems, IEEE Trans. Automat. Control, 63 (2018), 3719-3734. doi: 10.1109/TAC.2018.2798800.
[24]	W. Riedl, R. Baier and M. Gerdts, Optimization-based subdivision algorithm for reachable sets, J. Comput. Dyn., 8 (2021), 99-130. doi: 10.3934/jcd.2021005.
[25]	J. Rieger, Semi-implicit euler schemes for ordinary differential inclusions, SIAM Journal on Numerical Analysis, 52 (2014), 895-914. doi: 10.1137/110842727.
[26]	J. Rieger, Robust boundary tracking for reachable sets of nonlinear differential inclusions, Found. Comput. Math., 15 (2015), 1129-1150. doi: 10.1007/s10208-014-9218-8.
[27]	J. Rieger, The Euler scheme for state constrained ordinary differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 21 (2016), 2729-2744. doi: 10.3934/dcdsb.2016070.
[28]	M. Rungger and M. Zamani, Accurate reachability analysis of uncertain nonlinear systems, Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control, (2018), 61-70. doi: 10.1145/3178126.3178127.
[29]	M. Sandberg, Convergence of the forward euler method for nonconvex differential inclusions, SIAM Journal on Numerical Analysis, 47 (2008), 308-320. doi: 10.1137/070686093.
[30]	M. Serry and G. Reissig, Overapproximating reachable tubes of linear time-varying systems, IEEE Trans. Automat. Control, 67 (2022), 443-450. doi: 10.1109/TAC.2021.3057504.
[31]	L. Shao, F. Zhao and Y. Cong, Approximation of convex bodies by multiple objective optimization and an application in reachable sets, Optimization, 67 (2018), 783-796. doi: 10.1080/02331934.2018.1426583.
[32]	G. Smirnov, Introduction to the Theory of Differential Inclusions, Grad. Stud. Math., 41. American Mathematical Society, Providence, RI, 2002. doi: 10.1090/gsm/041.
[33]	V. Veliov, Discrete approximations of integrals of multivalued mappings, C. R. Acad. Bulgare Sci., 42 (1989), 51-54.
[34]	V. 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.
[35]	V. Veliov, On the time-discretization of control systems, SIAM J. Control Optim., 35 (1997), 1470-1486. doi: 10.1137/S0363012995288987.