Consensus Problems on Small World Graphs: A Structural Study

Pedram Hovareshti and John S. Baras

Number: ISR TR 2006-10, Year: 2006, Advisor: John S. Baras

Abstract

Consensus problems arise in many instances of collaborative control of multi-agent complex systems; where it is important for the agents to act in coordination with the other agents. To reach coordination, agents need to share information. In large groups of agents the information sharing should be local in some sense, due to energy limitation, reliability, and other constraints. A consensus protocol is an iterative method that provides the group with a common coordination variable. However, local information exchange limits the speed of convergence of such protocols. Therefore, in order to achieve high convergence speed, we should be able to design appropriate network topologies. A reasonable conjecture is that the small world graphs should result in good convergence speed for consensus problems because their low average pairwise path length should speed the diffusion of information in the system. In this paper we address this conjecture by simulations and also by studying the spectral properties of a class of matrices corresponding to consensus problems on small world graphs.