A unified approach for different tasks on rings in robot-based computing systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

A unified approach for different tasks on rings in robot-based computing systems

Résumé

A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the famous CORDA distributed computing model where the robots cannot communicate but can perceive the positions of other robots. More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in Look-Compute-Move asynchronous cycles. Moreover, robots are anonymous, oblivious, uniform and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. In this setting, we devise algorithms that, starting from any exclusive rigid (i.e. aperiodic and asymmetric) configuration, solve the three above mentioned problems in anonymous ring-topologies. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem.
Fichier principal
Vignette du fichier
RR-8013.pdf (643.57 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00716761 , version 1 (11-07-2012)

Identifiants

  • HAL Id : hal-00716761 , version 1

Citer

Gianlorenzo d'Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse, Karol Suchan. A unified approach for different tasks on rings in robot-based computing systems. [Research Report] RR-8013, INRIA. 2012. ⟨hal-00716761⟩
187 Consultations
215 Téléchargements

Partager

Gmail Facebook X LinkedIn More