Consensus based approaches for distributed estimation, optimization and control

The problem of reaching a consensus, i.e., driving the state of systems interacting in a network to a common value, has many interesting applications and has recently received much attention within the control community. Consensus is reached through a local interaction rule between the interconnected systems that may require a synchronous updating, or an asynchronous updating based on gossip or broadcast communications. The objective of this talk is to review some consensus based approaches recently proposed by the Automatic Control group of the University of Cagliari. These approaches address different problems in a distributed setting, such as such as estimation of network properties, averaging, and load balancing. The emerging behavior of a multi-agent system is strictly related to the topology of the underlying network, which in turn is related to the spectrum of the Laplacian matrix of the network graph. In the first part of the talk, a decentralized algorithm to estimate the Laplacian eigenvalues is presented. The basic idea is to provide a local interaction rule among agents so that their state trajectory is a linear combination of sinusoids oscillating only at frequencies corresponding to the eigenvalues of the Laplacian matrix. In this way, the problem of decentralized estimation of the eigenvalues is mapped into a standard signal processing problem. In the second part of the talk two extensions of the classical consensus algorithm are presented. One extension concerns discrete consensus under gossip communications. In quantized consensus the state of the agents takes discrete values. This setting can be extended to encompass the more general problem of load balancing of discrete tasks of different size over a set of heterogeneous processors. To solve this problem the notion of swap, i.e., an exchange of tasks between agent that does not balance the load, is fundamental to avoid local minima of the objective function. A new deterministic swapping rule that- greatly reduces the expected time to reach consensus will be discussed. Another extension concerns a new decentralized discontinuous interaction rule which allows to synchronize a network of agents with first-order dynamics. The topology of the network is described by a strongly connected directed graph, and the agents dynamics are perturbed by additive and uniformly bounded uncertain timevarying disturbances. The proposed interaction rule completely rejects the effects of the disturbances by providing the achievement of consensus after a finite transient time which can be arbitrarily reduced by increasing a scalar control parameter.