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

Abstract : 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.
Type de document :
[Research Report] RR-8013, INRIA. 2012
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

Contributeur : Nicolas Nisse <>
Soumis le : mercredi 11 juillet 2012 - 11:24:35
Dernière modification le : jeudi 11 janvier 2018 - 16:04:42
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 02:31:19


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00716761, version 1



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〉



Consultations de la notice


Téléchargements de fichiers