[en] This study considers the discrete-time dynamics of a network of agents that exchange information according to the nearest-neighbour protocol under which all agents are guaranteed to reach consensus asymptotically. We present a fully decentralised algorithm that allows any agent to compute the consensus value of the whole network in finite time using only the minimal number of successive values of its own history. We show that this minimal number of steps is related to a Jordan block decomposition of the network dynamics and present an algorithm to obtain the minimal number of steps in question by checking a rank condition on a Hankel matrix of the local observations. Furthermore, we prove that the minimal number of steps is related to other algebraic and graph theoretical notions that can be directly computed from the Laplacian matrix of the graph and from the underlying graph topology.
Disciplines :
Ingénierie, informatique & technologie: Multidisciplinaire, généralités & autres
Auteur, co-auteur :
Yuan, Y.
Stan, G.-B.
Barahona, M.
Shi, L.
GONCALVES, Jorge ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Langue du document :
Anglais
Titre :
Decentralised minimal-time consensus
Date de publication/diffusion :
2011
Nom de la manifestation :
2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)
Lieu de la manifestation :
Orlando, FL, Etats-Unis
Date de la manifestation :
12-15 December 2011
Titre de l'ouvrage principal :
The proceedings of the 2011 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC)
H. 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.
F. Cucker and S. Smale, "Emergent behavior in flocks," IEEE Transactions on Automatic Control, 2007.
D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Englewood Cliffs, NJ: Prentice-Hall, 1989.
R. Olfati-Saber. "Ultrafast consensus in small-world networks," in Proceedings of American Control Conference, 2005.
D. Watts and S. Strogatz, "Collective dynamics of 'small-world' networks," Nature, 1998.
L. Pecora and M. Barahona, "Synchronization of oscillators in complex networks," Chaos and Complexity Letters, 2005.
M. Barahona and L. Pecora, "Synchronization in small-world systems," Physical Review Letters, 2002.
G.-B. Stan and R. Sepulchre, "Analysis of interconnected oscillators by dissipativity theory", IEEE Transactions on Automatic Control, 2007.
A. Jadbabaie, J. Lin, and A. S. Morse, "Coordination of groups of mobile autonomous agents using nearest neighbor rules," IEEE Transactions on Automatic Control, 2003.
R. Olfati-Saber and R. M. Murray, "Consensus problems in networks of agents with switching topology and time-delays," IEEE Transactions on Automatic Control, 2004.
W. Ren and R. W. Beard, Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications, Springer, 2007.
J. Cortes, "Finite-time convergent gradient flows with applications to network consensus," Automatica, 2006.
S. Sundaram and C. N. Hadjicostis, "Finite-time distributed consensus in graphs with time-invariant topologies," in Proceedings of American Control Conference, 2007.
Y. Yuan, G. Stan, L. Shi and J. Goncalves "Decentralized final value theorem for discrete-time LTI systems with application to minimal-time distributed consensus," in Proceedings of IEEE Conference on Decision and Control, 2009.
L. Xiao and S. Boyd, "Fast linear iterations for distributed averaging," System and control letter, 2004.
E. Gluskin, "Let us teach this generalization of the final-value theorem," European Journal of Physics, 2003.
R. Horn and C. Johnson, Matrix Analysis. Cambridge University Press 1999.
Vincent D. Blondel, Julien M. Hendrickx and John N. Tsitsiklis, "Continuous-time average-preserving opinion dynamics with opinion-dependent communications," SIAM Journal on Control and Optimization, 2010.
D. Boley, F. Luk and D. Vandevoorde, "Vandermonde factorization of a Hankel matrix," Scientific computing, 1997.
S. Martini, M. Egerstedt and A. Bicchi, "Controllability analysis of networked systems using relaxed equitable partitions," International Journal of Systems, Control and Communications, 2010.
Y. Yuan, G. Stan, L. Shi, M. Barahona and J. Goncalves "Decentralised minimal time consensus," submitted to Automatica.
K. Zhou, J. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall, 1996.
C. Godsil and G. Royal, Algebraic Graph Theory, New York: Springer-Verlag, 2001.
M. Egerstedt, "Controllability of networked system," in Proceedings of International Symposium on Mathematical Theory of Networks and Systems 2010.
M. Rafiee and A. Bayen, "Optimal network topology design in multi-agent systems for efficient average consensus," in Proceedings of IEEE Conference on Decision and Control, 2010.
E. van Dam, "Regular graphs with four eigenvalues," Linear Algebra Application, 1995.
E. van Dam, "Nonregular graphs with three eigenvalues," Journal of Combinatorial Theory Series B, 1998.
M. Newman, "The Laplacian spectrum of graphs," master thesis, University of Manitoba, Canada, 2000.
S. Kar and J. Moura, "Ramanujan topologies for decision making in sensor networks," in proceedings of Annual Allerton Conference on Communication, Control and Computing, Monticello, 2006.
Y. Yuan, G. Stan, S. Warnick and J. Goncavles, "Robust network reconstruction from data," Automatica, 2011.
Y. Yuan and J. Goncalves, "Minimal-time network reconstruction for DTLTI systems," in Proceedings of IEEE Conference on Decision and Control, 2010.
