Rendez-vous avec un lapin

Overview & Synopsis

Nous nous intéressons à une version du problème du rassemblement de robots mobiles où certains d'entre eux peuvent poser un lapin aux autres. Étant donné un ensemble de robots mobiles : si aucun des robots ne tombe en panne alors tous les robots doivent se rassembler à la même position, non connue à l'avance, en un temps fini. Si un, ou plusieurs robots tombe(nt) en panne à la même position (et posent donc un lapin aux autres), alors tous les autres robots encore en fonction doivent se rassembler à la même position que ceux qui sont en panne. Motivés par les résultats d'impossibilité dans le cadre semi-synchrone, nous présentons dans ce papier, le premier algorithme résolvant le problème dans un environnement synchrone, en supposant le modèle vision-calcul-déplacement, sans hypothèses supplémentaires : les robots sont amnésiques, désorientés, ne peuvent pas détecter de multiplicité, et peuvent commencer leur exécution à n'importe quelle position (y compris celles avec des points de multiplicité).