Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots. (17th March 2020)

• Record Type: Journal Article
• Authors: Devismes, Stéphane; Lamani, Anissa; Petit, Franck; Raymond, Pascal; Tixeuil, Sébastien
• Is Part Of: Computer journal. Volume 64:Number 1(2021)
• Page Start: 132
• Page End: 154
• Publication Date: 2020-03-17
• Subjects: oblivious robots -- terminating exploration -- finite discrete space -- grid; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz166
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\bf(2, 2)$ -Grid (resp. a $\bf(3, 3)$ -Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\bf(2, 2)$ -Grid and five for the $\bf(3, 3)$ -Grid, respectively.