Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-03657044
Contributeur : Quentin Bramas Connectez-vous pour contacter le contributeur
Soumis le : mercredi 4 mai 2022 - 13:34:13
Dernière modification le : lundi 27 juin 2022 - 16:54:40

Fichier

Exploration perp_e-accent-aigu...
Fichiers produits par l'(les) auteur(s)

Identifiants

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⟩

Partager

Métriques

Consultations de la notice

72

Téléchargements de fichiers

13