Vers l'infini et au delà

International audienceOn considère le problème de l'exploration d'une grille infinie par un nombre fini de robots. Ces robots ont une visibilité finie et exécutent tous le même algorithme de manière synchrone. Les robots ne possèdent pas de système de coor-données commun, mais sont chiraux (ils savent distinguer leur droite de leur gauche). Les robots possèdent une lumière ayant un nombre fini de couleurs possibles. Misà part cette lumière, les robots n'ont aucune mémoire, aucun moyen de communiquer explicitement et sont anonymes.Évidemment, la couleur de leur lumière est un moyen de se distinguer, pour casser la symétrie et ainsi exécuter des actions différentes. On montre tout d'abord que cinq robots de ce type sont nécessaires et suffisants pour résoudre le problème de l'exploration de la grille infinie. Pour cela, nous prouvons qu'il n'existe pas d'algorithme n'utilisant que quatre robots, quelle que soit leur visibilité (tant qu'elle est finie). Puis nous donnons un algorithme qui fonctionne avec cinq robots, avec des lumières possédant cinq couleurs, et une visibilitéà un saut. Si on se restreintà des robots dont les couleurs ne sont pas modifiables (et toujours avec une visibilitéà un saut), on montre que six robots sont nécessaires et suffisants pour résoudre notre problème