Robot Searching and Gathering on Rings under Minimal Assumptions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Robot Searching and Gathering on Rings under Minimal Assumptions

Résumé

Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring. They operate on the basis of the so called \emph{Look}-\emph{Compute}-\emph{Move} cycle. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or to stay idle. In the first case, it performs the computed move, eventually. The computation also depends on the required task. In this paper, we solve both the well-known \emph{Searching} and \emph{Gathering} tasks. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a full characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.
Nous considérons un ensemble de robots mobiles qui sont placés sur distincts sommets d'un réseau en anneau. Le réseau est anonyme et les robots ont des aptitudes minimales. Ils opérent par des cycles \emph{Observer}-\emph{Calculer}-\emph{Bouger}. Nous résolvons les problémes de la réunion et du nettoyage de graphe dans ce modéle.
Fichier principal
Vignette du fichier
RR-8250.pdf (1000.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00794921 , version 1 (26-02-2013)

Identifiants

  • HAL Id : hal-00794921 , version 1

Citer

Gianlorenzo d'Angelo, Alfredo Navarra, Nicolas Nisse. Robot Searching and Gathering on Rings under Minimal Assumptions. [Research Report] RR-8250, INRIA. 2013. ⟨hal-00794921⟩
266 Consultations
137 Téléchargements

Partager

Gmail Facebook X LinkedIn More