Master 2013 2014
Stages de la spécialité SAR
Exploration d’Environnement par un Essaim de roBOTs mobiles


Site :Exploration d’environnement par un essaim de robots mobiles
Lieu :LIP6 4 place Jussieu PARIS
Encadrant : Franck Petit et Sébastien Tixeuil
Dates :du 01/04/2014 au 31/08/2014
Rémunération :oui, gratification standard
Mots-clés : Parcours SAR autre qu’ATIAM, rech./prof.

Description

Nous considérons une cohorte de robots dotés d’actionneurs de mouvements et de capteurs visuels, mais incapables de communiquer explicitement entre eux. Les robots évoluent par cycles qui comprennent chacun des phases d’observation, de calcul et de déplacement. Au cours d’un cycle, un robot observe son environnement, puis basé sur cette observation, le robot décide d’une destination (éventuellement sa position courante) vers laquelle il se déplace. Les robots ont des capacités très faibles : ils sont anonymes (ils n’ont aucun moyen de se distinguer l’un de l’autre), uniformes (ils exécutent tous le même protocole), amnésiques (leur mémoire volatile s’efface entre deux cycles), et ne savent pas s’orienter (et ne savent pas s’accorder sur une direction ou une orientation commune). Ils se déplacent dans un environnement constitué d’un ensemble fini de lieux reliés entre eux par des passages destinés à la circulation. On représente naturellement ce genre d’environnement par un graphe dont les nœuds représentent les lieux et les arêtes la possibilité pour un robot de se déplacer d’un lieu à un autre.

Nous nous intéressons au problème de l’exploration avec arrêt consistant à faire en sorte que k robots initialement situés sur des nœuds différents puissent explorer entièrement un anneau constitué de n nœuds sans qu’aucune paire d’entre eux ne se puisse se retrouver sur un même nœud. Cette dernière restriction s’applique notamment lorsque les contraintes physiques des robots, comme leur volume, les empêchent physiquement d’occuper le même espace à plusieurs.

L’objet du stage est de déterminer la classe des configurations initiales pour lesquelles le problème est insoluble en fonction de n et de k, puis de tenter de proposer un algorithme déterministe fonctionnant à partir des configurations exclues de cette classe.