Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

https://hal.uca.fr/hal-03130277
Contributor : Pascal Lafourcade <>
Submitted on : Wednesday, February 3, 2021 - 2:42:21 PM
Last modification on : Wednesday, February 24, 2021 - 4:24:05 PM

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

74

Files downloads

44