Soutenance de thèse : Mihai-Ioan POPESCU

Static and Dynamic Multi-Robot Routing with Periodic Connectivity Maintenance, Patrolling and Network Data Delivery

Doctorant : Mihai-Ioan POPESCU

Laboratoire INSA : CITI

Ecole doctorale : ED512 Informatique Et Mathématiques de Lyon

Cette thèse aborde premièrement les problématiques du routage multi-robots (MRR) et des scénarios dynamiques de MRR (définis comme DMRR dans la thèse), où le besoin de solutions décentralisées avec des temps efficaces est requis pour pour des applications réelles. Les solutions de l'état de l'art sont confrontées à des problèmes de temps de fonctionnement ou à de mauvaises performances lorsqu'elles sont étendues à des scénarios de grande taille, par exemple avec des dizaines de robots et des centaines de cibles. Nous formalisons le problème MRR en intégrant les contraintes de saturation des coûts en proposant MRR-Sat et DMRR-Sat et en montrant qu’ils sont NP-difficiles pour différents fonctions objectifs. Nous proposons une approche par enchères parallèles à plusieurs tours (PMR) qui introduit des degrés de parallélisme variables dans l'allocation des tâches des robots. Nous évaluons empiriquement et théoriquement les performances de solutions, à l’aide de scénarios expérimentaux et de preuves de complexité. Deux autres solutions sont proposées pour les scénarios dynamiques (DMRR), qui utilisent les principes de PMR. Une approche similaire d’évaluation, par expérimentation et preuve est proposée. La troisième partie de la thèse examine le problème de la patrouille multi- robot de groupes de cibles. Nous développons une heuristique dans le cadre CBSC (Covering with Bounded Simple Cycles) qui permet de prendre en compte des limites énergétiques des robots. La quatrième partie de la thèse se concentre sur le problème du maintien de la connectivité dans le réseau de robots qui exécutent la tâche de patrouille. Nous proposons des algorithmes efficaces qui peuvent maintenir la connectivité intermittente ou périodique de la flotte de robots, afin d'assurer la communication entre robots et l’acheminement des données collectées à une station finale. Enfin, un simulateur d'agents mobiles est développé dans le cadre de ce travail afin de faciliter la visualisation et l'étude des algorithmes.