Gathering of Robots on Anonymous Grids without multiplicity detection
International audience The paper studies the gathering problem on grid networks. A team of robots placed at different nodes of a grid, have to meet at some node and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupie...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , , , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2012
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-00728988 https://hal.inria.fr/hal-00728988/document https://hal.inria.fr/hal-00728988/file/main.pdf https://doi.org/10.1007/978-3-642-31104-8_28 |
id |
ftunivnantes:oai:HAL:hal-00728988v1 |
---|---|
record_format |
openpolar |
institution |
Open Polar |
collection |
Université de Nantes: HAL-UNIV-NANTES |
op_collection_id |
ftunivnantes |
language |
English |
topic |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
spellingShingle |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] d'Angelo, Gianlorenzo Di Stefano, Gabriele Klasing, Ralf Navarra, Alfredo Gathering of Robots on Anonymous Grids without multiplicity detection |
topic_facet |
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
description |
International audience The paper studies the gathering problem on grid networks. A team of robots placed at different nodes of a grid, have to meet at some node and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids. In particular, we show that in this case, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of a structure like the grid that allows to overcome the multiplicity detection with respect to the ring case. |
author2 |
University of L'Aquila Italy (UNIVAQ) Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) Inria Sophia Antipolis - Méditerranée (CRISAM) Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA) Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE) Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Dipartimento di Matematica e Informatica Perugia (DMI) Università degli Studi di Perugia = University of Perugia (UNIPG) |
format |
Conference Object |
author |
d'Angelo, Gianlorenzo Di Stefano, Gabriele Klasing, Ralf Navarra, Alfredo |
author_facet |
d'Angelo, Gianlorenzo Di Stefano, Gabriele Klasing, Ralf Navarra, Alfredo |
author_sort |
d'Angelo, Gianlorenzo |
title |
Gathering of Robots on Anonymous Grids without multiplicity detection |
title_short |
Gathering of Robots on Anonymous Grids without multiplicity detection |
title_full |
Gathering of Robots on Anonymous Grids without multiplicity detection |
title_fullStr |
Gathering of Robots on Anonymous Grids without multiplicity detection |
title_full_unstemmed |
Gathering of Robots on Anonymous Grids without multiplicity detection |
title_sort |
gathering of robots on anonymous grids without multiplicity detection |
publisher |
HAL CCSD |
publishDate |
2012 |
url |
https://hal.inria.fr/hal-00728988 https://hal.inria.fr/hal-00728988/document https://hal.inria.fr/hal-00728988/file/main.pdf https://doi.org/10.1007/978-3-642-31104-8_28 |
op_coverage |
Reykjavík, Iceland |
geographic |
Reykjavík |
geographic_facet |
Reykjavík |
genre |
Iceland Reykjavík Reykjavík |
genre_facet |
Iceland Reykjavík Reykjavík |
op_source |
19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012) https://hal.inria.fr/hal-00728988 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Jun 2012, Reykjavík, Iceland. pp.327-338, ⟨10.1007/978-3-642-31104-8_28⟩ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-31104-8_28 hal-00728988 https://hal.inria.fr/hal-00728988 https://hal.inria.fr/hal-00728988/document https://hal.inria.fr/hal-00728988/file/main.pdf doi:10.1007/978-3-642-31104-8_28 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-642-31104-8_28 |
container_start_page |
327 |
op_container_end_page |
338 |
_version_ |
1766041483227430912 |
spelling |
ftunivnantes:oai:HAL:hal-00728988v1 2023-05-15T16:51:22+02:00 Gathering of Robots on Anonymous Grids without multiplicity detection d'Angelo, Gianlorenzo Di Stefano, Gabriele Klasing, Ralf Navarra, Alfredo University of L'Aquila Italy (UNIVAQ) Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE) Inria Sophia Antipolis - Méditerranée (CRISAM) Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED) Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) Université Nice Sophia Antipolis (1965 - 2019) (UNS) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA) Laboratoire Bordelais de Recherche en Informatique (LaBRI) Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE) Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) Dipartimento di Matematica e Informatica Perugia (DMI) Università degli Studi di Perugia = University of Perugia (UNIPG) Reykjavík, Iceland 2012-06-30 https://hal.inria.fr/hal-00728988 https://hal.inria.fr/hal-00728988/document https://hal.inria.fr/hal-00728988/file/main.pdf https://doi.org/10.1007/978-3-642-31104-8_28 en eng HAL CCSD Springer info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-31104-8_28 hal-00728988 https://hal.inria.fr/hal-00728988 https://hal.inria.fr/hal-00728988/document https://hal.inria.fr/hal-00728988/file/main.pdf doi:10.1007/978-3-642-31104-8_28 info:eu-repo/semantics/OpenAccess 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012) https://hal.inria.fr/hal-00728988 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), Jun 2012, Reykjavík, Iceland. pp.327-338, ⟨10.1007/978-3-642-31104-8_28⟩ [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] info:eu-repo/semantics/conferenceObject Conference papers 2012 ftunivnantes https://doi.org/10.1007/978-3-642-31104-8_28 2023-02-08T00:24:19Z International audience The paper studies the gathering problem on grid networks. A team of robots placed at different nodes of a grid, have to meet at some node and remain there. Robots operate in Look-Compute-Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move towards one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids. In particular, we show that in this case, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of a structure like the grid that allows to overcome the multiplicity detection with respect to the ring case. Conference Object Iceland Reykjavík Reykjavík Université de Nantes: HAL-UNIV-NANTES Reykjavík 327 338 |