Brief Announcement: Ring Exploration by Oblivious Robots With Vision Limited to 2 or 3

3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We consider the deterministic terminating exploration in an anonymous, unoriented ring using asynchronous, oblivious, and myopic robots. By myopic, we mean that robot vision is limited within a certain distance $\phi$, computed in terms of hops. In~\cite{DLLP13}, it is shown that exploration is impossible with asynchronous settings if $\phi = 1$, {i.e.}, if the vision is limited to its own and its immediate neighboring nodes. In this paper, we study the cases where the robot visibility is limited to $2$ and $3$ neighboring nodes, respectively. In the former case, we propose two deterministic solutions in the asynchronous model for $7$ and $9$ robots. The first solution works starting from specific configurations while the other one works on any initial configuration. In the latter case, we show that no exploration is possible with less than $5$ robots. We then propose two asynchronous solutions that solve the problem using respectively $5$ and $7$ robots. The former works starting from specific configurations. The latter works for any initial configuration.
Type de document :
Communication dans un congrès
15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2013, Nov 2013, Osaka, Japan. Springer Berlin / Heidelberg, 8255, pp.363-366, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-319-03089-0_31〉

https://hal.inria.fr/hal-00933714
Contributeur : Franck Petit <>
Soumis le : mardi 21 janvier 2014 - 06:57:17
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Citation

Ajoy Datta, Anissa Lamani, Lawrence Larmore, Franck Petit. Brief Announcement: Ring Exploration by Oblivious Robots With Vision Limited to 2 or 3. 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2013, Nov 2013, Osaka, Japan. Springer Berlin / Heidelberg, 8255, pp.363-366, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-319-03089-0_31〉. 〈hal-00933714〉

Métriques

Consultations de la notice