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:59Z
dc.date.available2024-04-15T09:49:59Z
dc.date.created2009-12-18
dc.date.issued2009-12-18
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198295
dc.descriptionRapport de recherche du LaBRI : RR-1467-09
dc.description.abstractEnTwo mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Agents are modeled as points, and each of them is equipped with a compass. Compasses of agents may be incoherent. Agents construct their routes, but the actual walk of each agent is decided by the adversary: the movement of the agent can be at arbitrary speed, the agent may sometimes stop or go back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both agents agree, or not, (3) agents 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 agents' 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.language.isoen
dc.subjectmobile agent
dc.subjectrendezvous
dc.subjectdeterministic
dc.subjectpolygon
dc.subjectobstacle
dc.title.enAsynchronous deterministic rendezvous in bounded terrains
dc.typeAutre document
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.identifier.arxiv1001.0889
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
hal.identifierhal-00442196
hal.version1
hal.popularnon
hal.audienceNon spécifiée
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00442196v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2009-12-18&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