Asynchronous deterministic rendezvous in bounded terrains

DOI10.1007/978-3-642-13284-1_7MaRDI QIDQ3569117zbMATH OpenOpenAlexFDO

Authors Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, Andrzej Pelc

Publication date 17 June 2010

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.0889

zbMATH Keywords

deterministicmobile agentobstaclepolygonrendezvous

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Agent technology and artificial intelligence (68T42)

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.

Recommendations

• Asynchronous deterministic rendezvous in bounded terrains
• Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
• Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
• How to meet asynchronously (almost) everywhere
• How to meet asynchronously (almost) everywhere

Cited in

(14)

• Asymmetric rendezvous search on the circle
• Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
• Asynchronous rendezvous with different maps
• Rendezvous in planar environments with obstacles and unknown initial distance
• scientific article; zbMATH DE number 1729496 (Why is no real title available?)
• Rendezvous of two robots with constant memory
• How to meet asynchronously (almost) everywhere
• Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
• Asynchronous Deterministic Rendezvous on the Line
• How to meet asynchronously (almost) everywhere
• Meeting in a polygon by anonymous oblivious robots
• The Agreement Power of Disagreement
• Asynchronous deterministic rendezvous in bounded terrains
• Gathering on a circle with limited visibility by anonymous oblivious robots

This page was built for publication: Asynchronous deterministic rendezvous in bounded terrains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569117)