Distributed Consensus Protocols in Adaptive Multi-Agent Systems

Abstract

The analysis of noisy consensus dynamics in networks is of great interest to both advance the fundamental understanding of multi-agent systems in nature as well as create robust decentralized engineering systems. We develop a protocol that heuristically attempts to optimize metrics of consensus dynamics without explicitly measuring a network’s global properties. Adopting the approach of utility maximization by nodes in a network, we allow nodes to modify connections with their neighbors over time. This results in a locally adaptive network: the global graph structure updates through the collective action of local changes, and no node has any knowledge of this evolution beyond its effects on the node’s local environment. Our research focuses specifically on developing the form of this utility function to (heuristically) optimize network performance with respect to noisy consensus dynamics. Beginning with a utility function inspired by economic and sociological models for network behavior, our analysis discovers the importance of coupling state and network dynamics to enhance consensus performance. Consequently, we develop the "perceived intelligence" coupling factor which creates a positive feedback between the state dynamics and network structure: nodes gravitate towards smart individuals who appear to be close to the final consensus state. Results indicate that this feedback reduces overshoot in the state dynamics and improves the convergence speed and robustness of consensus, but it induces heavy oscillations in network structure as individuals swing between smart indiviuals. Therefore, we sophisticate the model by introducing "intelligence history," a recursive estimation scheme for perceived intelligence that dampens the positive feedback, thereby reducing swings in network structure. With the addition of perceived intelligence and intelligence history, our protocol greatly outperforms the original utility model, especially when network costs are taken into account in the metrics of consensus performance. Overall, the protocol appears to be a very capable heuristic for maximizing consensus performance in the presence of noise, and it is easily adaptable to a variety of applications.