# American Institute of Mathematical Sciences

• Previous Article
On Algebraic condition for null controllability of some coupled degenerate systems
• MCRF Home
• This Issue
• Next Article
Stabilization of multidimensional wave equation with locally boundary fractional dissipation law under geometric conditions
doi: 10.3934/mcrf.2019009

## Randomized algorithms for stabilizing switching signals

 1 Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India 2 Department of Electrical Engineering, Indian Institute of Science, Bangalore 560012, India 3 Systems & Control Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India

* Corresponding author

Received  June 2017 Revised  July 2018 Published  September 2018

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.

Citation: Niranjan Balachandran, Atreyee Kundu, Debasish Chatterjee. Randomized algorithms for stabilizing switching signals. Mathematical Control & Related Fields, doi: 10.3934/mcrf.2019009
##### References:
 [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.

show all references

##### References:
 [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.
An illustration of the steps in the Proof of Theorem 4.3
Plot for the empirical probability of a cycle being contractive against its length $n$ with $\displaystyle{\Phi (r) = \frac{1}{10}\sqrt{r}}$
 [1] Xiang Xie, Honglei Xu, Xinming Cheng, Yilun Yu. Improved results on exponential stability of discrete-time switched delay systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 199-208. doi: 10.3934/dcdsb.2017010 [2] Hongyan Yan, Yun Sun, Yuanguo Zhu. A linear-quadratic control problem of uncertain discrete-time switched systems. Journal of Industrial & Management Optimization, 2017, 13 (1) : 267-282. doi: 10.3934/jimo.2016016 [3] Yuefen Chen, Yuanguo Zhu. Indefinite LQ optimal control with process state inequality constraints for discrete-time uncertain systems. Journal of Industrial & Management Optimization, 2018, 14 (3) : 913-930. doi: 10.3934/jimo.2017082 [4] Shan Gao, Jinting Wang. On a discrete-time GI$^X$/Geo/1/N-G queue with randomized working vacations and at most $J$ vacations. Journal of Industrial & Management Optimization, 2015, 11 (3) : 779-806. doi: 10.3934/jimo.2015.11.779 [5] Vladimir Răsvan. On the central stability zone for linear discrete-time Hamiltonian systems. Conference Publications, 2003, 2003 (Special) : 734-741. doi: 10.3934/proc.2003.2003.734 [6] Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767 [7] Chuandong Li, Fali Ma, Tingwen Huang. 2-D analysis based iterative learning control for linear discrete-time systems with time delay. Journal of Industrial & Management Optimization, 2011, 7 (1) : 175-181. doi: 10.3934/jimo.2011.7.175 [8] Elena K. Kostousova. On polyhedral estimates for trajectory tubes of dynamical discrete-time systems with multiplicative uncertainty. Conference Publications, 2011, 2011 (Special) : 864-873. doi: 10.3934/proc.2011.2011.864 [9] Qingling Zhang, Guoliang Wang, Wanquan Liu, Yi Zhang. Stabilization of discrete-time Markovian jump systems with partially unknown transition probabilities. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1197-1211. doi: 10.3934/dcdsb.2011.16.1197 [10] Byungik Kahng, Miguel Mendes. The characterization of maximal invariant sets of non-linear discrete-time control dynamical systems. Conference Publications, 2013, 2013 (special) : 393-406. doi: 10.3934/proc.2013.2013.393 [11] Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489 [12] Deepak Kumar, Ahmad Jazlan, Victor Sreeram, Roberto Togneri. Partial fraction expansion based frequency weighted model reduction for discrete-time systems. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 329-337. doi: 10.3934/naco.2016015 [13] Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253 [14] Elena K. Kostousova. On control synthesis for uncertain dynamical discrete-time systems through polyhedral techniques. Conference Publications, 2015, 2015 (special) : 723-732. doi: 10.3934/proc.2015.0723 [15] Elena K. Kostousova. On polyhedral control synthesis for dynamical discrete-time systems under uncertainties and state constraints. Discrete & Continuous Dynamical Systems - A, 2018, 38 (12) : 6149-6162. doi: 10.3934/dcds.2018153 [16] Victor Kozyakin. Minimax joint spectral radius and stabilizability of discrete-time linear switching control systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-11. doi: 10.3934/dcdsb.2018277 [17] Simone Fiori. Auto-regressive moving-average discrete-time dynamical systems and autocorrelation functions on real-valued Riemannian matrix manifolds. Discrete & Continuous Dynamical Systems - B, 2014, 19 (9) : 2785-2808. doi: 10.3934/dcdsb.2014.19.2785 [18] Lih-Ing W. Roeger, Razvan Gelca. Dynamically consistent discrete-time Lotka-Volterra competition models. Conference Publications, 2009, 2009 (Special) : 650-658. doi: 10.3934/proc.2009.2009.650 [19] Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121 [20] Ciprian Preda. Discrete-time theorems for the dichotomy of one-parameter semigroups. Communications on Pure & Applied Analysis, 2008, 7 (2) : 457-463. doi: 10.3934/cpaa.2008.7.457

2017 Impact Factor: 0.631

## Metrics

• PDF downloads (24)
• HTML views (90)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]