Seminar Details
2016-05-10 (14:00) : Gossip Coverage Control for Robotic Networks: Dynamical Systems on the Space of Partitions
At Euler building (A002)
Organized by Mathematical Engineering
Speaker :
Carli, Ruggero
Abstract :
Future applications in environmental monitoring, delivery of
services and transportation of goods motivate the study of deployment
and partitioning tasks for groups of autonomous mobile agents. These
tasks are achieved by recent coverage algorithms, based upon the
classic methods by Lloyd. These algorithms however rely upon critical
requirements on the communication network: information is exchanged
synchronously among all agents and long-range communication is
sometimes required. In this talk we discusses novel coverage
algorithms that require only gossip communication, i.e., asynchronous,
pairwise, and possibly unreliable communication. Which robot pair
communicates at any given time may be selected deterministically or
randomly. A key innovative idea is describing coverage algorithms for
robot deployment and environment partitioning as dynamical systems on
a space of partitions. In other words, we study the evolution of the
regions assigned to each agent rather than the evolution of the
agents positions. The proposed gossip algorithms are shown to
converge to centroidal Voronoi partitions under mild technical
conditions. Our treatment features a broad variety of results in
topology, analysis and geometry. First, we establish the compactness
of a suitable space of partitions with respect to the symmetric
difference metric. Second, with respect to this metric, we establish
the continuity of various geometric maps, including the Voronoi
diagram as a function of its generators, the location of a centroid as
a function of a set, and the widely-known multicenter function studied
in facility location problems. Third, we prove two convergence
theorems for dynamical systems on metric spaces described by
deterministic and stochastic switches.
We conclude the talk by proposing possible extensions of this novel
approach to other communication protocols, like asynchronous gossip
and asynchronous broadcast. A short discussion is devoted also to the
case where the multicenter function dictating the coverage is unknown
and possibly time-varying; in this scenario we combine the coverage
algorithms to estimation procedures which pair Gaussian processes
regression with Kalman filtering techniques.