Bracketing backward reach sets of a dynamical system. (English) Zbl 1454.93023

Summary: In this paper, we present a new method for bracketing (i.e. characterising from inside and from outside) backward reach set of the target region \(\mathbb{T}\) of a continuous-time dynamical system. The principle of the method is to formalise the problem as a constraint network, where the variables are the trajectories (or paths) of the system. The resolution is made possible by using mazes which is a set of paths that contain all solutions of the problem. As a result, we will be able to derive a method able to compute a backward reach set for a huge class of systems without any knowledge of a parametric Lyapunov function and without assuming any linearity for our system. The method will be illustrated in several examples.


93B03 Attainable sets, reachability
93B70 Networked control


AQCS; GloptiPoly; Acumen
Full Text: DOI HAL


[1] Araya, I., Trombettoni, G., & Neveu, B. (2012). A contractor based on convex interval Taylor. Proceedings of CPAIOR (pp. 1-16), LNCS 7298. Berlin: Springer.
[2] Asarin, E., Dang, T., & Girard, A. (2003). Reachability analysis of nonlinear systems using conservative approximation. Hybrid systems: Computation and control (pp. 20-35). Berlin: Springer. · Zbl 1032.93034
[3] Asarin, E.; Dang, T.; Girard, A., Hybridization methods for the analysis of non-linear systems, Acta Informatica, 7, 43, 451-476 (2007) · Zbl 1134.93026
[4] Aubin, J., Viability kernels and capture basins of sets under differential inclusions, SIAM Journal on Control and Optimization, 40, 3, 853-881 (2001) · Zbl 1025.49016
[5] Aubin, J.; Frankowska, H., Set-valued analysis (1990), Boston: Birkhäuser, Boston · Zbl 0713.49021
[6] Bacha, A., Jerbi, H., & Braiek, N. (2008). On the estimation of asymptotic stability region of nonlinear polynomial systems: Geometrical approaches. In H. Aschemann (Ed.), New approaches in automation and robotics (pp. 55-72). Vienna: I-Tech Education and Publishing.
[7] Barreiro, A.; Aracil, J.; Pagano, D., Detection of attraction domains of non-linear systems using bifurcation analysis and Lyapunov functions, International Journal of Control, 75, 5, 314-327 (2002) · Zbl 1032.93068
[8] Bayen, A.; Mitchell, I. M.; Osihi, M.; Tomlin, C., Aircraft autolander safety analysis through optimal control-based reach set computation, Journal of Guidance, Control, and Dynamics, 30, 1, 68-77 (2007)
[9] Biemond, J.; Michiels, W., Estimation of basins of attraction for controlled systems with input saturation and time-delays, IFAC Proceedings Volumes, 47, 3, 11006-11011 (2014)
[10] Blanchini, F.; Miani, S., Set-theoretic methods in control (2007), Basel: Springer Science & Business Media, Basel · Zbl 0996.93040
[11] Bouissou, O., Chapoutot, A., Djaballah, A., & Kieffer, M. (2014). Computation of parametric barrier functions for dynamical systems using interval analysis. 2014 IEEE 53rd annual conference on decision and control (CDC) (pp. 753-758). · Zbl 1357.93046
[12] Chabert, G.; Jaulin, L., QUIMPER, a language for quick interval modelling and programming in a bounded-error context, Artificial Intelligence, 173, 1079-1100 (2009) · Zbl 1191.68628
[13] Collins, P.; Goldsztejn, A., The reach-and-evolve algorithm for reachability analysis of nonlinear dynamical systems, Electronic Notes in Theoretical Computer Science, 223, 87-102 (2008) · Zbl 1337.93018
[14] Combastel, C. (2005). A state bounding observer for uncertain non-linear continuous-time systems based on zonotopes. CDC-ECC ’05.
[15] Cousot, P., & Cousot, R. (1977). Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. Conference record of the fourth ACM symposium on principles of programming languages (pp. 238-252), Los Angeles, California.
[16] Delanoue, N., Jaulin, L., & Cottenceau, B. (2006). Attraction domain of a nonlinear system using interval analysis. Twelfth international conference on principles and practice of constraint programming (IntCP 2006), France, Nantes. · Zbl 1087.68068
[17] Desilles, A., Zidani, H., & Cruck, E. (2012). Collision analysis for an UAV. AIAA guidance, navigation, and control conference (pp. 13-16). American Institute of Aeronautics and Astronautics.
[18] Desrochers, B.; Jaulin, L., A minimal contractor for the polar equation: Application to robot localization, Engineering Applications of Artificial Intelligence, 55, 83-92 (2016)
[19] Doyen, L., Henzinger, T., & Raskin, J. (2005). Automatic rectangular refinement of affine hybrid systems. Proceedings of the third international conference on formal modeling and analysis of timed systems (pp. 144-161). Berlin: Springer. · Zbl 1175.68243
[20] Drevelle, V.; Bonnifait, P., Localization confidence domains via set inversion on short-term trajectory, IEEE Transactions on Robotics, 29, 5, 1244-1256 (2013)
[21] Dubins, L. E., On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, American Journal of Mathematics, 79, 3, 497-516 (1957) · Zbl 0098.35401
[22] Esterhuizen, W.; Lévine, J., Barriers and potentially safe sets in hybrid systems: Pendulum with non-rigid cable, Automatica, 73, 248-255 (2016) · Zbl 1371.93092
[23] Gao, Y., Lygeros, J., & Quincampoix, M. (2006). The reachability problem for uncertain hybrid systems revisited: A viability theory perspective. In J. Hespanha & A. Tiwari (Eds.), Hybrid systems: Computation and control (pp. 242-256). Berlin: Springer-Verlag. · Zbl 1178.93073
[24] Girard, A. (2003). Computation and stability analysis of limit cycles in piecewise linear hybrid systems. 1st IFAC conference on analysis and design of hybrid systems (pp. 181-186).
[25] Gonzaga, C.; Jungers, M.; Daafouz, J., Stability analysis and stabilisation of switched nonlinear systems, International Journal of Control, 85, 7, 822-829 (2012) · Zbl 1282.93206
[26] Goubault, E., & Putot, S. (2006). Static analysis of numerical algorithms. Proceedings of SAS 06 (pp. 18-34), LNCS 4134. Berlin: Springer-Verlag. · Zbl 1225.68073
[27] Guyonneau, R., Lagrange, S., & Hardouin, L. (2013). A visibility information for multi-robot localization. IEEE/RSJ international conference on intelligent robots and systems (IROS).
[28] Halbwachs, N.; Proy, Y.-E.; Roumanoff, P., Verification of real-time systems using linear relation analysis, Formal Methods in System Design, 11, 2, 157-185 (1997)
[29] Henrion, D.; Korda, M., Convex computation of the region of attraction of polynomial control systems, IEEE Transactions on Automatic Control, 59, 2, 297-312 (2014) · Zbl 1360.93601
[30] Henrion, D.; Lasserre, J.; Lofberg, J., Gloptipoly 3: Moments, optimization and semidefinite programming, Optimization Methods and Software, 24, 4-5, 761-779 (2009) · Zbl 1178.90277
[31] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied interval analysis, with examples in parameter and state estimation, robust control and robotics (2001), London: Springer-Verlag, London · Zbl 1023.65037
[32] Kaynama, S., Maidens, J., Oishi, M., Mitchell, I., & Dumont, G. (2012). Computing the viability kernel using maximal reachable sets. Proceedings of the 15th ACM international conference on hybrid systems: Computation and control (pp. 55-64), HSCC ’12. New York, NY: ACM. · Zbl 1362.93017
[33] Khalil, H., Nonlinear systems (2002), Upper Saddle River, NJ: Prentice Hall, Upper Saddle River, NJ
[34] Konecny, M., Taha, W., Duracz, J., Duracz, A., & Ames, A. (2013). Enclosing the behavior of a hybrid system up to and beyond a zeno point. Cyber-physical systems, networks, and applications (CPSNA). · Zbl 1336.93085
[35] Landau, L.; Lifshitz, E., Fluid mechanics, course of theoretical physics (1987), Oxford: Butterworth-Heinemann, Oxford
[36] Le, B.; Reynet, O.; Jaulin, L., State estimation with fleeting data, Automatica, 48, 2, 381-387 (2012) · Zbl 1260.93153
[37] Le Mézo, T.; Jaulin, L.; Zerr, B., Bracketing the solutions of an ordinary differential equation with uncertain initial conditions, Applied Mathematics and Computation, 318, 70-79 (2018) · Zbl 1426.93022
[38] Le Mézo, T.; Jaulin, L.; Zerr, B., An interval approach to compute invariant sets, IEEE Transactions on Automatic Control, PP, 99, 1-1 (2018)
[39] Lhommeau, M.; Jaulin, L.; Hardouin, L., Capture basin approximation using interval analysis, International Journal of Adaptative Control and Signal Processing, 25, 3, 264-272 (2011) · Zbl 1225.93057
[40] Mackworth, A., Consistency in networks of relations, Artificial Intelligence, 8, 1, 99-118 (1977) · Zbl 0341.68061
[41] Mazhoud, I.; Hadj-Hamou, K.; Bigeon, J.; Remy, G., Interval-based global optimization in engineering using model reformulation and constraint propagation [Special section], Engineering Applications of Artificial Intelligence, 25, 2, 404-417 (2012)
[42] Mitchell, I. (2007). Comparing forward and backward reachability as tools for safety analysis. In A. Bemporad, A. Bicchi, & G. Buttazzo (Eds.), Hybrid systems: Computation and control (pp. 428-443). Berlin: Springer-Verlag. · Zbl 1221.93029
[43] Mitchell, I., Bayen, A., & Tomlin, C. (2001). Validating a Hamilton-Jacobi approximation to hybrid system reachable sets. In M. D. D. Benedetto & A. Sangiovanni-Vincentelli (Eds.), Hybrid systems: Computation and control (pp. 418-432), number 2034 in lecture notes in computer science. Berlin: Springer. · Zbl 0996.93503
[44] Monnet, D.; Ninin, J.; Jaulin, L., Computing an inner and an outer approximation of the viability kernel, Reliable Computing, 22, 139 (2016)
[45] Parrilo, P.; Lall, S., Semidefinite programming relaxations and algebraic optimization in control, European Journal of Control, 9, 2 (2003) · Zbl 1293.93302
[46] Podelski, A., & Wagner, S. (2006). Model checking of hybrid systems: From reachability towards stability. In J. Hespanha & A. Tiwari (Eds.), Hybrid systems: Computation and control (pp. 507-521). Berlin: Springer-Verlag. · Zbl 1178.93077
[47] Quincampoix, M., Differential inclusions and target problems, SIAM Journal on Control and Optimization, 30, 2, 324-335 (1992) · Zbl 0862.49006
[48] Ratschan, S., Approximate quantified constraint solving by cylindrical box decomposition, Reliable Computing, 8, 1, 21-42 (2002) · Zbl 0997.65077
[49] Ratschan, S.; She, Z., Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions, SIAM Journal of Control and Optimization, 48, 7, 4377-4394 (2010) · Zbl 1215.65188
[50] Saint-Pierre, P., Approximation of the viability kernel, Applied Mathematics and Optimization, 29, 2, 187-209 (1994) · Zbl 0790.65081
[51] Saint-Pierre, P. (2002). Hybrid kernels and capture basins for impulse constrained systems. In C. Tomlin & M. Greenstreet (Eds.), In hybrid systems: Computation and control (Vol. 2289, pp. 378-392). Berlin: Springer-Verlag. · Zbl 1050.93041
[52] Sandretto, J.; Chapoutot, A., Validated simulation of differential algebraic equations with Runge-Kutta methods, Reliable Computing, 22, 57 (2016)
[53] Seube, N.; Moitie, R.; Leitmann, G., Aircraft take-off in Windshear: A viability approach, Set-Valued Analysis, 8, 1, 163-180 (2000) · Zbl 0965.93076
[54] She, Z.; Xue, B., Computing an invariance kernel with target by computing Lyapunov-like functions, IET Control Theory Applications, 7, 15, 1932-1940 (2013)
[55] Spivak, M., Calculus on manifolds: A modern approach to classical theorems of advanced calculus (1965), Cambridge, MA: Westview Press, Cambridge, MA · Zbl 0141.05403
[56] Taha, W., & Duracz, A. (2015). Acumen: An open-source testbed for cyber-physical systems research. CYCLONE’15.
[57] Tarski, A., A decision method for elementary algebra and geometry (1951), Berkeley: University of California Press, Berkeley · Zbl 0044.25102
[58] Tornil-Sin, S.; Ocampo-Martinez, C.; Puig, V.; Escobet, T., Robust fault detection of non-linear systems using set-membership state estimation based on constraint satisfaction, Engineering Applications of Artificial Intelligence, 25, 1, 1-10 (2012)
[59] Wilczak, D.; Zgliczynski, P., Cr-Lohner algorithm, Schedae Informaticae, 20, 9-46 (2011)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.