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

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〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00933714
Contributeur : Franck Petit <>
Soumis le : mardi 21 janvier 2014 - 06:57:17
Dernière modification le : jeudi 22 novembre 2018 - 14:17:16

Identifiants

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〉

Partager

Métriques

Consultations de la notice

176