Linear Consensus Algorithms: Structural Properties and Connections with Markov Chains

Nous considérons un réseau d'agents multiples en interaction, et tel que chaque agent est supposé posséder un état concernant une certaine quantité d'intérêt. Selon le contexte, les états d'agents peuvent correspondre à des opinions, des valeurs, des estimés, des croyances, des positions, des vitesses, etc. Ces états sont mis à jour selon un algorithme ou protocole qui consiste en une règle d'interaction dictant la manière par laquelle les états d'un agent donné influencent ou sont influencés par ceux de ses voisins. Les voisins sont définis à partir d'un graphe sous-jacent de communication, ce dernier évoluant dans le temps de manière soit endogène ou exogène. Un consensus du système est défini comme la convergence de tous les états vers une valeur commune, lorsque le temps croît indéfiniment. La notion de consensus apparaît dans de multiples domaines de recherche. En biologie, le consensus est lié aux comportements émergents d'un ensemble d'oiseaux en vol, des bancs de poissons, etc. En robotique et en automatique, les problèmes de consensus se présentent lorsque l'on cherche à réaliser la coordination et la coopération d'agents mobiles (ex. robots et capteurs). Cette question est particulièrement importante dans la mise en réseau de capteurs avec nombreuses applications, soit en contrôle de l'environnement, ou dans un contexte militaire. En économie, la recherche de consensus par rapport à un mécanisme commun d'ajustement des prix constitue un autre exemple. En sociologie, l'émergence d'une langue commune dans une société primitive est un comportement collectif au sein d'un système complexe. Un autre comportement limite d'intérêt dans un système est celui où les états, plutôt que de converger vers une seule valeur, se fractionnent en groupes distincts, avec des limites communes dans le groupe mais distinctes d'un groupe à l'autre. Un tel comportement est appelé dans notre thèse, consensus multiple. Dans cette thèse, nous adressons deux objectifs de recherche en relation avec le comportement asymptotique des états d'agents dans un système multi-agent, possédant une dynamique mise à jour via un algorithme distribué de calcul de moyenne, de caractère général, en temps continu ou discret. Le premier objectif visé est celui de l'identification de conditions aussi faibles que possible, pour lesquelles le consensus unique ou multiple est garanti inconditionnellement, c'est-à-dire pour toute valeur du temps initial ou encore des valeurs initiales attribuées aux états. Contrairement au premier objectif centré sur la recherche de convergence inconditionnelle, notre second objectif de recherche est celui de l'identification d'ensembles particuliers de conditions initiales, non triviales toutefois, pour lesquelles un consensus global est possible.

Abstract

We consider a network of multiple interacting agents, whereby each agent is assumed to hold a state regarding a certain quantity of interest. Depending on the context, states may be referred to as opinions, values, estimates, beliefs, positions, velocities, etc. Agent states are updated based on an algorithm or protocol which is an interaction rule specifying the manner in which individual agent states influence and are influenced by neighboring states. Neighbors are defined via an underlying exogenously or endogenously evolving communication graph. Consensus in the system is defined as convergence of all states to a common value, as time grows large. The notion of consensus arises in many research areas. In biology, consensus is linked with the emergent behavior of bird flocks, fish schools, etc. In robotics and control, consensus problems arise when seeking coordination and cooperation of mobile agents (e.g., robots and sensors). This is, particularly, an important issue in sensor networking with wide applications in environmental control, military applications, etc. In economics, seeking an agreement on a common belief in a price system is another example of consensus. In sociology, the emergence of a common language in primitive societies is a collective behavior within a complex system. Another important limiting behavior of the system is one whereby agents, instead of all converging to the same value, separate into multiple clusters with a uniform limiting value within each cluster. Such behavior, in this thesis, is called multiple consensus. In this thesis, we address two research objectives relating to the asymptotic behavior of agent states in a multi-agent system, with dynamics updated via a general distributed averaging algorithm in either continuous time or discrete time. The first issue is that of identifying conditions, as weak as possible, under which consensus or multiple consensus is guaranteed to occur unconditionally, i.e., irrespective of the time or values that states are initialized at. In contrast to the first research objective centered on unconditional consensus, our second research objective is that of identifying sets of particular, yet non-trivial, initial agent conditions such that global consensus occurs. In particular, we are interested in characterizing so-called eminence grise coalitions (EGC): An EGC is a possibly small group of individuals in the network who are, “naturally”, capable of leading the whole group to eventually agree on any desired value, by only choosing their own initial values properly. What is meant by “naturally” is that the group in question does not need to manipulate the nature of the network, and in particular, leaves all the interactions between any two individuals including members of the group themselves untouched. They could be thought of as hidden leaders, not specifically identifiable by title or position, but who hold the potential of perfectly influencing the asymptotic behavior of individuals in the network. In investigating EGCs in a network of opinions, the size of its smallest EGC is the main focus of our analysis.