CZYZOWICZ, Jurek; ILCINKAS, David; LABOUREL, Arnaud; PELC, Andrzej

doi:10.1007/978-3-642-13284-1_7

Metadatos

Licencia de uso del documento

CZYZOWICZ, Jurek
Département d'Informatique et d'Ingénierie [DII]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

LABOUREL, Arnaud
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

Idioma

Communication dans un congrès

Este ítem está publicado en

Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2010, 2010-06, Şirince. 2010, vol. 6058, p. 72-85

Springer Berlin / Heidelberg

Resumen en inglés

Two 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.< Leer menos

Palabras clave

mobile agent

rendezvous

deterministic

polygon

obstacle

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198240

DOI

http://dx.doi.org/10.1007/978-3-642-13284-1_7

Proyecto ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800