Ring Exploration by Oblivious Robots with Vision Limited to 2 or 3

The problem of exploring a finite discrete space by autonomous mobile robots is a basic building block for many applications. Space to explore is partitioned into a finite number of locations represented by a graph, where nodes represent indivisible locations that can be sensed by the robots, and where edges represent the possibility for a robot to move from one location to the other. %, e.g., a building, a town, a factory, or a mine. We address the terminating exploration problem which requires that starting from a configuration where no two robots occupy the same node, every node needs to be visited by at least one robot, with the additional constraint that all robots eventually stop moving.

Authors and Affiliations

1. School of Computer Science, University of Nevada Las Vegas, USA

   Ajoy K. Datta & Lawrence L. Larmore

2. MIS, Université de Picardie Jules Verne Amiens, France

   Anissa Lamani

3. LIP6, INRIA, CNRS, UPMC Sorbonne Universities, France

   Franck Petit

Editors and Affiliations

1. Graduate School of Information Science and Technology, Osaka University, Yamadaoka 1-5, 565-0871, Suita, Osaka, Japan

   Teruo Higashino

2. Nagoya Institute of Technology, Gokiso-cho Showa, 466-8555, Nagoya, Japan

   Yoshiaki Katayama

3. Graduate School of Information Science and Technology, Osaka University, Japan

   Toshimitsu Masuzawa

4. LIP6, University Paris 6, Paris, France

   Maria Potop-Butucaru

5. Kyushu University, Fukuoka, Japan

   Masafumi Yamashita

Reprints and permissions

© 2013 Springer International Publishing Switzerland

Policies and ethics