Randomized algorithms for stabilizing switching signals

Niranjan Balachandran; Atreyee Kundu; Debasish Chatterjee

doi:10.3934/mcrf.2019009

Article Contents

2019, Volume 9, Issue 1: 159-174. Doi: 10.3934/mcrf.2019009

This issue Previous Article Insensitizing controls for a semilinear parabolic equation: A numerical approach Next Article Extension of the strong law of large numbers for capacities

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
* Corresponding author

Received: May 31, 2017

Revised: June 30, 2018

Published: January 2019

Abstract Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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}}$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.