Vous êtes ici : GIPSA-lab > Formation > Thèses soutenues
Chargement
TRAN Thi Minh Dung

” Méthodes distribuées pour la conception de protocoles de consensus de moyenne en temps fini, l'évaluation de la robustesse et la reconstruction de la topologie des réseaux de systèmes multi-age

 

Directeur de thèse :     Alain KIBANGOU     Carlos CANUDAS-DE-WIT

École doctorale : Electronique, electrotechnique, automatique, traitement du signal (eeats)

Spécialité : Automatique et productique

Structure de rattachement : UJF

Établissement d'origine : Autre

Financement(s) : bourse attribuée par un gouvernement étranger ; vacations ; vacations

 

Date d'entrée en thèse : 16/01/2012

Date de soutenance : 26/03/2015

 

Composition du jury :
M. Alessandro GIUA Professeur, Université d'Aix-Marseille (France), Rapporteur
M. Jean-Marie GORCE Professeur, INSA Lyon (France), Rapporteur
M. Christian COMMAULT Professeur, Université Grenoble Alpes (France), Examinateur
M. Walid HACHEM Directeur de recherche CNRS, Telecom Paris Tech (France), Examinateur
M. Antoine GIRARD Maitre de conférences HDR, Université Grenoble Alpes (France), Examinateur
M. Fabio MORBIDI Maitre de conférences, Université de Picardie Jules Verne (France), Examinateur
M., Alain KIBANGOU Maitre de conférences, Université Grenoble Alpes (France), Co-encadrant

 

Résumé : Durant la dernière décennie, une attention considérable a été consacrée au consensus des systèmes multi-agents. Le consensus est un processus coopératif dans lequel les agents interagissent afin de parvenir à un accord. La plupart des études ont été orientées vers l'analyse en régime permanent de ce processus d'agrément. Or, durant le régime transitoire, les algorithmes de consensus à convergence asymptotique génèrent un grand nombre de données. Dans cette thèse, notre objectif est d'exploiter ces données afin de concevoir des protocoles de consensus de moyenne en temps fini, d'évaluer la robustesse du graphe, et reconstituer la topologie du réseau de manière distribuée. Le consensus de moyenne en temps fini garantit un temps d'exécution minimal qui peut assurer l'efficacité et la précision des algorithmes distribués complexes dans lesquels il est utilisé comme sous-composante. En considérant des réseaux d'agents modélisés avec des graphes connexes non orientés, nous formulons ce problème comme étant un problème de factorisation de la matrice de moyenne (matrice ayant tous ses éléments égaux à 1/N, N étant le nombre de nœuds du réseau). Puisque, les objets communicants doivent apprendre leur environnement avant d'établir des liens de communication, nous suggérons l'utilisation de séquences d'apprentissage afin de résoudre ce problème de factorisation formulé comme un problème d'optimisation non convexe sous contrainte. Nous montrons que tout minimum local de la fonction de coût génère une factorisation exacte de la matrice de moyenne. En contraignant les matrices facteurs à être dépendante de la matrice Laplacienne du graphe, la résolution de la factorisation de la matrice de moyenne de manière distribuée permet d'estimer le spectre de la matrice Laplacienne. Ce spectre peut être utilisé pour calculer des indices de robustesse (Nombre d'arbres couvrant et résistance effective du graphe, aussi appelé indice de Kirchhoff). La seconde partie de la thèse est donc consacrée à l'évaluation de la robustesse du réseau via l'estimation distribuée du spectre du Laplacien. Le problème est posé comme étant un problème de consensus sous contrainte. Une première approche conduit à un problème d'optimisation non-convexe résolu de manière distribuée au moyen de la méthode des multiplicateurs de Lagrange. Une seconde approche, obtenue après une reparamétrisation adaptée, conduit à un problème d'optimisation convexe résolu en utilisant l'algorithme du sous-gradient et la méthode de direction alternée des multiplicateurs (ADMM). Grâce à une programmation linéaire en nombres entiers, la méthode proposée permet en sus de déterminer les multiplicités des valeurs propres. Enfin, connaissant les valeurs propres de la matrice Laplacienne, nous montrons comment reconstruire la topologie du réseau via l'estimation décentralisée des vecteurs propres. Nous considérons particulièrement le cas où certains nœuds sont anonymes.


GIPSA-lab, 11 rue des Mathématiques, Grenoble Campus BP46, F-38402 SAINT MARTIN D'HERES CEDEX - 33 (0)4 76 82 71 31