[en] This paper considers the problem of obtaining in minimal time the “dynamical network structure” (DNS) from partial state observations of a discrete-time linear time-invariant system. From the DNS, we can not only obtain the network structure of the system at the measurement level, but also estimate the minimal number of hidden states which are not observed directly. First, we discuss when reconstruction of the DNS is and is not possible. Then, we give an algorithm to find the minimal number of successive outputs to find the DNS. Finally, we discuss extensions of the results to non-linear and noisy systems. These results can be directly applied to the decentralised network control problem of multi-agent systems to find network connections of the observed agents.
Disciplines :
Ingénierie, informatique & technologie: Multidisciplinaire, généralités & autres
Auteur, co-auteur :
Yuan, Y.
GONCALVES, Jorge ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Langue du document :
Anglais
Titre :
Minimal-time network reconstruction for DTLTI systems
Date de publication/diffusion :
2010
Nom de la manifestation :
49th IEEE Conference on Decision and Control (CDC)
Lieu de la manifestation :
Atlanta, GA, Etats-Unis
Date de la manifestation :
December 15-17, 2010
Titre de l'ouvrage principal :
The proceedings of the 49th IEEE Conference on Decision and Control (CDC)
R. Horn and C. Johnson, Matrix analysis, Cambridge University Press 1999.
S. Sundaram and C. N. Hadjicostis, "Finite-time distributed consensus in graphs with time-invariant topologies," Proceedings of the American Control Conference, 2007.
Y. Yuan, G. Stan, L. Shi and J. Goncalves, " Decentralised final value theorem for discrete-time LTI systems with application to minimal-time distributed consensus," Proceedings of the Conference on Decision and Control, 2009.
Y. Yuan, G. Stan, L. Shi, M. Barahona and J. Goncalves, " Minimal-time final value of unknown DT-LTI systems with application to the decentralised network consensus problem," The 19th International Symposium on Mathematical Theory of Networks and Systems, 2010.
Y. Yuan, G.-B. Stan, S. Warnick and J. Goncavles, "Robust dynamical network structure reconstruction," To appear, Automatica, 2010.
J. Goncalves and S. Warnick, "Necessary and sufficient conditions for dynamical structure reconstruction of LTI networks", IEEE Transactions on Automatic Control, vol. 53, 2008.
Y. Yuan, G.-B. Stan, S. Warnick and J. Goncavles, "Minimal dynamical structure realisations with application to network reconstruction from data," in revision, IEEE Transaction on Automatic Control, 2010.
E.D. Sontag, "Network reconstruction based on steady-state data", Essays in Biochemistry, 45:161-176, 2008.
D. Materassi, G. Innocenti, L. Giarre, "Reduced complexity models in the identification of dynamical networks: links with sparsification problems", Proceedings of Conference on Decision and Control, 2009.
L. Pecora and M. Barahona, "Synchronisation of oscillators in complex networks," Chaos and Complexity Letters, 1, 61, 2005.
H. G. Tanner, A. Jadbabaie, and G. J. Pappas, "Stable flocking of mobile agents, part I: Fixed topology," in Proceedings of IEEE Conference of Decision and Control, 2003, pp. 2010-2015.
H. G. Tanner, A. Jadbabaie, and G. J. Pappas, "Stable flocking of mobile agents, part II: Dynamic topology," in Proceedings of IEEE Conference on Decision and Control, 2003, pp. 2016-2021.
A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination of groups of mobile autonomous agents using nearest neighbour rules," IEEE Transactions on Automatic Control, vol. 48, no. 6, 2003.
R. Olfati-Saber. "Flocking for multi-agent dynamic systems: algorithms and theory," IEEE Trans. on Automatic Control, vol. 51(3), pp. 401-420, Mar. 2006.
R. Olfati-Saber. "Evolutionary dynamics of behavior in social networks," Proceedings of the 46th IEEE Conference on Decision and Control, Dec. 2007
W. Ren and R. W. Beard, Distributed consensus in multi-vehicle cooperative control: theory and applications, Springer, 2007.
C. Godsil and G. Royal, Algebraic graph theory, New York: Springer-Verlag, 2001.
L. Ljung, "System identification: theory for user," Prentince Hall, 1999.
S. Mason and H. Zimmermann, Eletronic circuits, signals and systems. John Wiley and Sons, INC. 1968.
R. Olfati-Saber and R. M. Murray, "Consensus problems in networks of agents with switching topology and time-delays," IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520-1533, 2004.
Z. Nehari, "On bounded bilinear forms," Annals of Maths, vol. 65, no.1, 1957.
N. Young, An introduction to Hilbert space. Cambridge university press, 1988.
S. Power, Hankel operators on Hilbert space.Pitman Advanced Pub., 1982.
K. Glover and L. Silverman "Characterisation of structural controllability," IEEE Transactions on Automatic Control, 21 (4). pp. 534-537, 1976.
K. Glover, "A tutorial on Hankel-norm approximation," In: Willems, J.C., (ed.) From Data to Model. Springer-Verlag, Berlin, Germany, pp. 26-48, 1989.
K. Zhou, J. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall, 1996.
S. Martini, M. Egerstedt, and A. Bicchi, "Controllability Analysis of Networked Systems Using Equitable Partitions," International Journal of Systems, Control and Communications, Vol. 2, No. 1/2/3, pp. 100-121, Jan. 2010.
