Afficher la notice abrégée

Gathering of Robots on Anonymous Grids without multiplicity detection

hal.structure.identifierUniversity of L'Aquila [Italy] [UNIVAQ]
hal.structure.identifierAlgorithms, simulation, combinatorics and optimization for telecommunications [MASCOTTE]
dc.contributor.authorD'ANGELO, Gianlorenzo
hal.structure.identifierUniversity of L'Aquila [Italy] [UNIVAQ]
dc.contributor.authorDI STEFANO, Gabriele
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierDipartimento di Matematica e Informatica [Perugia] [DMI]
dc.contributor.authorNAVARRA, Alfredo
dc.date.accessioned2024-04-15T09:44:41Z
dc.date.available2024-04-15T09:44:41Z
dc.date.issued2012-06-30
dc.date.conference2012-06-30
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197867
dc.description.abstractEnThe 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.
dc.language.isoen
dc.publisherSpringer
dc.title.enGathering of Robots on Anonymous Grids without multiplicity detection
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-31104-8_28
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.page327-338
bordeaux.volume7355
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.title19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012)
bordeaux.countryIS
bordeaux.conference.cityReykjavík
bordeaux.peerReviewedoui
hal.identifierhal-00728988
hal.version1
hal.invitednon
hal.proceedingsoui
hal.conference.end2012-07-02
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00728988v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2012-06-30&rft.volume=7355&rft.spage=327-338&rft.epage=327-338&rft.au=D'ANGELO,%20Gianlorenzo&DI%20STEFANO,%20Gabriele&KLASING,%20Ralf&NAVARRA,%20Alfredo&rft.genre=unknown


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée