Afficher la notice abrégée

Asynchronous Deterministic Rendezvous in Bounded Terrains

hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorCZYZOWICZ, Jurek
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorILCINKAS, David
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorLABOUREL, Arnaud
hal.structure.identifierDépartement d'Informatique et d'Ingénierie [DII]
dc.contributor.authorPELC, Andrzej
dc.date.accessioned2024-04-15T09:49:14Z
dc.date.available2024-04-15T09:49:14Z
dc.date.issued2010
dc.date.conference2010-06
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198240
dc.description.abstractEnTwo mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots' trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSpringer Berlin / Heidelberg
dc.source.titleProceedings of the 17th International Colloquium on Structural Information and Communication Complexity
dc.subjectmobile agent
dc.subjectrendezvous
dc.subjectdeterministic
dc.subjectpolygon
dc.subjectobstacle
dc.title.enAsynchronous Deterministic Rendezvous in Bounded Terrains
dc.typeCommunication dans un congrès
dc.identifier.doi10.1007/978-3-642-13284-1_7
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.page72-85
bordeaux.volume6058
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.conference.titleSIROCCO 2010
bordeaux.countryTR
bordeaux.title.proceedingProceedings of the 17th International Colloquium on Structural Information and Communication Complexity
bordeaux.conference.cityŞirince
bordeaux.peerReviewedoui
hal.identifierhal-00516048
hal.version1
hal.invitednon
hal.proceedingsoui
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00516048v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Proceedings%20of%20the%2017th%20International%20Colloquium%20on%20Structural%20Information%20and%20Communication%20Complexity&rft.date=2010&rft.volume=6058&rft.spage=72-85&rft.epage=72-85&rft.au=CZYZOWICZ,%20Jurek&ILCINKAS,%20David&LABOUREL,%20Arnaud&PELC,%20Andrzej&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