Article Contents
Article Contents

# Randomized algorithms for stabilizing switching signals

• * Corresponding author
• Qualitative behaviour of switched systems has attracted considerable research attention in the recent past. In this article we study 'how likely' is it for a family of systems to admit stabilizing switching signals. A weighted digraph is associated to a switched system in a natural fashion, and the switching signal is expressed as an infinite walk on this digraph. We provide a linear time probabilistic algorithm to find cycles on this digraph that have a desirable property (we call it "contractivity"), and under mild statistical hypotheses on the connectivity and weights of the digraph, demonstrate that there exist uncountably many stabilizing switching signals derived from such cycles. Our algorithm does not require the vertex and edge weights to be stored in memory prior to its application, has a learning/exploratory character, and naturally fits very large scale systems.

Mathematics Subject Classification: Primary: 93C30; Secondary: 60G42.

 Citation:

• Figure 1.  An illustration of the steps in the Proof of Theorem 4.3

Figure 2.  Plot for the empirical probability of a cycle being contractive against its length $n$ with $\displaystyle{\Phi (r) = \frac{1}{10}\sqrt{r}}$

•  [1] B. Bollobás, Modern Graph Theory, vol. 184 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1998. doi: 10.1007/978-1-4612-0619-4. [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, Cambridge, MA, 2009. [3] R. Durrett, Probability: Theory and Examples, 4th edition, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, Cambridge, 2010. doi: 10.1017/CBO9780511779398. [4] S. S. Ge and Z. Sun, Switched Linear Systems: Control and Design, Springer, London, 2005. [5] J. P. Hespanha and A. S. Morse, Stability of switched systems with average dwell-time, in Proceedings of the 38th IEEE Conference on Decision and Contr., 1999, 2655–2660. doi: 10.1109/CDC.1999.831330. [6] H. Ishii, T. Bașar and R. Tempo, Randomized algorithms for synthesis of switching rules for multimodal systems, IEEE Transactions on Automatic Control, 50 (2005), 754-767.  doi: 10.1109/TAC.2005.849187. [7] Ö. Karabacak, Dwell time and average dwell time methods based on the cycle ratio of the switching graph, Systems & Control Letters, 62 (2013), 1032-1037.  doi: 10.1016/j.sysconle.2013.08.002. [8] A. Kundu, Stabilizing Switching Signals for Switched Systems: Analysis and Synthesis, PhD thesis, Indian Institute of Technology Bombay, 2015. [9] A. Kundu and D. Chatterjee, Stabilizing discrete-time switched linear systems, Proceedings of the 17th ACM International Conference on Hybrid Systems: Computation & Control, 2014, Berlin, Germany, 11–20. [10] A. Kundu and D. Chatterjee, On stability of discrete-time switched systems, Nonlinear Analysis: Hybrid Systems, 23 (2017), 191-210.  doi: 10.1016/j.nahs.2016.06.002. [11] K. Lee and R. Bhattacharya, Stability analysis of large-scale distributed networked control systems with random communication delays: a switched system approach, Systems & Control Letters, 85 (2015), 77-83.  doi: 10.1016/j.sysconle.2015.08.011. [12] S. Lewandowski, Shortest paths and negative cycle detection in graph with negative weights I. the Bellman-Ford-Moore algorithm revisited, Technical Report 2010/05, Universität Stuttgart, FMI, Stuttgart, Germany. [13] D. Liberzon, Switching in Systems and Control, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 2003. doi: 10.1007/978-1-4612-0017-8. [14] D. Liberzon and A. S. Morse, Basic problems in stability and design of switched systems, IEEE Control Systems Magazine, 19 (1999), 59-70. [15] H. Lin and P. J. Antsaklis, Stability and stabilizability of switched linear systems: A survey of recent results, IEEE Transactions on Automatic Control, 54 (2009), 308-322.  doi: 10.1109/TAC.2008.2012009. [16] J. L. Mancilla-Aguilar, R. García, E. Sontag and Y. Wang, Uniform stability properties of switched systems with switchings governed by digraphs, Nonlinear Analysis. Theory, Methods & Applications. Series A: Theory and Methods, 63 (2005), 472-490.  doi: 10.1016/j.na.2005.04.043. [17] S. Mitra, N. Lynch and D. Liberzon, Verifying average dwell time by solving optimization problems, in Hybrid Systems: Computation and Control, vol. 3927 of Lecture Notes in Computer Science, Springer, Berlin, 2006,476–490. doi: 10.1007/11730637_36. [18] M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, vol. 23 of Algorithms and Combinatorics, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-04016-0. [19] T. Yamada and H. Kinoshita, Finding all the negative cycles in a directed graph, Discrete Appl. Math., 118 (2002), 279-291.  doi: 10.1016/S0166-218X(01)00201-3. [20] C. Zaroliagis, Negative cycles in weighted digraphs, Encyclopedia of Algorithms, 576–578. [21] G. Zhai, H. Bo, K. Yasuda and A. N. Michel, Qualitative analysis of discrete-time switched systems, Proceedings of the American Control Conference, 1880–1885.

Figures(2)