Qualitative and quantitative graph-theoretic aspects of convergence to consensus

Abstract:

We consider in this talk the asymptotic evolution of time-varying multi-agent systems. As an example, consider the following finite-dimensional discrete-time linear equation \begin{equation} \label{equa} x(t+1) = A(t) x(t),\quad t=0,1,\dots \end{equation} Here, the $n$-dimensional vector $x(t)$ gathers the states of the $n$ so-called ``agents", and the real $n\times n$ matrices $A(t)$ are assumed to be {\em row stochastic}, so the components of the state $x(t+1)$ are obtained as {\em averages\/} of {\em some\/} of the components of the present state $x(t)$. This is quite different from the usual situation in Control theory, when one is looking for asymptotic stability of the zero equilibrium of (\ref{equa}). Indeed here, the vector whose every component is equal to 1 is an eigenvector for any stochastic matrix $A(t)$, associated to the eigenvalue 1: accordingly, the origin of (\ref{equa}) cannot be asymptotically stable. This eigenvector spans the so-called {\em consensus subspace} $\{x\ :\ x_1=\cdots = x_n\}$. We are precisely interested here in studying the issue of {\em consensus}, that is convergence to this latter subspace. Historically appearing in the areas of communication networks, control theory, and parallel computation, similar questions arise in peer-to-peer and sensors networks, in the maneuvring of groups of vehicles, in the study of transmission control protocol (TCP) protocols, in the theory of coupled oscillators, in neural networks, but also in apparently distant fields such as the study and modeling of opinion in social science, and of animal flocking. Our aim is to bring home ``what is necessary to have consensus", and ``what is not". It turns out that the way the information can travel inside the agent population is primordial. As a matter of fact, this explains why the assumptions related to consensus are in general naturally expressed with notions borrowed from graph theory. In particular, the existence of {\em spanning trees} appears as central, for time-invariant graph topologies, but also for time-varying ones. We will also show how introducing quantitative informations in this description (``weights" adequately defined on the spanning trees) allows to obtain estimates of the speed of convergence towards consensus.

Biography:

Pierre-Alexandre Bliman graduated from Ecole Polytechnique in 1986 (Promotion X83) and from Ecole Nationale Sup\'erieure de Techniques Avanc\'ees in 1988. In 1990 he received the PhD degree in ``Math\'ematiques et Automatique'' from the Universit\'e Paris IX-Dauphine. In 2005 he was awarded the ``Habilitation \`a diriger des recherches" from Universit\'e Paris XI-Orsay. Since 1991, he is researcher at INRIA. His research interests include control of oscillations, delay systems, robust control, control of networks of dynamical systems and modeling and control of energy conversion systems, including fuel cell systems.