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

• AcceptedNov 6, 2017
• PublishedNov 12, 2018
Share
Rating

### 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

• #### 2

Citations

• Altmetric

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