Master 2012 2013
Stages de la spécialité SAR
Exploration d’environnement par une équipe de gros robots


Lieu :LIP6, 4 place Jussieu 75005 PARIS
Encadrant : Franck Petit et Sébastien Tixeuil
Dates :Du 02/04/2013 au 01/09/2013
Rémunération :env. 420 euros nets par mois
Mots-clés : Parcours SAR autre qu’ATIAM, recherche


Warning: Illegal string offset 'id_auteur' in /dsk/www-master/html/2012/ecrire/public/assembler.php(625) : eval()'d code on line 3
Cliquer ici pour vous authentifier


Warning: Illegal string offset 'statut' in /dsk/www-master/html/2012/ecrire/public/assembler.php(625) : eval()'d code on line 1

Warning: Illegal string offset 'id_auteur' in /dsk/www-master/html/2012/ecrire/public/assembler.php(625) : eval()'d code on line 2

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 le nombre minimal de robots nécessaire à la résolution du problème et de proposer un algorithme déterministe atteignant (ou se rapprochant de) ce nombre.

franck.petit@lip6.fr pour toute question complémentaire.