Un jour sans fin

International audienceCet article est un résumé de travaux portant sur l'exploration exclusive perpétuelle d'une grille finie par un petit nombre de robots aux capacités faibles. Ces robots sont opaques, sans orientation commune et ont une vision à portée limitée. Cependant, ils savent distinguer leur droite de leur gauche, exécutent le même algorithme de manière synchrone et sont équipés de lumières avec un nombre réduit de couleurs. Mise à part cette lumière, les robots n'ont aucune mémoire permanente et aucun moyen de communiquer. Par ailleurs, les couleurs de leurs lumières constituent l'unique moyen de les distinguer. Dans ce cadre, nous étudions l'optimalité en termes de portée, de nombre de robots et de couleurs utilisées. En supposant une portée optimale (1 saut), nous proposons un algorithme optimal en nombre de robots (2) et de couleurs (3). Nous donnons deux autres algorithmes pour une portée à deux sauts : l'un utilise 3 robots et une seule couleur (l'optimal) ; l'autre réalise le meilleur compromis entre le nombre de robots (2) et le nombre de couleurs (2)