Jurek Czyzowicz ∗† Arnaud Labourel ∗‡ ¶ Andrzej Pelc ∗§ How to meet asynchronously (almost) everywhere arXiv:1001.0890v1 [cs.DS] 6 Jan 2010 Abstract Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it 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. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerfull adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting – agents can, indeed, meet almost everywhere – we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other. The problem and the model. Two mobile agents (robots) modeled as points starting at different locations If nodes of the graph are labeled and the labeling is known, then agents can decide to meet at a pre- determined node and the rendezvous problem reduces to graph exploration. However, in many applications, when rendezvous is needed in a network of unknown topology, such unique labeling of nodes may be unavail- able, or agents may be unable to perceive such labels, e.g., due to security reasons. Hence it is important to design rendezvous algorithms for agents operating in anonymous graphs, i.e., graphs without unique labeling of nodes. It is important to note that the agents have to be able to locally distinguish ports at a node: otherwise, an agent may even be unable to visit all neighbors of a node of degree 3 (after visiting the second neighbor, the agent cannot distinguish the port leading to the first vis- ited neighbor from that leading to the unvisited one). Consequently, agents initially located at two nodes of degree 3, might never be able to meet. This justifies a common assumption made in the literature: all ports at In this paper we study the asynchronous version of the rendezvous problem, under both above scenarios: each agent designs its route and an adversary controls the speed of each agent, can vary this speed, stop the agent, or even move it 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. In the asynchronous version of the graph scenario, meeting at a node may be impossible even in the two-node graph, as the adversary can desynchronize the agents and make them visit nodes at different times. Thus it is necessary to relax the requirement and allow agents to meet either in a node or inside an edge. Such a definition of meeting is natural, e.g., when agents are robots traveling in a labyrinth. We consider an embedding of the underlying graph in the three-dimensional Euclidean space, with nodes of the graph being points of the space and edges being pairwise disjoint line segments joining them (hence there are no edge crossings). Agents are modeled as points moving inside this embedding. of an unknown environment have to meet. This task is known in the literature as the rendezvous problem, and has been studied under two alternative scenarios. Either the agents move in a network, modeled by an undirected connected graph (the graph scenario ), or they move in (some subset of) the plane (the geometric scenario ). 1 Introduction $^{∗}$D´ epartement d’informatique, Universit´ e du Qu´ ebec en Outaouais, Gatineau, Qu´ ebec J8X 3X7, Canada. E-mails: jurek@uqo.ca , labourel.arnaud@gmail.com , pelc@uqo.ca $^{†}$Partially supported by NSERC discovery grant. $^{¶}$Supported by the ANR-project “ALADDIN”, and the ´ equipe- projet INRIA “C ´ EPAGE”. $^{‡}$This work was done during this author’s stay at the Universit´ e du Qu´ ebec en Outaouais as a postdoctoral fellow. $^{§}$Partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Universit´ e du Qu´ ebec en Outaouais.