Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Wednesday, July 11, 2012 - 11:24:35 AM
Last modification on : Saturday, June 25, 2022 - 11:07:51 PM
Long-term archiving on: : Friday, October 12, 2012 - 2:31:19 AM


Files produced by the author(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⟩



Record views


Files downloads