logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 1: 012205(2019) https://doi.org/10.1007/s11432-017-9311-x

On strong structural controllability and observability of linear time-varying systems: a constructive method

More info
  • ReceivedJul 30, 2017
  • AcceptedNov 6, 2017
  • PublishedNov 12, 2018

Abstract

In this paper, we consider the controllability and observability of generalized linear time-varying (LTV) systems whose coefficients are not exactly known. All that is known about these systems is the placement of non-zero entries in their coefficient matrices $(A,B)$. We provide the characterizations in order to judge whether the placements can guarantee the controllability/observability of such LTV systems, regardless of the exact value of each non-zero coefficient. We also present a direct and efficient algorithm with an associated time cost of $O(n+m+\nu)$ to verify the conditions of our characterizations, where $n$ and $m$ denote the number of columns of $A$ and $B$, respectively, and $\nu$ is number of non-zero entries in $(A,B)$.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61233004, 61590924, 61521063).


References

[1] Kalman R E, Ho Y C, Narenda K S. Controllability of linear dynamical systems. Contrib Diff Eqs, 1963, 1: 189--213. Google Scholar

[2] Rosenbrock H H. State-Space and Multivariable Theory. New York: Wiley, 1970. Google Scholar

[3] Hautus M L J. Controllability and observability conditions of linear autonomous systems. Nederl Akad Wet Proc Ser A, 1969, 72: 443--448. Google Scholar

[4] Ching-Tai Lin . Structural controllability. IEEE Trans Automat Contr, 1974, 19: 201-208 CrossRef Google Scholar

[5] Shields R, Pearson J. Structural controllability of multiinput linear systems. IEEE Trans Automat Contr, 1976, 21: 203-212 CrossRef Google Scholar

[6] Mayeda H. On structural controllability theorem. IEEE Trans Automat Contr, 1981, 26: 795-798 CrossRef Google Scholar

[7] Wang L, Jiang F C, Xie G M. Controllability of multi-agent systems based on agreement protocols. Sci China Ser F-Inf Sci, 2009, 52: 2074-2088 CrossRef Google Scholar

[8] Guan Y, Wang L. Structural controllability of multi-agent systems with absolute protocol under fixed and switching topologies. Sci China Inf Sci, 2017, 60: 092203 CrossRef Google Scholar

[9] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473: 167-173 CrossRef PubMed ADS Google Scholar

[10] Mu J, Li S, Wu J. On the structural controllability of distributed systems with local structure changes. Sci China Inf Sci, 2018, 61: 052201 CrossRef Google Scholar

[11] Mayeda H, Yamada T. Strong Structural Controllability. SIAM J Control Optim, 1979, 17: 123-138 CrossRef Google Scholar

[12] Hartung C, Reissig G, Svaricek F. Characterization of strong structural controllability of uncertain linear time-varying discrete-time systems. In: Proceedings of the 51st IEEE Conference on Decision and Control, Maui, 2012. 2189--2194. Google Scholar

[13] Hartung C, Reissig G, Svaricek F. Sufficient conditions for strong structural controllability of uncertain linear time-varying systems. In: Proceedings of American Control Conference, Washington, 2013. 5895--5900. Google Scholar

[14] Hartung C, Reissig G, Svaricek F. Necessary conditions for structural and strong structural controllability of linear time-varying systems. In: Proceedings of European Control Conference, Zurich, 2013. 1335--1340. Google Scholar

[15] Reissig G, Hartung C, Svaricek F. Strong Structural Controllability and Observability of Linear Time-Varying Systems. IEEE Trans Automat Contr, 2014, 59: 3087-3092 CrossRef Google Scholar

[16] Rugh W J. Linear System Theory. 2nd ed. Englewood Cliffs: Prentice Hall, 1996. Google Scholar

[17] Kalman R E. On the general theory of control systems. IEEE Trans Automat Contr, 1959, 4: 481--492. Google Scholar

[18] Sontag E D. Mathematical Control Theory. 2nd ed. New York: Springer, 1991. Google Scholar

[19] Liu X, Lin H, Chen B M. Graph-theoretic characterisations of structural controllability for multi-agent system with switching topology. Int J Control, 2013, 86: 222-231 CrossRef Google Scholar

  • Figure 1

    Run time of Algorithm 1to verify strong structurally controllable property which depends on $\nu$ and $n$ for randomly chosen structural matrices $(\bar~A,~\bar~B)~\in~\{~0,~*~\}^{n~\times~(n+m)}$ such that each LTV system $(\bar~A,~\bar~B)$ is strong structurally controllable. $\nu$ denotes the number of non-zero entries in $(\bar~A,~\bar~B)$. The underlying implementation of Algorithm 1was executed in C programming language on a Intel Core i3-2120 (3.3 GHz). (a) $n~=~1000,~m~=~250$; (b) $m~=~500,~\nu~=~50000$.

  •   

    Algorithm 1 SSC checking for structural LTV system

    $~\mathbf{Input}~$

    $~U~=~\{~u_1,~\ldots~,~u_n~\},~V~=~\{~v_1,~\ldots~,~v_{n+m}~\}~$,

    $~N(u_1),\ldots,N(u_n),N(v_1),\ldots,N(v_{n+m})~$,

    $~\mathbf{Initialization}~$

    $t~=~1$,

    $W~=~\lbrace~v_{n+1},\ldots,v_{n+m}~\rbrace$,

    $\tilde~W~=~W$,

    $\tilde~U~=~U$,

    for $x~\in~U~\cup~V$

    $\tilde~N(x)~=~N(x)$,

    end for

    $~\mathbf{Main~~Algorithm}~$

    while $~\tilde~U~\neq~\emptyset$ do

    $x~=~$ Null,

    for each $~w~\in~W$

    if $~|~\tilde~N(w)~|~=~1$ with $\tilde~N(w)~=~u_{i_t}$ then

    $x~=~w$,

    $y~=~u_{i_t}$,

    Break,

    end if

    end for

    if $x~=~\emptyset$ then

    Return “False",

    Break,

    end if

    $t~=~t+1$,

    for each $z\in~\tilde~N(y)$

    $~\tilde~N(z)~=~\tilde~N(z)~-~\lbrace~y~\rbrace$,

    end for

    $~\tilde~U~=~\tilde~U~-~\lbrace~y~\rbrace$,

    $~~W~=~~W~\cup~\lbrace~y~\rbrace~-~\lbrace~x~\rbrace$,

    $~\tilde~W~=~\tilde~W~\cup~\lbrace~y~\rbrace$,

    Delete $~\tilde~N(y)$,

    end while

    if $\tilde~U~=~\emptyset$ then

    Return “True",

    end if

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1