Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality - Archive ouverte HAL Access content directly
Conference Papers Year :

Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality

(1) , (2) , (3)
1
2
3

Abstract

We consider swarms of luminous myopic opaque robots that run in synchronous Look-Compute-Move cycles. These robots have no global compass, but agree on a common chirality. In this context, we propose optimal solutions to the perpetual exploration of a finite grid. Precisely, we investigate optimality in terms of the visibility range, number of robots, and number of colors. In more detail, under the optimal visibility range one, we give an algorithm which is optimal w.r.t. both the number of robots and colors: it uses two robots and three colors. Under visibility two, we design two algorithms: the first one uses three robots with an optimal number of colors (i.e., one), the second one achieves the best trade-off between the number of robots and colors, i.e., it uses two robots and two colors.
Fichier principal
Vignette du fichier
BDL21.pdf (543.28 Ko) Télécharger le fichier
Vignette du fichier
ICDCN2021-video.mp4 (72.79 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03130277 , version 1 (03-02-2021)

Licence

Attribution - NonCommercial - NoDerivatives - CC BY 4.0

Identifiers

Cite

Quentin Bramas, Pascal Lafourcade, Stéphane Devismes. Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality. International Conference on Distributed Computing and Networking, 2021, Nara, Japan. ⟨10.1145/1122445.1122456⟩. ⟨hal-03130277⟩
75 View
124 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More