Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

2.33.1 Coordination dans les réseaux multi-agents (24h, 3ECTS)

Responsable : Olivier Bournez, Professeur, École polytechnique.

Équipe pédagogique :

Édition 2016-2017 :

Le cours est donné par Bernadette Charron-Bost le lundi de 8h45 à 11h45 au Batiment Sophie Germain (P7), salle 2035. La première séance a lieu le 19 septembre.

Langue : français ou en anglais selon la demande ; documentation en anglais.

Objectif

Les phénomènes de coordination et de synchronisation dans un grand nombre de systèmes physiques ou biologiques (synchronisation d'oscillateurs couplés, vol groupé d'oiseaux, synchronisation de lucioles ou encore diffusion de rumeurs) sont modélisés par des algorithmes de consensus. Du fait de leur grande robustesse et adaptabilité, ces algorithmes naturels peuvent être avantageusement utilisés pour la conception de systèmes multi-agents artificiels (fusion de données dans un réseau de capteurs, protocoles de répartition dynamique de charge, contrôle de groupes de robots ou encore rendez-vous spatiaux).

L'objectif de ce cours est d'étudier la calculabilité et la complexité du problème du consensus dans un système d'agents qui interagissent à travers un réseau dynamique. Nous étudierons plus particulièrement le cas des systèmes d'influence où le graphe de communication (ou d'influence) est une fonction de l'état du système et qui permettent de modéliser certains comportement collectifs en dynamique d'opinion ou en biologie.

Plan du cours

Consensus dans les réseaux multi-agents

  • Problème du consensus et algorithmes de moyenne
  • Analyse matricielle et chaines de Markov
  • Consensus dans les modèles de réseaux dynamiques
  • Consensus dans le cas d'interactions bidirectionnelles

Propriétés et applications

  • Complexité en temps et vitesse de convergence
  • Robustesse des algorithmes de moyenne ; consensus quantifié
  • Asynchronisme des interactions
  • Applications

Systèmes d'influence

  • Définition ; cas des systèmes diffusifs
  • Modèle de Hegselmann-Krause en dynamique d'opinions
  • Modèle de Cucker-Smale-Vicsek pour l'étude du flocking

Pré-requis

Notions de base en algèbre linéaire, théorie des graphes et en algorithmique distribuée.

Notes de cours et exercices

Notes de cours :

  1. Sur le théorème de Perron-Frobenius : chapter1.pdf
  2. Sur le théorème de Moreau : chapter2.pdf
  3. Sur les vitesses de convergence : vitesse.pdf

Articles :

  • Bernard Chazelle, Natural Algorithms and Influence Systems, CACM, vol. 55(12).

Feuilles d'exercices et devoir :

Messages :

  • Le premier cours a lieu le lundi 19 septembre.
  • Devoir à rendre le 17 novembre (fichier dm16.pdf).
  • Pas de cours le lundi 31 octobre.

Bibliographie

  • Dimitri P. Bertsekas and John N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1997.
  • Bernard Chazelle. Natural Algorithms and Influence Systems. Communications of the ACM, vol. 55(12), december 2012.
  • Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
  • Luc Moreau. Stability of Multiagent Systems With Time-Dependent Communication Links, IEEE Transactions on Automatic Control, Vol. 50(2), february 2005.
  • Shlomo Sternberg. Dynamical Systems. Dover Publications. 2010.

Cours reliés

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA