BOURNAT Marjorie

doctorant à Sorbonne Université
Équipe : DELYS
https://lip6.fr/Marjorie.Bournat

Direction de recherche : Franck PETIT

Co-encadrement : DUBOIS Swan, DIEUDONNÉ Yoann

Dégradation progressive et spéculation pour les robots dans des environnements hautement dynamiques

Les systèmes distribués sont des systèmes composés de plusieurs processus communiquants et coopérants ensemble pour résoudre des tâches communes. C’est un modèle générique pour de nombreux systèmes réels comme les réseaux sans fil ou mobiles, les systèmes multiprocesseurs à mémoire partagée, etc. D’un point de vue algorithmique, il est reconnu que de fortes hypothèses (comme l’asynchronisme ou la mobilité) sur de tels systèmes mènent souvent à des résultats d’impossibilité ou à de fortes bornes inférieures sur les complexités. Dans cette thèse, nous étudions des algorithmes qui s’auto-adaptent à leur environnement (i.e., l’union de toutes les hypothèses sur le système) en se concentrant sur les deux approches suivantes. La dégradation progressive contourne les résultats d’impossibilité en dégradant les propriétés offertes par l’algorithme lorsque l’environnement devient fort. La spéculation contourne les bornes inférieures élevées sur les complexités en optimisant l’algorithme seulement sur les environnements les plus probables.
Les réseaux de robots représentent un cas particulier des systèmes distribués où les processus, dotés de capteurs, sont capables de bouger d’une localisation à une autre. Nous considérons des environnements dynamiques dans lesquels cette capacité peut évoluer avec le temps. Cette thèse répond positivement à la question ouverte de savoir s’il est possible et bénéfique d’appliquer les approches progressivement dégradante et spéculative aux réseaux de robots dans des environnements dynamiques. Cette réponse est obtenue en étudiant le rassemblement (où tous les robots doivent se retrouver à la même localisation en temps fini) progressivement dégradant et l’exploration perpétuelle (où les robots doivent visiter infiniment souvent chaque localisation) spéculative.

Soutenance : 27/06/2019

Membres du jury :

Ralf Klasing, Directeur de recherche CNRS au LaBRI [Rapporteur]
Roger Wattenhofer, Full Professor at Swiss Federal Institute of Technology in Zurich [Rapporteur]
Lélia Blin, Maîtresse de conférences (HDR) à Sorbonne Université
Sylvie Delaët, Maîtresse de conférences (HDR) à Université Paris Sud
Carole Delporte, Professeure des universités à Université Paris Diderot
Yoann Dieudonné, Maître de conférences à l'Université de Picardie Jules Verne
Swan Dubois, Maître de conférences à Sorbonne Université
Franck Petit, Professeur des universités à Sorbonne Université

Date de départ : 31/08/2019

Publications 2015-2019