Ring Exploration with Myopic Luminous Robots

Abstract We investigate exploration algorithms for autonomous mobile robots evolving in uniform ring-shaped networks. Different from the usual Look-Compute-Move (LCM) model, we consider two characteristics: myopia and luminosity. Myopia means each robot has a limited visibility. We consider the weakest assumption for myopia: each robot can only observe its neighboring nodes. Luminosity means each robot maintains a non-volatile visible light. We consider the weakest assumption for luminosity: each robot can use only two colors for its light. The main interest of this paper is to clarify the impact of luminosity on exploration with myopic robots. As a main contribution, we characterize the minimum number of myopic robots to achieve perpetual and terminating exploration in the fully synchronous (FSYNC), semi-synchronous (SSYNC), and asynchronous (ASYNC) models; we prove that (i) in the FSYNC model, two myopic robots are necessary and sufficient to achieve perpetual exploration, and three myopic robots are necessary and sufficient to achieve terminating exploration, and (ii) in the SSYNC and ASYNC models, three myopic robots are necessary and sufficient to achieve perpetual exploration, and four myopic robots are necessary and sufficient to achieve terminating exploration. These results clarify the power of lights for myopic robots since, without lights, five myopic robots are necessary and sufficient to achieve terminating exploration in the FSYNC model, and no terminating exploration algorithm exists with myopic robots in the SSYNC and ASYNC models. We also show that, in the FSYNC model (resp., the SSYNC and ASYNC models), the proposed perpetual exploration algorithm is universal, that is, the algorithm solves perpetual exploration from any solvable initial configuration with two (resp., three) myopic robots and two colors. On the other hand, we show that, in the FSYNC model (resp., the SSYNC and ASYNC models), no universal algorithm exists for terminating exploration, that is, no algorithm may solve terminating exploration from any solvable initial configuration with three (resp., four) myopic robots and two colors.