Consensus Protocols

Consensus protocols [1] have become a widely popular engineering tool for distributed coordination of multi-agent systems. Not only they have many practical applications, such as sensor fusion and synchronization of coupled oscillators, but also have been applied as a mathematical tool in solving a distributed optimization problem and distributed control over networks. The goal of a consensus protocol is such that the state of each agent in the network converges to a common point. In order to achieve this goal, the connectivity of the agents in the network plays an important role. It has been shown in the literature that under a certain level of connectivity, the objective can actually be achieved.

For some distributed optimization problems, each agent actually must be able to obtain a common optimal decision [2,3]. This can be achieved by implementing the consensus protocol as a part of the distributed algorithm. In our work [4,5], we also exploit the consensus approach as an information-exchange protocol for distributed model predictive control schemes. In this regard, we can actually relax the necessary communication requirement and allow some level of communication failures.

In this simulation, we introduce the standard consensus protocol over a fixed communication network. Let the network of a multi-agent system be described by an undirected and fixed graph \(G = (N,E)\), where \(N\) denotes the set of agents, i.e., \(N = \{1,2, \dots \}\) and \(E\) denotes the set of communication links, i.e., \((i,j) \in E\) means that agents \(i\) and \(j\) can communicate with each other. In this regard, denote the set of neighbors of agent \(i\) by \(N_i\), i.e., \(N_i = \{j: (i,j) \in E\}\). Let \(x_i\) be the state of agent \(i\). Then, the standard consensus protocol [1] is stated as follows:

\[\begin{aligned} \frac{dx_i}{d t} = \sum_{j \in N_i} \left(x_j - x_i \right) \end{aligned}\]

for all \(i \in N\). We suppose that there are four agents in the network and these agents are initially started at a different position in a two-dimensional Euclidean space. Throughout this simulation, we can observe the behavior of these agents when the above consensus protocol is applied. To that end, please follow the following instructions.

  1. Prior to pressing Play, please choose the communication network for the system. We provide three different choices, which can be selected by sliding the bar on the top. Note that we intentionally do not provide a description of the network so that we can analyze it from the behavior of the agents.
  2. Press Play and observe the movement of the agents. Do they all move to the same position?
  3. Press Pause and then reposition all agents randomly by dragging and dropping them. Can you guess what is the common point that the agents achieve? You might check the plots of the horizontal and vertical positions if needed.
  4. Try steps 1-3 for all three networks and analyze the differences in the behavior of the agents. Under which networks the convergence to a common point is achieved? Which network has the fastest convergence? Can you guess which network has more connectivity?


[1] R. Olfati-Saber and R. M. Murray, "Consensus and cooperation in networked multi-agent systems," Proceedings of the IEEE, vol. 95, No. 1, pp. 215-233, 2007.

[2] A. Nedić, A. Ozdaglar, and P. A. Parrilo, "Constrained consensus and optimization in multi-agent networks," IEEE Transactions on Automatic Control, vol. 55, no. 4, pp. 922-938, 2010.

[3] A. Nedić and A. Olshevsky, "Distributed optimization over time-varying directed graphs," IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601-615, 2015.

[4] W. Ananduta, J. Barreiro-Gomez, C. Ocampo-Martinez, and N. Quijano, "Resilient information-exchange protocol of distributed model predictive control Schemes," in Proceedings of American Control Conference, Milwaukee, USA, 2018, pp. 1286-1291.

[5] W. Ananduta, J. Barreiro-Gomez, C. Ocampo-Martinez, and N. Quijano, "Mitigation of communication failures in distributed model predictive control strategies," IET  Control Theory and Applications, vol. 12, no. 18, pp. 2507-2515, 2018.

image image image

Consensus Protocols - A virtual Lab by Wicak Ananduta