Responsable : Olivier Bournez, Professeur, École polytechnique.

Équipe pédagogique :

• Olivier Bournez (Professeur à l'École polytechnique, LIX)
• Bernadette Charron-Bost (Directrice de Recherche CNRS, LIX)
• Sylvain Perifel (Maître de Conférence Université Paris 7, LIAFA)

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.

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.

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

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

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).

• Luc Moreau, Stability of Multiagent Systems With Time-Dependent Communication Links, IEEE Transactions on Automatic Control, Vol. 50(2), february 2005

Feuilles d'exercices et devoir :

1. surete.pdf
2. dm16.pdf

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

• 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.

• 2-8-1 Théorie non-séquentielle des systèmes distribués
• 2-17-1 Fondements sur la modélisation des réseaux
• 2-18-1 Algorithmique distribuée pour les réseaux
• 2-18-2 Algorithmique distribuée avec mémoire partagée
• 2-19 Méthodes informatiques pour la biologie systémique et synthétique
• 2-29-1 Algorithmique des graphes