Multi-Agent Consensus
Consensus protocols drive a network of agents to agree on a common value using only communication with neighbors.
Agreeing locally
Consensus is the problem of getting many agents, each with its own initial value, to converge to a common quantity while each communicates only with a few neighbors. It is the building block of distributed coordination: formation, synchronization, distributed averaging, and load sharing all reduce to variants of consensus. The elegance is that global agreement emerges from purely local interactions.
The graph Laplacian
Model the communication network as a graph and form its Laplacian matrix L. The standard continuous protocol sets each agent's rate of change to the negative Laplacian times the state vector, so each agent moves toward the average of its neighbors. The dynamics x-dot equals minus L x converge to consensus if and only if the graph contains a spanning tree, meaning information can reach every agent from some root. The consensus value for an undirected connected graph is the average of the initial values.
Rate and robustness
How fast consensus is reached is governed by the algebraic connectivity, the second-smallest eigenvalue of the Laplacian, known as the Fiedler value. A larger Fiedler value means faster convergence. Directed graphs, time-varying topologies where links come and go, and communication delays all complicate the analysis, but consensus persists as long as the union of graphs over time remains sufficiently connected.
- Agents converge using only neighbor information
- Dynamics x-dot equals minus L x, L the graph Laplacian
- Convergence requires a spanning tree in the graph
- Fiedler eigenvalue sets the convergence rate
Consensus generalizes to leader-follower schemes, where agents track a designated leader, and to formation control, where each agent maintains an offset from the consensus point. These are the basis of coordinated multi-machine and swarm control.
For a design-stage network of coordinating subsystems, consensus protocols would synchronize distributed quantities using only local links, evaluated in simulation. It is the cooperative core of distributed control.