This research project is about the analysis and sinthesis of complex systems obtained interconnecting a large number
of simple dynamical systems. The central point is the emergence, at the level of the interconnected system, of
evolution patterns absent in the simple local systems. In other terms, we are experiencing complexity as the product of
interconnection. Such structure show up in various scientific and technological areas:
(a) in 'sensor networks' as distributed estimation algorithms where each sensor has access to a
limited local amount of information and can exchange data with its neighbors.
A prototypical problem in this setting is
the so called 'consensus' where the agents seek syncronization, namely the achievement of a
common estimated value; in the case when such value is the
average of the local estimation available by each single agent, we talk about 'average consensus'.
(b) in multi-agent systems (robots or other unmanned vehicles) which are supposed to achieve a common goal
(rendezvous, formation, flocking). Their individual
dynamics are coupled through a communication graph obtaining in this way an interconnected dynamical system. Collected behaviors
of such systems are similar to those observable in biological systems: swarms of birds,
(c) as models to study particular 'attributes'in social networks: opinion dynamics, leader election,...
1. Scalable algorithms for consensus.
In spite of the huge literature on this argument (see item (a) above),
there still remain fundamental problems open. One of these is to determine the minimal complexity of consensus, namely
the minimal number of transmissions needed by a local and distributed algorithm on a given graph of n agents,
to achieve consensus
(or, better, to get up to a threshold from consensus). If the communication graph is a ring, the avilable algorithms yield a complexity
of n squared, while on a bidimensional grid, the complexity is n to the 3/2. Is it possible to improve? Our conjecture
is that it must be possible to obtain algorithms whose complexity grows linearly in the number of agents n, or at most,
with some extra logarithmic factors. Such a reult would be very important in the applications.
The starting point to construct such algorithms could be the well known 'divide et impera' technique:
split the nerwork into subgraphs and make the algorithm operate at the
lower level and then fuse the results at the higher level.
2. Randomized algorithms for consensus.
In many applicative contexts, it is not possible that all agents transmit data simultaneously:
this to avoid collisions and to limit the computations at every node. For this reason,
there are algorithms where each node,
at one instant, receives data from just one neighbor. To obtain fast algorithms however is necessary to
continuously switch
the edge which are used. Random switches are very popular in the literature
since they allow to construct very good algorithms. The most common random algorithms are of two types:
(a) gossip algorithms where, at each time step, a pair of randomly selected agents exchange data;
(b) broadcasting algorithms where, at each time step, a single agent activates and transmits its data to all its neighbors.
The theoretical analysis of these algorithms is not simple: besides the estimation of the convergence speed,
we need also to estimate the displacement of the consensus from the average point.
At the moment there are only partial results in the literature mainly regarding mean square convergence analysis.
Simulations show phenomena that at the moment are not fully understood at a theoretical level
and further effort will be needed to fully understand the asymtptotic behaviors of these schemes.
3. Consensus algorithms under noisy communication channels.
In the applicattion of consensus algorithms over wireless sensor networks, power and, possibly,
bandwith limitations, naturally lead to consider
finite capacity digital transmission channels among the various sensors. As a consequence, this forces quantization at the
level of the transmitted values. Analysis of consensus algorithms under quantization has been partially done in the last few years, in the assumption of
a noiseless channel. The noisy case, extremely important, is, at the present, completely open.
To achieve reliable transmission over such channels, it will be needed to couple the
consensus algorithms with suitable coding/decoding schemes.
In order to maintain an iterative structure in the algorithm, however, we will need to employ convolutional codes
or digital fountain codes coupled with some subotpimal iterative decoding scheme recently considered in the coding theory literature
under the name of message passing algorithms.
4. Consensus versus other distributed estimation problems.
Consensus is probably the simplest distributed estimation problem to be solved on a network.
Many other important estimation problems can be formulated on a network.
Many linear regression problem can be in principle be reduced to a family of consensus problems. If this family is small, consensus algorithms
can be a valid way to solve the problem, however when this family is large, the reduction to consensus is no longer feasible and totally new roads need to be found.
In other cases it is not even possible to reduce the problem to consensus. One important example is the
so-called self-localization problem where the agents need to establish their absolute position on the basis of noisy relative measurements and of some noisy measurements of
the absolute positions.
5. The rendez-vous and other cooperative control problems
under a time-varying communication graph.
In this thesis, we focus on feedback laws for a network of dynamical systems communicating through a varying
network. Variability can be of random type or rather due to the relative positions among the various moving
agents (for instance when each agent can only communicate within a given threshold distance). Even for the problem of
rendezvous under the assumption that each agent exhibits a linear local dynamics,
the asymptotic analysis of such an interconnected system, is far from being completed.