Fagnani Fabio

Homepage


Distributed estimation and cooperative control in large scale networks




A thesis on this topic?

PhD fellowship on this topic?




Estimation in large scale networks is a fundamental research topic with a broad variety of technological applications: environmental monitoring, logistics, search, surveillance just to mention few. It has stimulated challenging theoretical problems which are attracting, particularly in North America, the intellectual energies of outstanding mathematicians, computer scientists, and electrical engineers. Two types of networks we have in mind: networks of sensors, small sensing devices deployed in some environment, or networks consisting of mobile autonomous vehicles like robots or other unmanned vehicles. The basic technological assumption is that these agents have limited resources for computing and transmitting data and these activities should be kept as low as possible. On the other hand, the tasks which the network is deputed to can not be accomplished at a local level and in general require a cooperative action of the various agents. These networks are going to play an increasingly important role in theWestern societies of 21th century. The technology to construct them already essentially exists, but a big gap remains in the project of the algorithms needed to make them accomplish tasks in the desired cooperative way.

A general problem that the agents of a network have to solve is to estimate some desired quantities given a probabilistic model of the environment and a set of observed measurements. Measures of close agents are typically correlated and is exactly to exploit this fact that the agents need to cooperate in order to achieve the global optimal estimation.

The simplest of these estimation problems is the so-called 'average consensus problem' which is when all sensors measure (with noise) the same physical quantity: the best linear unbiased estimator in this case consists in averaging the various measures. The average consensus problem consists in finding distributed iterative algorithms implementing this solution. In spite of the efforts devoted to this problem, there are still fundamental unanswered questions related to this problem: the available algorithms which are local and distributed, fail to be scalable, since they need to converge a number of total transission in the network which grows in general in a superlinear way with the number of agents (this means that the amount of energy consumed by each agent is going in the average to grow in the number of agents). Are there scalable local distributed algorithms for consensus? Another key point is to be able to develop a theory to cope with more realistic assumptions on the networks. One of these is that the transmission channels among the various agents are finite capacity and noisy: in this case there is not yet a single theoretical result.

The main goal of this project is to deepen the investigation of the average consensus problem and also to attack new distributed inferential problems over large scale networks like sensor calibration, self-localization, source localizations, tracking of time-varying quantities. Our main goal is to construct scalable algorithms.

In cooperative control agents are supposed to performe some feedback control action on the basis of their internal state information and the information received from their neighbors. The graph topology gives fundamental constraints on the type of closed loop behavior which the overall dynamical system can achieve. Design of control laws to achieve certain objectives is in general a challenging problem. A particular interesting situation is when we are assuming the agents to be mobile and the control goal to be defined in terms of their positions and velocities. The rendez-vous problem is when all the agents want to meet in a point and is mathematically analogous to the consensus problem described above. There is however a variant of this problem which has no counterpart in the corresponding estimation problem: it is when the agents are, realistically, assumed to be able to transmit to other agents exclusively within a certain threshold distance R (geometric communication graph). In this case, the graph topology is time-varying in a way that is coupled to the dynamics of the agents. The overall system is in this case non-linear and quite difficult to be analyzed. Only partial convergence results are available in this context. Variation of the rendez-vous problems are also quite interesting: in the so-called flocking, for instance, we want to enforce a rendez-vous of velocities and, beside this, the stabilization of agents interdistances to certain design values. Flocking phenomena seem to happen in nature as a coordination feature of swarming birds or other groups of animals.


Specific research topics:

1. Analysis of random average consensus algorithms: gossip algorithms, broadcasting algorithms, deterministic algorithms in a random environment (noisy transmissions, quantization effects, packet drops, nodes failures).

2.Consensus algorithms over finite capacity channels (binary erasure channels, binary symmetric channels). Encoding strategies using versions of digital fountain codes

3. Design of local, distributed, scalable algorithms over large scale networks for the average consensus problem.

4. Analysis of linear distributed estimation problems different from consensus Self-localization, source localization and tracking problems.

5. Analysis of rendez-vous algorithms under a geometric graph. Flocking.

Publications:

R. Carli, P. Frasca, F. Fagnani, S. Zampieri, Gossip consensus algorithms via quantized communication., submitted, 2009.

P. Frasca, R. Carli, F. Fagnani, S. Zampieri, Average consensus on networks with quantized communication, Int. J. Robust and Nonlinear Control, 2008. In press. doi: 10.1002/rnc.1396

F. Fagnani, S. Zampieri, Average consensus with packet drop communication, SIAM J. on Control and Opt., to appear, 2008.

F. Fagnani, S. Zampieri, Randomized consensus algorithms over large scale networks, IEEE J. on Selected Areas of Communications, 26 (4), pp. 634-649, 2008.

R. Carli, F. Fagnani, A. Speranzon, S. Zampieri, Communication constraints in the average consensus problem, Automatica 44 (3), pp. 671-684, 2008.

Conference papers

P. Frasca, R. Carli, F. Fagnani, S. Zampieri. Average consensus by gossip algorithms with quantized communication. Proceedings of CDC'08, Cancun, Mexico, Dec. 9-11, pp. 4831-4836, 2008.

R. Carli, F. Fagnani, P. Frasca, S. Zampieri. The quantization error in the average consensus problem. Proceedings of MED'08, Ajaccio, France, June 25-27 , pp. 1592 - 1597, 2008.

C. Canuto, F. Fagnani, P. Tilli, A Eulerian approach to the analysis of rendez-vous algorithms, Proceedings of IFAC2008, Seoul, Korea, July 6-11, pp. 9039-9044, 2008.

F. Fagnani, S. Zampieri, Asymmetric Randomized Gossip Algorithms for Consensus, Proceedings of IFAC2008, Seoul, Korea, July 6-11, pp. 9052-9056, 2008.

R. Carli, F. Fagnani, P. Frasca, S. Zampieri, A probabilistic analysis of the average consensus algorithm with quantized communication, Proceedings of IFAC2008, Seoul, Korea, July 6-11, pp 8062-8067, 2008.

R. Carli, F. Fagnani, P. Frasca, T. Taylor, and S. Zampieri, Average consensus on networks with transmission noise or quantization, Proceedings of the European Control Conference, 2007.

F. Fagnani and S. Zampieri. Randomized consensus algorithms over large scale networks. In Proceedings Information Theory and Application Workshop, San Diego, Jan. 29-Feb. 2 2007, pp. 150-159, 2007.

F. Fagnani, R. Speranzon, S. Zampieri, Communication constraints in coordinated consensus problems, American Control Conference 2006, 14-16 June 2006, 6 pp, 2006.

R. Carli, F. Fagnani, M. Focoso, R. Speranzon, S. Zampieri, Symmetries in the coordinated consensus problem, NESC Networked embedded sensing and control, Lecture Notes in Control and Inform. Sci., 331, Springer, Berlin, pp.25-51, 2006.

R. Carli, F. Fagnani, S. Zampieri, On the state agreement with quantized information, Proceedings of MTNS 2006, Kyoto, pp.1500-1508, 2006.

F. Fagnani, K.H. Johansson, R. Speranzon, S. Zampieri, On multi-vehicle rendezvous under quantized communication, MTNS 2004, Leuven, papernumber:384.pdf, 2004.