Reaching a Consensus in a Dynamically Changing Environment:A Graphical Approach

This paper presents new graph-theoretic results appropriate for the analysis of a variety of consensus problems cast in dynamically changing environments. The concepts of rooted, strongly rooted, and neighbor-shared are defined, and conditions are derived for compositions of sequences of directed graphs to be of these types. The graph of a stochastic matrix is defined, and it is shown that under certain conditions the graph of a Sarymsakov matrix and a rooted graph are one and the same. As an illustration of the use of the concepts developed in this paper, graphtheoretic conditions are obtained which address the convergence question for the leaderless version of the widely studied Vicsek consensus problem. Key words. cooperative control, graph theory, switched systems, multiagent system