Groupe d’études et de recherche en analyse des décisions

Multi-agent Coordination in a Noisy Environment: Stochastic Consensus and Collective Motion

Minyi Huang The Australian National University, Australie

The recent years have witnessed enormous research efforts on multi-agent coordination, ranging from flocking of birds, synchronization of coupled oscillators, distributed computing, to formation of autonomous vehicles. A common feature of these systems is that the constituent agents need to maintain a certain coordination so as to cooperatively achieve a group objective.

In this context, of fundamental importance is the so-called consensus problem, where consensus means a condition where all the agents individually adjust their own value for a key parameter (e.g., the headings of a group of unmanned aerial vehicles) so as to converge to a common value. In networked consensus problems, each agent's state is updated (either synchronously or asynchronously) by forming a convex combination of the states of its neighbours and itself, and most existing works assumed exact state exchange between neighbouring agents. In this setup, the overall vector of all individual states evolves according to a product of stochastic matrices, and Markov chain techniques provide a powerful tool for analysis.

However, in many practical models, the exact state transmission to other agents is unrealistic, and measurement noises may occur, for instance, due to communication channels. Such noisy modelling has attracted the interest of many researchers, and the design of consensus algorithms is challenging since the well-understood Markov chain based techniques are no longer applicable.

In this research, we develop a stochastic approximation approach for consensus-seeking in a noisy environment. The decreasing step-size in the state recursion will enable cautious learning capability for the agents to reach consensus. In contrast to classical stochastic approximation, the limit states stay in a subspace rather than at a predetermined point due to the specific geometry of the energy level set. For convergence analysis, we will exploit stochastic double array analysis, and develop stochastic Lyapunov analysis based on algebraic graph theory.

In a further step, we examine a coordination scenario for random agents with individual quantitative optimization. We take a simple stochastic differential equation modelling of individual dynamics and consider a leader-follower architecture where experienced agents coordinate with less experienced ones. This leads to a form of hierarchical game formulation and we look for decentralized control strategies using local information. The so-called Nash certainty equivalence methodology, based on a consistency relationship between the individual actions and the group behaviour, will be developed to generate Nash strategies for the agents.