Skip to Main content Skip to Navigation
Conference papers

Un jour sans fin

Résumé : Cet 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).
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03205279
Contributor : Stéphane Devismes Connect in order to contact the contributor
Submitted on : Thursday, September 16, 2021 - 5:40:41 PM
Last modification on : Monday, November 15, 2021 - 2:56:02 PM

File

algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03205279, version 2

Citation

Stéphane Devismes, Pascal Lafourcade. Un jour sans fin. ALGOTEL 2021 — 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2021, La Rochelle, France. ⟨hal-03205279v2⟩

Share

Metrics

Record views

37

Files downloads

28