Optimal torus exploration by oblivious robots

Stéphane Devismes (1) , Anissa Lamani (2) , Franck Petit (3) , Sébastien Tixeuil (4)

1 VERIMAG - IMAG - VERIMAG
2 MIS - Modélisation, Information et Systèmes - UR UPJV 4290
3 DELYS - DistributEd aLgorithms and sYStems
4 NPA - Networks and Performance Analysis

We deal with a team of autonomous robots that are endowed with motion actuators and visibility sensors. Those robots are weak and evolve in a discrete environment. By weak, we mean that they are anonymous, uniform, unable to explicitly communicate, and oblivious. We first show that it is impossible to solve the terminating exploration of a simple torus of arbitrary size with less than 4 or 5 such robots, respectively depending on whether the algorithm is probabilistic or deterministic. Next, we propose in the SSYNC model a probabilistic solution for the terminating exploration of torus-shaped networks of size ℓ×L, where 7≤ℓ≤L, by a team of 4 such weak robots. So, this algorithm is optimal w.r.t. the number of robots.

Mots clés: Robot; Torus; Exploration; Obliviousness; Robots; Obliviouness

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Stéphane Devismes, Anissa Lamani, Franck Petit, Sébastien Tixeuil. Optimal torus exploration by oblivious robots. Computing, 2019, 101 (9), pp.1241-1264. ⟨10.1007/s00607-018-0595-8⟩. ⟨hal-02420598⟩