Perpetual Exploration of a 3D Grid by Luminous Autonomous Robots

12/04/2022 - Anaïs DURAND, Maîtresse de conférences
Anaïs DURAND

We consider swarms of luminous autonomous robots. These robots are myopic (i.e., they cannot see beyond some visibility range), do not have a global compass yet they agree on a common chirality, and run in synchronous Look-Compute-Move cycles. They must rely on their lights with few colors to communicate.

In this context, we study the problem of perpetually exploring a 3D grid. We show that assuming the optimal visibility range one, three robots are necessary and sufficient to solve the problem. We propose such an algorithm requiring five colors. Then, we propose an algorithm that is optimal in terms of colors. The solution we propose works with oblivious robots, i.e., robots endowed with only one light color. This second solution requires five robots and visibility range two.

Simulations: Algorithm 1 and Algorithm 2