
Previous Article
Insensitizing controls for a semilinear parabolic equation: A numerical approach
 MCRF Home
 This Issue

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 
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.
References:
[1] 
B. Bollobás, Modern Graph Theory, vol. 184 of Graduate Texts in Mathematics, SpringerVerlag, New York, 1998. doi: 10.1007/9781461206194. 
[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 dwelltime, 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), 754767. 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), 10321037. 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 discretetime 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 discretetime switched systems, Nonlinear Analysis: Hybrid Systems, 23 (2017), 191210. doi: 10.1016/j.nahs.2016.06.002. 
[11] 
K. Lee and R. Bhattacharya, Stability analysis of largescale distributed networked control systems with random communication delays: a switched system approach, Systems & Control Letters, 85 (2015), 7783. doi: 10.1016/j.sysconle.2015.08.011. 
[12] 
S. Lewandowski, Shortest paths and negative cycle detection in graph with negative weights I. the BellmanFordMoore 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/9781461200178. 
[14] 
D. Liberzon and A. S. Morse, Basic problems in stability and design of switched systems, IEEE Control Systems Magazine, 19 (1999), 5970. 
[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), 308322. doi: 10.1109/TAC.2008.2012009. 
[16] 
J. L. MancillaAguilar, 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), 472490. 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, SpringerVerlag, Berlin, 2002. doi: 10.1007/9783642040160. 
[19] 
T. Yamada and H. Kinoshita, Finding all the negative cycles in a directed graph, Discrete Appl. Math., 118 (2002), 279291. doi: 10.1016/S0166218X(01)002013. 
[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 discretetime 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, SpringerVerlag, New York, 1998. doi: 10.1007/9781461206194. 
[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 dwelltime, 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), 754767. 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), 10321037. 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 discretetime 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 discretetime switched systems, Nonlinear Analysis: Hybrid Systems, 23 (2017), 191210. doi: 10.1016/j.nahs.2016.06.002. 
[11] 
K. Lee and R. Bhattacharya, Stability analysis of largescale distributed networked control systems with random communication delays: a switched system approach, Systems & Control Letters, 85 (2015), 7783. doi: 10.1016/j.sysconle.2015.08.011. 
[12] 
S. Lewandowski, Shortest paths and negative cycle detection in graph with negative weights I. the BellmanFordMoore 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/9781461200178. 
[14] 
D. Liberzon and A. S. Morse, Basic problems in stability and design of switched systems, IEEE Control Systems Magazine, 19 (1999), 5970. 
[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), 308322. doi: 10.1109/TAC.2008.2012009. 
[16] 
J. L. MancillaAguilar, 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), 472490. 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, SpringerVerlag, Berlin, 2002. doi: 10.1007/9783642040160. 
[19] 
T. Yamada and H. Kinoshita, Finding all the negative cycles in a directed graph, Discrete Appl. Math., 118 (2002), 279291. doi: 10.1016/S0166218X(01)002013. 
[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 discretetime switched systems, Proceedings of the American Control Conference, 1880–1885. 
[1] 
Xiang Xie, Honglei Xu, Xinming Cheng, Yilun Yu. Improved results on exponential stability of discretetime switched delay systems. Discrete & Continuous Dynamical Systems  B, 2017, 22 (1) : 199208. doi: 10.3934/dcdsb.2017010 
[2] 
Hongyan Yan, Yun Sun, Yuanguo Zhu. A linearquadratic control problem of uncertain discretetime switched systems. Journal of Industrial & Management Optimization, 2017, 13 (1) : 267282. doi: 10.3934/jimo.2016016 
[3] 
Yuefen Chen, Yuanguo Zhu. Indefinite LQ optimal control with process state inequality constraints for discretetime uncertain systems. Journal of Industrial & Management Optimization, 2018, 14 (3) : 913930. doi: 10.3934/jimo.2017082 
[4] 
Shan Gao, Jinting Wang. On a discretetime GI$^X$/Geo/1/NG queue with randomized working vacations and at most $J$ vacations. Journal of Industrial & Management Optimization, 2015, 11 (3) : 779806. doi: 10.3934/jimo.2015.11.779 
[5] 
Vladimir Răsvan. On the central stability zone for linear discretetime Hamiltonian systems. Conference Publications, 2003, 2003 (Special) : 734741. doi: 10.3934/proc.2003.2003.734 
[6] 
Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Framebound priority scheduling in discretetime queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767788. doi: 10.3934/jimo.2011.7.767 
[7] 
Chuandong Li, Fali Ma, Tingwen Huang. 2D analysis based iterative learning control for linear discretetime systems with time delay. Journal of Industrial & Management Optimization, 2011, 7 (1) : 175181. doi: 10.3934/jimo.2011.7.175 
[8] 
Elena K. Kostousova. On polyhedral estimates for trajectory tubes of dynamical discretetime systems with multiplicative uncertainty. Conference Publications, 2011, 2011 (Special) : 864873. doi: 10.3934/proc.2011.2011.864 
[9] 
Qingling Zhang, Guoliang Wang, Wanquan Liu, Yi Zhang. Stabilization of discretetime Markovian jump systems with partially unknown transition probabilities. Discrete & Continuous Dynamical Systems  B, 2011, 16 (4) : 11971211. doi: 10.3934/dcdsb.2011.16.1197 
[10] 
Byungik Kahng, Miguel Mendes. The characterization of maximal invariant sets of nonlinear discretetime control dynamical systems. Conference Publications, 2013, 2013 (special) : 393406. doi: 10.3934/proc.2013.2013.393 
[11] 
Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discretetime linear multiagent systems with observertype protocols. Discrete & Continuous Dynamical Systems  B, 2011, 16 (2) : 489505. 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 discretetime systems. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 329337. doi: 10.3934/naco.2016015 
[13] 
Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discretetime coupled systems with multidiffusion by graphtheoretic approach and its application. Discrete & Continuous Dynamical Systems  B, 2016, 21 (1) : 253269. doi: 10.3934/dcdsb.2016.21.253 
[14] 
Elena K. Kostousova. On control synthesis for uncertain dynamical discretetime systems through polyhedral techniques. Conference Publications, 2015, 2015 (special) : 723732. doi: 10.3934/proc.2015.0723 
[15] 
Elena K. Kostousova. On polyhedral control synthesis for dynamical discretetime systems under uncertainties and state constraints. Discrete & Continuous Dynamical Systems  A, 2018, 38 (12) : 61496162. doi: 10.3934/dcds.2018153 
[16] 
Victor Kozyakin. Minimax joint spectral radius and stabilizability of discretetime linear switching control systems. Discrete & Continuous Dynamical Systems  B, 2017, 22 (11) : 111. doi: 10.3934/dcdsb.2018277 
[17] 
Simone Fiori. Autoregressive movingaverage discretetime dynamical systems and autocorrelation functions on realvalued Riemannian matrix manifolds. Discrete & Continuous Dynamical Systems  B, 2014, 19 (9) : 27852808. doi: 10.3934/dcdsb.2014.19.2785 
[18] 
LihIng W. Roeger, Razvan Gelca. Dynamically consistent discretetime LotkaVolterra competition models. Conference Publications, 2009, 2009 (Special) : 650658. doi: 10.3934/proc.2009.2009.650 
[19] 
Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discretetime finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 11211133. doi: 10.3934/jimo.2016.12.1121 
[20] 
Ciprian Preda. Discretetime theorems for the dichotomy of oneparameter semigroups. Communications on Pure & Applied Analysis, 2008, 7 (2) : 457463. doi: 10.3934/cpaa.2008.7.457 
2017 Impact Factor: 0.631
Tools
Metrics
Other articles
by authors
[Back to Top]