March  2019, 9(1): 159-174. 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, 2019, 9 (1) : 159-174. 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. Google Scholar

[2]

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, Cambridge, MA, 2009. Google Scholar

[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. Google Scholar

[4]

S. S. Ge and Z. Sun, Switched Linear Systems: Control and Design, Springer, London, 2005.Google Scholar

[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. Google Scholar

[6]

H. IshiiT. 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. Google Scholar

[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. Google Scholar

[8]

A. Kundu, Stabilizing Switching Signals for Switched Systems: Analysis and Synthesis, PhD thesis, Indian Institute of Technology Bombay, 2015.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[14]

D. Liberzon and A. S. Morse, Basic problems in stability and design of switched systems, IEEE Control Systems Magazine, 19 (1999), 59-70. Google Scholar

[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. Google Scholar

[16]

J. L. Mancilla-AguilarR. GarcíaE. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

C. Zaroliagis, Negative cycles in weighted digraphs, Encyclopedia of Algorithms, 576–578.Google Scholar

[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.Google Scholar

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. Google Scholar

[2]

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, Cambridge, MA, 2009. Google Scholar

[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. Google Scholar

[4]

S. S. Ge and Z. Sun, Switched Linear Systems: Control and Design, Springer, London, 2005.Google Scholar

[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. Google Scholar

[6]

H. IshiiT. 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. Google Scholar

[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. Google Scholar

[8]

A. Kundu, Stabilizing Switching Signals for Switched Systems: Analysis and Synthesis, PhD thesis, Indian Institute of Technology Bombay, 2015.Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.Google Scholar

[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. Google Scholar

[14]

D. Liberzon and A. S. Morse, Basic problems in stability and design of switched systems, IEEE Control Systems Magazine, 19 (1999), 59-70. Google Scholar

[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. Google Scholar

[16]

J. L. Mancilla-AguilarR. GarcíaE. 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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

C. Zaroliagis, Negative cycles in weighted digraphs, Encyclopedia of Algorithms, 576–578.Google Scholar

[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.Google Scholar

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]

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, 2019, 24 (8) : 3537-3556. 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

2018 Impact Factor: 1.292

Metrics

  • PDF downloads (62)
  • HTML views (562)
  • Cited by (0)

[Back to Top]