Robot Searching and Gathering on Rings under Minimal Assumptions

Gianlorenzo d'Angelo 1 Alfredo Navarra 1 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00794921
Contributor : Nicolas Nisse <>
Submitted on : Tuesday, February 26, 2013 - 4:36:32 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Sunday, April 2, 2017 - 5:51:52 AM

File

RR-8250.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00794921, version 1

Collections

Citation

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

Share

Metrics

Record views

513

Files downloads

143