In rendezvous, two agents traverse network edges in synchronous rounds and have to meet at some node. In treasure hunt, a single agent has to find a stationary target situated at an unknown node of the network. We study tradeoffs between the amount of information ( @math ) available @math to the agents and the cost (number of edge traversals) of rendezvous and treasure hunt. Our goal is to find the smallest size of advice which enables the agents to solve these tasks at some cost @math in a network with @math edges. This size turns out to depend on the initial distance @math and on the ratio @math , which is the @math due to advice. For arbitrary graphs, we give upper and lower bounds of @math and @math , respectively, on the optimal size of advice. For the class of trees, we give nearly tight upper and lower bounds of @math and @math , respectively.
The problem of rendezvous has been studied both under randomized and deterministic scenarios. In the framework of networks, it is usually assumed that the nodes do not have distinct identities. An extensive survey of randomized rendezvous in various models can be found in @cite_22 , cf. also @cite_26 @cite_6 @cite_47 @cite_33 . Deterministic rendezvous in networks has been surveyed in @cite_41 . Several authors considered geometric scenarios (rendezvous in an interval of the real line, e.g., @cite_33 @cite_23 , or in the plane, e.g., @cite_16 @cite_38 ). Gathering more than two agents was studied, e.g., in @cite_15 .
@cite_38 @cite_26 @cite_33 @cite_22 @cite_15 @cite_41 @cite_6 @cite_23 @cite_47 @cite_16
1972775782 25030497 1498202041 1543762072 1988551609 1526420573 2040570464 2081055073 2138881680 2623545498
Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph. Two identical (anonymous) mobile agents have to meet in an arbitrary, possibly infinite, unknown connected graph. Agents are modeled as points, they start at nodes of the graph chosen by the adversary and the route of each of them only depends on the already traversed portion of the graph and, in the case of randomized rendezvous, on the result of coin tossing. 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 means that both agents must be at the same time in some node or in some point inside an edge of the graph. In the deterministic scenario we characterize the initial positions of the agents for which rendezvous is feasible and we provide an algorithm guaranteeing asynchronous rendezvous from all such positions in an arbitrary connected graph. In the randomized scenario we show an algorithm that achieves asynchronous rendezvous with probability 1, for arbitrary initial positions in an arbitrary connected graph. In both cases the graph may be finite or (countably) infinite. We study rendezvous of two anonymous agents, where each agent knows its own initial position in the environment. Their task is to meet each other as quickly as possible. The time of the rendezvous is measured by the number of synchronous rounds that agents need to use in the worst case in order to meet. In each round, an agent may make a simple move or it may stay motionless. We consider two types of environments, finite or infinite graphs and Euclidean spaces. A simple move traverses a single edge (in a graph) or at most a unit distance (in Euclidean space). The rendezvous consists in visiting by both agents the same point of the environment simultaneously (in the same round). In this paper, we propose several asymptotically optimal rendezvous algorithms. In particular, we show that in the line and trees as well as in multidimensional Euclidean spaces and grids the agents can rendezvous in time O(d), where d is the distance between the initial positions of the agents. The problem of location-aware rendezvous was studied before in the asynchronous model for Euclidean spaces and multi-dimensional grids, where the emphasis was on the length of the adopted rendezvous trajectory. We point out that, contrary to the asynchronous case, where the cost of rendezvous is dominated by the size of potentially large neighborhoods, the agents are able to meet in all graphs of at most n nodes in time almost linear in d, namely, O(d log2 n). We also determine an infinite family of graphs in which synchronized rendezvous takes time Ω(d). We study the problem of gathering at the same location two mobile agents that are dispersed in an unknown and unlabeled environment. This problem called Rendezvous, is a fundamental task in distributed coordination among autonomous entities. Most previous studies on the subject model the environment as an undirected graph and the solution techniques rely heavily on the fact that an agent can backtrack on any edge it traverses. However, such an assumption may not hold for certain scenarios, for instance a road network containing one-way streets. Thus, we consider the case of strongly connected directed graphs and present the first deterministic solution for rendezvous of two anonymous (identical) agents moving in such a digraph. Our algorithm achieves rendezvous with detection for any solvable instance of the problem, without any prior knowledge about the digraph, not even its size. Two or more mobile entities, called agents or robots, starting at distinct initial positions, have to meet. This task is known in the literature as rendezvous. Among many alternative assumptions that have been used to study the rendezvous problem, two most significantly influence the methodology appropriate for its solution. The first of these assumptions concerns the environment in which the mobile entities navigate: it can be either a terrain in the plane, or a network modeled as an undirected graph. The second assumption concerns the way in which the entities move: it can be either deterministic or randomized. In this article, we survey results on deterministic rendezvous in networks. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc. We study the size of memory of mobile agents that permits to solve deterministically the rendezvous problem, i.e., the task of meeting at some node, for two identical agents moving from node to node along the edges of an unknown anonymous connected graph. The rendezvous problem is unsolvable in the class of arbitrary connected graphs, as witnessed by the example of the cycle. Hence we restrict attention to rendezvous in trees, where rendezvous is feasible if and only if the initial positions of the agents are not symmetric. We prove that the minimum memory size guaranteeing rendezvous in all trees of size at most nis i¾?(logn) bits. The upper bound is provided by an algorithm for abstract state machines accomplishing rendezvous in all trees, and using O(logn) bits of memory in trees of size at most n. The lower bound is a consequence of the need to distinguish between up to ni¾? 1 links incident to a node. Thus, in the second part of the paper, we focus on the potential existence of pairs of finiteagents (i.e., finite automata) capable of accomplishing rendezvous in all bounded degreetrees. We show that, as opposed to what has been proved for the graph exploration problem, there are no finite agents capable of accomplishing rendezvous in all bounded degree trees. The author considers the problem faced by two people who are placed randomly in a known search region and move about at unit speed to find each other in the least expected time. This time is called the rendezvous value of the region. It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise. A general formulation of the rendezvous search problem is given for a compact metric space endowed with a group of isometrics which represents the spatial uncertainties of the players. These concepts are illustrated by considering upper bounds for various rendezvous values for the circle and an arbitrary metric network. The discrete rendezvous problem on a cycle graph for players restricted to symmetric Markovian strategies is then solved. Finally, the author considers the problem faced by two people on an infinite line who each know the distribution of the distance but not the direction to each other. The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Ω(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number e of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log e + log log n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most e leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Ω(log e + log log n) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3. A set of k mobile agents with distinct identifiers and located in nodes of an unknown anonymous connected network, have to meet at some node. We show that this gathering problem is no harder than its special case for k=2, called the rendezvous problem, and design deterministic protocols solving the rendezvous problem with arbitrary startups in rings and in general networks. The measure of performance is the number of steps since the startup of the last agent until the rendezvous is achieved. For rings we design an oblivious protocol with cost O([email protected]?), where n is the size of the network and @? is the minimum label of participating agents. This result is asymptotically optimal due to the lower bound showed by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69-96]. For general networks we show a protocol with cost polynomial in n and [email protected]?, independent of the maximum difference @t of startup times, which answers in the affirmative the open question by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69-96]. We obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. Our solutions answer several problems left open in a recent paper by We also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. Both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. We call such sequences strongly universal traversal (exploration) sequences. We give an explicit construction of strongly universal exploration sequences. The existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.