Skip to Main content Skip to Navigation
Conference papers

Exploration perpétuelle : ça s'en va et ça revient

Résumé : Cet article traite de l'exploration perpétuelle d'une grille par un petit nombre de robots ayant des capacités très limitées. Ces robots ont une vision à portée bornée, sont désorientés (ils n'ont pas de système de coordonnées commun), et ne savent pas distinguer leur droite de leur gauche. Ils exécutent le même algorithme de manière synchrone et sont équipés de lumières capables de changer de couleur. En outre, chaque robot dispose d'un panel réduit de couleurs et ces couleurs constituent les seules informations pouvant être mémorisées par le robot et capturées par les robots alentour. Dans ce cadre restreint, on souhaite que les robots visitent infiniment souvent et de manière exclusive chaque noeud d'une grille. Notre but est de trouver des solutions mobilisant le moins de ressources possibles. En supposant une portée de 1, nous proposons un algorithme utilisant seulement 3 robots et nous prouvons que ce nombre est optimal. Nous avons aussi élaboré un algorithme utilisant seulement une couleur (optimalité en nombre de couleurs). Ce dernier fonctionne avec 5 robots et suppose une portée de visibilité à distance 2. Cette hypothèse a été montrée nécessaire dans un article précédent.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03657044
Contributor : Quentin Bramas Connect in order to contact the contributor
Submitted on : Wednesday, May 4, 2022 - 1:34:13 PM
Last modification on : Friday, August 5, 2022 - 2:54:52 PM

File

Exploration perp_e-accent-aigu...
Files produced by the author(s)

Identifiers

Citation

Arthur Rauch, Quentin Bramas, Stéphane Devismes, Pascal Lafourcade, Anissa Lamani. Exploration perpétuelle : ça s'en va et ça revient. AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France. pp.1-4, ⟨10.5281/zenodo.4640462⟩. ⟨hal-03657044v2⟩

Share

Metrics

Record views

113

Files downloads

19