6 September 2012, h.10:00 - Room 201 DEI/A

Abstract:

In the context of the wide interest in automatic coordination and "consensus" algorithms in the last decade, we have shown that complex features can appear when the agents evolve on a nonlinear state space, like the sphere. In this talk we quickly review the setup and examples of such nonlinear consensus algorithms. Then we comment on the possible complexity of equilibria reached by agents that evolve on such a nonlinear space by interacting according to a fixed undirected graph. In particular, we consider agents on the projective space of Rk, which links to the algorithmic problem of graph k-coloring. It is thereby shown that characterizing stable equilibria of repulsive agents on the projective space can be as difficult as graph coloring, that is NP-hard for k > 2. The Bell-Kochen-Specker Theorem developed in the context of quantum systems, implies that unfortunately the converse reasoning does not help: letting a swarm of repulsive agents reach a globally stable equilibrium, does not necessarily solve graph coloring.

Biography:

Alain Sarlette is a lecturer on dynamical systems engineering at Ghent University, Belgium. He has an engineering degree in applied physics (2005) and a PhD in dynamical systems modeling and control (2009), both from the University of Liège, Belgium. He has been a visiting researcher at Ecole des Mines de Paris (Prof.P.Rouchon), at Princeton University (Prof.N.Leonard) and at the European Space Agency. His research interests include the control and analysis of multi-agent systems, quantum systems, and nonlinear systems in general.