×

Combinatorial methods for invariance and safety of hybrid systems. (English) Zbl 1406.93145

Summary: Inspired by switching systems and automata theory, we investigate how combinatorial analysis techniques can be performed on a hybrid automaton in order to enhance its safety or invariance analysis. We focus on the particular case of “constrained switching systems”, that is, hybrid automata with linear dynamics and no guards. We follow two opposite approaches, each with unique benefits: First, we construct invariant sets via the “reduced” system, induced by a smaller graph which consists of the essential nodes, called the unavoidable nodes. The computational amelioration of working with a smaller, and in certain cases the minimum necessary number of nodes, is significant. Second, we exploit graph liftings, in particular the Iterated dynamics lift (\(T\)-lift) and the path-dependent lift (\(P\)-Lift). For the former case, we show that invariant sets can be computed in a fraction of the iterations compared to the non-lifted case, while we show how the latter can be utilized to compute non-convex approximations of invariant sets of a controlled complexity.
We also revisit well-studied problems, highlighting the potential benefits of the approach. In particular, we apply our framework to (i) invariant sets computations for systems with dwell-time restrictions, (ii) fast computations of the maximal invariant set for uncertain linear systems and (iii) non-convex approximations of the minimal invariant set for arbitrary switching linear systems.

MSC:

93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
93C05 Linear systems in control theory
93C55 Discrete-time control/observation systems
93B11 System structure simplification
37F20 Combinatorics and topology in relation with holomorphic dynamical systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Artstein, Z.; Rakovic, S. V., Feedback and invariance under uncertainty via set iterates, Automatica, 44, 520-525 (2008) · Zbl 1283.93167
[2] Artstein, Z.; Rakovic, S. V., Set invariance under output feedback : A set-dynamics approach, International Journal of Systems Science, 42, 539-555 (2011) · Zbl 1233.93044
[3] Athanasopoulos, N., & Lazar, M. (2014). Stability analysis of switched systems defined by graphs. In 53rd IEEE conference on decision and control; Athanasopoulos, N., & Lazar, M. (2014). Stability analysis of switched systems defined by graphs. In 53rd IEEE conference on decision and control
[4] Athanasopoulos, N.; Smpoukis, K.; Jungers, R. M., Invariant sets analysis for constrained switching systems, IEEE Control Systems Letters, 1, 256-261 (2017)
[5] Blanchini, F., Set invariance in control -A survey, Automatica, 35, 1747-1767 (1999), Survey Paper · Zbl 0935.93005
[6] Blanchini, F.; Miani, S., (Set-theoretic methods in control. Set-theoretic methods in control, Systems & control: Foundations & applications (2008), Birkhauser: Birkhauser Boston, Basel, Berlin) · Zbl 1140.93001
[7] Bliman, P.-A., & Ferrari-Trecate, G. (2003). Stability analysis of discrete-time switched systems through Lyapunov functions with nonminimal state. In IFAC conference on the analysis and design of hybrid systems; Bliman, P.-A., & Ferrari-Trecate, G. (2003). Stability analysis of discrete-time switched systems through Lyapunov functions with nonminimal state. In IFAC conference on the analysis and design of hybrid systems
[8] Cambier, L., Philippe, M., & Jungers, R. M. CSS Toolbox for Matlab http://www.mathworks.com/matlabcentral/fileexchange/52723-the-cssystem-toolbox; Cambier, L., Philippe, M., & Jungers, R. M. CSS Toolbox for Matlab http://www.mathworks.com/matlabcentral/fileexchange/52723-the-cssystem-toolbox
[9] Dai, X., A Gel’fand-type spectral radius formula and stability of linear constrained switching systems, Linear Algebra and its Applications, 436, 1099-1113 (2012) · Zbl 1237.15010
[10] De Santis, E.; Di Benedetto, M. D.; Berardi, L., Computation of maximal safe sets for switching systems, IEEE Transactions on Automatic Control, 49, 184-195 (2004) · Zbl 1365.93287
[11] Dehghan, M.; Ong, C.-J., Characterization and computation of disturbance invariant sets for constrained switched linear systems with dwell time restriction, Automatica, 48, 2175-2181 (2012) · Zbl 1257.93059
[12] Dehghan, M.; Ong, C.-J., Discrete-time switching linear systems with constraints: Characterization and computation of invariant sets under dwell-time consideration, Automatica, 48, 964-969 (2012) · Zbl 1246.93073
[13] Donkers, M. C.F.; Heemels, W. P.M.; van den Wouw, N.; Hetel, L., Stability analysis of networked systems using a switched linear systems approach, IEEE Transactions on Automatic Control, 56, 2101-2115 (2011) · Zbl 1368.93465
[14] Essick, R.; Lee, J.-W.; Dullerud, G. E., Control of linear switched systems with receding horizon modal information, IEEE Transactions on Automatic Control, 59, 2340-2352 (2014) · Zbl 1360.93333
[15] Even, G.; Naor, S. J.; Schieber, B.; Sudan, M., Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 151-174 (1998) · Zbl 0897.68078
[16] Geiselhart, R.; Gielen, R. H.; Lazar, M.; Wirth, F. R., An alternative converse Lyapunov theorem for discrete-time systems, Systems & Control Letters, 70, 49-59 (2014) · Zbl 1290.93149
[17] Girard, A.; Pappas, G. J., Approximate bisimulation: A bridge between computer science and control theory, European Journal of Control, 17, 568-578 (2011) · Zbl 1253.68241
[18] Goebel, R.; Sanfelice, R. G.; Teel, A. R., Hybrid dynamical systems: Modeling stability, and robustness (2012), Princeton University Press · Zbl 1241.93002
[19] Hernandez-Mejias, M. A.; Sala, A.; Arino, C.; Querol, A., Reliable controllable sets for constrained Markov-Jump Linear Systems, International Journal of Robust and Nonlinear Control, 26, 2075-2089 (2015) · Zbl 1342.93042
[20] Jungers, R. M., (The joint spectral radius: theory and applications. The joint spectral radius: theory and applications, Lecture notes in control and information sciences, Vol.385 (2009), Springer)
[21] Karp, R. M., Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103 (1972) · Zbl 1467.68065
[22] Kolmanovsky, I. V.; Gilbert, E. G., Theory and computation of disturbance invariant sets for discrete-time linear systems, Mathematical Problems in Egineering, 4, 317-367 (1998) · Zbl 0923.93005
[23] Lazar, M., Doban, A. I., & Athanasopoulos, N. (2013). On stability analysis of discrete-time homogeneous dynamics. In 17th international conference on system theory, control and computing; Lazar, M., Doban, A. I., & Athanasopoulos, N. (2013). On stability analysis of discrete-time homogeneous dynamics. In 17th international conference on system theory, control and computing
[24] Lee, J.-W.; Dullerud, G. E., Uniform stabilization of discrete-time switched and Markovian jump linear systems, Automatica, 42, 205-218 (2006) · Zbl 1105.93049
[25] Liberzon, D., Switching in systems and control (2003), Birkhauser: Birkhauser Boston · Zbl 1036.93001
[26] Lothaire, M., Algebraic combinatorics on words, Vol. 90 (2002), Cambridge University Press · Zbl 1001.68093
[27] Philippe, M.; Essick, R.; Dullerud, R.; Jungers, R. M., Stability of discrete-time switching systems with constrained switching sequences, Automatica, 72, 242-250 (2015) · Zbl 1344.93088
[28] Protasov, V. Y.; Jungers, R. M., Resonance and marginal instability of switching systems, Nonlinear Analysis. Hybrid Systems, 17, 81-93 (2015) · Zbl 1342.37029
[29] Rakovic, S. V., Kern, B., & Findeisen, R. (2010). Practical set invariance for decentralized discrete-time systems. In 49th IEEE conference on decision and control; Rakovic, S. V., Kern, B., & Findeisen, R. (2010). Practical set invariance for decentralized discrete-time systems. In 49th IEEE conference on decision and control
[30] Rakovic, S. V., Kern, B., & Findeisen, R. (2011). Practical robust positive invariance for large-scale discrete time systems. In IFAC world congress; Rakovic, S. V., Kern, B., & Findeisen, R. (2011). Practical robust positive invariance for large-scale discrete time systems. In IFAC world congress
[31] Rakovic, S. V.; Kerrigan, E. C.; Kouramas, K. I.; Mayne, D. Q., Invariant approximations of the minimal robustly positively invariant sets, IEEE Transactions on Automatic Control, 50, 3, 406-410 (2005) · Zbl 1365.93122
[32] Rakovic, S. V., Kouramas, K. I., Kerrigan, J. C., & Mayne, D. Q. (2005). The minimal robust positively invariant set for linear difference inclusions and its robust positively invariant approximations. Tech. Rep. EEE/C P /SVR/9-d/2005, Imperial College, London, UK.; Rakovic, S. V., Kouramas, K. I., Kerrigan, J. C., & Mayne, D. Q. (2005). The minimal robust positively invariant set for linear difference inclusions and its robust positively invariant approximations. Tech. Rep. EEE/C P /SVR/9-d/2005, Imperial College, London, UK. · Zbl 1365.93122
[33] Shorten, R.; Wirth, F.; Mason, O.; Wulff, K.; King, C., Stabiliy criteria for switched and hybrid systems, SIAM Review, 49, 545-592 (2007) · Zbl 1127.93005
[34] Wang, Y.; Roohi, N.; Dullerud, G. E.; Viswanathan, M., Stability analysis of switched linear systems defined by regular languages, IEEE Transactions on Automatic Control, 62, 2568-2575 (2017) · Zbl 1366.93558
[35] Zhang, L.; Zhuang, S.; Braatz, R. D., Switched model predictive control of switched linear systems: Feasibility, stability and robustness, Automatica, 67, 8-21 (2016) · Zbl 1335.93041
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.