Consensus on nonlinear spaces and graph coloring

Giovedi' 6 Settembre 2012 - Alain Sarlette


Giovedi' 6 Settembre 2012, alle 10:00 in sala riunioni 201 del DEI/A, il Dr. Alain Sarlette terra' un seminario dal titolo "Consensus on nonlinear spaces and graph coloring".

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.

-Short Bio
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.

Rif. int. P. Dai Pra

NEWS: New Second Level Degree in Data Science - Second cycle degree - a. y. 2017/18 X