Séminaire (organisé par l’équipe de recherche RO)

Yoan DIEUDONNE

Université de Picardie Jules Verne


Étude de quelques problèmes de coordination de robots autonomes


Mardi 22 juin à 12h en RD134


Résumé :

L’étude de cohortes de robots mobiles coopérant les uns les autres afin d’accomplir une tâche commune, a connu un regain d’attention durant cette dernière décennie. Une des principales raisons de cet engouement est que, pendant longtemps, la tendance a été d’utiliser un seul robot pour effectuer un travail. Force est de constater que de tels robots sont complexes, difficiles à programmer et à construire, et donc très chers. C’est pourquoi la tendance a peu à peu déviée vers des systèmes de plusieurs robots dont les capacités sont très limitées (et donc relativement peu coûteux) mais qui nous permettent facilement de les programmer, de les construire et de les déployer. En dépit de leurs limitations, les robots devraient être capables, ensemble, d’accomplir des tâches non-triviales. En fait, de tels systèmes sont préférables à un seul robot complexe et ce pour de multiples raisons : de moindre coût lorsqu’une unité tombe en panne, capacité à résoudre des tâches autrement impossibles pour une seule entité, la rapidité d’exécution, etc...

Comment bien coordonner des bataillons de robots mobiles, de sorte qu’ils puissent accomplir, ensemble, ce qu’ils sont appelés à faire ? Dans la majeure partie des études, cette question est approché essentiellement d’un point de vue empirique : les algorithmes existant utilisent principalement des heuristiques, et sont ensuite simplement testés soit par l’intermédiaire de simulations, soit sur des robots réels. Aucune preuve de validité et de finitude des solutions n’est proposée. Seules quelques rares études s’intéressent à cet aspect des choses, en se concentrant sur des tâches de bases tels que la formation de motifs, l’élection de leader, la convergence en un point etc... Basiques en apparence, la solvabilité de ces problèmes s’avèrent toutefois être un préalable dans la réalisation de missions plus complexes. Ces mêmes études singulières reposent sur une modélisation primaire des robots dont les principales caractéristiques sont d’êtres homogènes, autonomes, anonymes, sans mémoire et sans médium de communication.

Toutes ces suppositions font de ces robots des agents simples et "stupides" par de nombreux aspects au regard de ce que l’on rencontre habituellement dans la littérature concernant la robotique. Pour autant, ces hypothèses volontairement exagérées permettent de mieux cerner quel panel de fonctionnalités de base un ensemble de robots doit avoir afin d’accomplir une tâche donnée dans un environnement distribué. En d’autres termes, il est possible d’analyser méticuleusement les facteurs influençant la solvabilité de certains problèmes, en vue de déterminer les capacités minimales requises pour l’accomplissement de tel ou tel travail. C’est dans cette philosophie, désignée par l’appellation "approche algorithmique", que s’inscrivent nos travaux.

C’est en adoptant cette démarche, et en passant par des outils et des objets théoriques de la combinatoire des mots tels que les Mots de Lyndon, que nous avons pu caractérisé l’ensemble des classes de motifs pouvant être réalisé par un nombre quelconque de robots. De même nous avons dégagé des conditions nécessaires et suffisantes à la résolution du problème de l’élection d’un leader parmi une cohorte de robots. C’est aussi de cette façon que nous avons pu montré que le problème de la localisation, consistant à déterminer les coordonnées de chaque robot à partir d’un conglomérat de mesures incomplet, n’était pas solvable en pratique puisque NP-Difficile.

Seminars


Mardi 24 octobre 2017

Séminaire à 14h00 en GI042 (Bâtiment Blaise Pascal - UTC) présenté par Richard NELSON, Maître de conférences à l’Université de Waikato à Hamilton (Nouvelle-Zélande).
WAND : Network Research at the University of Waikato.


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS