1. Asynchronous deterministic rendezvous in bounded terrains
- Author
-
Arnaud Labourel, Andrzej Pelc, David Ilcinkas, Jurek Czyzowicz, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-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), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
- Subjects
Computational Geometry (cs.CG) ,FOS: Computer and information sciences ,Mathematical optimization ,General Computer Science ,Computer science ,0211 other engineering and technologies ,Terrain ,ComputerApplications_COMPUTERSINOTHERSYSTEMS ,0102 computer and information sciences ,02 engineering and technology ,Computer Science::Computational Geometry ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,01 natural sciences ,ComputingMethodologies_ARTIFICIALINTELLIGENCE ,Theoretical Computer Science ,Computer Science::Robotics ,010104 statistics & probability ,mobile agent ,Compass ,Computer Science - Data Structures and Algorithms ,rendezvous ,Data Structures and Algorithms (cs.DS) ,0101 mathematics ,obstacle ,021103 operations research ,Rendezvous ,deterministic ,polygon ,010201 computation theory & mathematics ,Asynchronous communication ,Bounded function ,Obstacle ,Polygon ,A priori and a posteriori ,Robot ,Computer Science - Computational Geometry ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Computer Science(all) - Abstract
Two 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.
- Published
- 2011