Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots

Autor: Pascal Raymond, Franck Petit, Sébastien Tixeuil, Stéphane Devismes, Anissa Lamani
Přispěvatelé: VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Networks and Performance Analysis (NPA), LIP6, VERIMAG [2016-2019] (VERIMAG - IMAG [2016-2019]), Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology [2007-2019] (Grenoble INP [2007-2019])-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)
Rok vydání: 2020
Předmět:
Normalization property
Theoretical computer science
Corda Model
General Computer Science
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[SCCO.COMP]Cognitive science/Computer science
Context (language use)
0102 computer and information sciences
02 engineering and technology
Exploration problem
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
[INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing
[INFO.INFO-MC]Computer Science [cs]/Mobile Computing
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Oblivious Robots
0202 electrical engineering
electronic engineering
information engineering
[INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO]
Grid
Probabilistic logic
010201 computation theory & mathematics
Asynchronous communication
Robot
020201 artificial intelligence & image processing
Exploration
[INFO.INFO-DC]Computer Science [cs]/Distributed
Parallel
and Cluster Computing [cs.DC]
Zdroj: The Computer Journal
The Computer Journal, Oxford University Press (UK), 2021, The Computer Journal, 64 (1), pp.132-154. ⟨10.1093/comjnl/bxz166⟩
The Computer Journal, Oxford University Press (UK), 2020, ⟨10.1093/comjnl/bxz166⟩
The Computer Journal, 2021, The Computer Journal, 64 (1), pp.132-154. ⟨10.1093/comjnl/bxz166⟩
ISSN: 1460-2067
0010-4620
DOI: 10.1093/comjnl/bxz166
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: