[en] This paper considers a group of agents that aim to reach an agreement on individually measured time-varying signals by local communication. In contrast to static network
averaging problem, the consensus we mean in this paper is reached in a dynamic sense. A discrete-time dynamic average consensus protocol can be designed to allow all the agents
tracking the average of their reference inputs asymptotically.
We propose a minimal-time dynamic consensus algorithm, which only utilises minimal number of local observations of randomly picked node in a network to compute the final consensus signal. Our results illustrate that with memory and computational ability, the running time of distributed averaging algorithms can be indeed improved dramatically using local information as suggested by Olshevsky and Tsitsiklis.
Disciplines :
Ingénierie, informatique & technologie: Multidisciplinaire, généralités & autres
Auteur, co-auteur :
Yuan, Y.
Liu, J.
Murray, R. M.
GONCALVES, Jorge ; University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB)
Langue du document :
Anglais
Titre :
Decentralised minimal-time dynamic consensus
Date de publication/diffusion :
2012
Nom de la manifestation :
2012 American Control Conference (ACC)
Lieu de la manifestation :
Montreal, Canada
Date de la manifestation :
June 27-29 2012
Titre de l'ouvrage principal :
The proceedings of the 2012 American Control Conference (ACC)
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.
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. Cybenko, "Dynamic load balancing for distributed memory multiprocessors," Journal of Parallel and Distributed Computing, 1989.
Y. Wang and F. Doyle, "On influences of global and local cues on the rate of synchronization of oscillator networks," To appear, Automatica, 2011.
M. Xue, E. Yeung, A. Rai, S. Roy, Y. Wan, and S. Warnick, "Initialcondition estimation in network synchronization processes: Graphical characterizations of estimator structure and performance," in Proceedings of the AIAA Guidance, Navigation and Control Conference, Portland, 2011.
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.
J. Fax and R. M. Murray, "Information flow and cooperative control of vehicle formations," IEEE Transactions on Automatic Control, 2004.
R. Olfati-Saber, "Distributed Kalman filtering for sensor networks," in Proceeding of the IEEE Conference on Decision and Control, 2007.
D. Spanos, R. Olfati-Saber and R. M. Murray, "Dynamic consensus for mobile networks," IFAC World Congress, 2005.
M. Zhu and S. Martinez, "On discrete-time dynamic average consensus," Automatica, 2010.
W. Ren, "Consensus seeking in multi-vehicle systems with a timevarying reference state," in Proceeding of American Control Conference, 2007.
R. Freeman, P. Yang and K. M. Lynch. "Stability and convergence properties of dynamic average consensus estimators," in Proceeding of the IEEE Conference on Decision and Control, 2006.
A. Olshevsky and J. N. Tsitsiklis, "Convergence speed in distributed consensus and averaging." SIAM Journal on Control and Optimization, 2009.
A. Olshevsky and J. N. Tsitsiklis, "A lower bound on distributed averaging," in Proceedings of IEEE Conference on Decision and Control, 2010.
H. Zhang, M. Chen, G. Stan, T. Zhou and J. Maciejowski, "Collective behavior coordination with predictive mechanisms," IEEE Circuits and Systems Magazine, 2008.
J. Cortes, "Finite-time convergent gradient flows with applications to network consensus," Automatica, 2006.
L. Wang and F. Xiao, "Finite-time consensus problems for networks of dynamic agents," IEEE Transactions on Automatic Control, 2010.
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 minimaltime distributed consensus," in Proceedings of IEEE Conference on Decision and Control, 2009.
Y. Yuan, G. Stan, L. Shi, M. Barahona and J. Goncalves, " Decentralised minimal time consensus," accepted, Automatica, 2012.
Y. Yuan, "Decentralised prediction and reconstruction algorithms," Ph.D. Thesis, University of Cambridge, 2012.
L. Xiao and S. Boyd, "Fast linear iterations for distributed averaging," System and control letter, 2004.
Vincent D. Blondel, Julien M. Hendrickx and John N. Tsitsiklis, "Continuous-time average-preserving opinion dynamics with opiniondependent communications," SIAM Journal on Control and Optimization, 2010.
K. Zhou, J. Doyle and K. Glover, "Robust and Optimal Control," Prentice Hall, 1996.
J. Partington, "An introduction to Hankel operators," Cambridge University Press, 1988.
S. Rump, "Structured perturbations part I: Normwise distances," SIAM Journal of Matrix Analysis, Application, 2003.
M. Hitz, "On computing the nearest singular Hankel matrices," Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2005.
R. Olfati-Saber, "Distributed Kalman filter with embedded consensus filters," in Proceedings of IEEE Conference on Decision and Control, 2005.
R. Olfati-Saber and J. S. Shamma, "Consensus filters for sensor networks and distributed sensor fusion," in Proceedings of IEEE Conference on Decision and Control, 2005.
M. Cao, A. S. Morse, and B. D. O. Anderson, "Agreeing asynchronously," IEEE Transactions on Automatic Control, 2008.
