text: The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this paper, 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 Omega(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 L 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 L + loglog n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most L 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 Omega(log L + loglog n)$ bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.
  @cite_35: 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.
  @cite_18: Search Theory is one of the original disciplines within the field of Operations Research. It deals with the problem faced by a Searcher who wishes to minimize the time required to find a hidden object, or “target. ” The Searcher chooses a path in the “search space” and finds the target when he is sufficiently close to it. Traditionally, the target is assumed to have no motives of its own regarding when it is found; it is simply stationary and hidden according to a known distribution (e. g. , oil), or its motion is determined stochastically by known rules (e. g. , a fox in a forest). The problems dealt with in this book assume, on the contrary, that the “target” is an independent player of equal status to the Searcher, who cares about when he is found. We consider two possible motives of the target, and divide the book accordingly. Book I considers the zero-sum game that results when the target (here called the Hider) does not want to be found. Such problems have been called Search Games (with the “ze- sum” qualifier understood). Book II considers the opposite motive of the target, namely, that he wants to be found. In this case the Searcher and the Hider can be thought of as a team of agents (simply called Player I and Player II) with identical aims, and the coordination problem they jointly face is called the Rendezvous Search Problem.
  @cite_31: We consider rendezvous problems in which two players move on the plane and wish to cooperate to minimise their first meeting time. We begin by considering the case where both players are placed such that the vector difference is chosen equiprobably from a finite set. We also consider a situation in which they know they are a distanced apart, but they do not know the direction of the other player. Finally, we give some results for the case in which player 1 knows the initial position of player 2, while player 2 is given information only on the initial distance of player 1.
  @cite_22: 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.
  @cite_7: We present two new results for the asymmetric rendezvous problem on the line. We first show that it is never optimal for one player to be stationary during the entire search period in the two-player rendezvous. Then we consider the meeting time of n-players in the worst case and show that it has an asymptotic behavior of n = 2 + O(log n).
  @cite_33: Two friends have become separated in a building or shopping mall and and wish to meet as quickly as possible. There are n possible locations where they might meet. However, the locations are identical and there has been no prior agreement where to meet or how to search. Hence they must use identical strategies and must treat all locations in a symmetrical fashion. Suppose their search proceeds in discrete time. Since they wish to avoid the possibility of never meeting, they will wish to use some randomizing strategy. If each person searches one of the n locations at random at each step, then rendezvous will require n steps on average. It is possible to do better than this: although the optimal strategy is difficult to characterize for general n, there is a strategy with an expected time until rendezvous of less than 0.829 n for large enough n. For n = 2 and 3 the optimal strategy can be established and on average 2 and 8 3 steps are required respectively. There are many tantalizing variations on this problem, which we discuss with some conjectures. DYNAMIC PROGRAMMING; SEARCH PROBLEMS
  @cite_28: Two players A and B are randomly placed on a line. The distribution of the distance between them is unknown except that the expected initial distance of the (two) players does not exceed some constant @math The players can move with maximal velocity 1 and would like to meet one another as soon as possible. Most of the paper deals with the asymmetric rendezvous in which each player can use a different trajectory. We find rendezvous trajectories which are efficient against all probability distributions in the above class. (It turns out that our trajectories do not depend on the value of @math ) We also obtain the minimax trajectory of player A if player B just waits for him. This trajectory oscillates with a geometrically increasing amplitude. It guarantees an expected meeting time not exceeding @math We show that, if player B also moves, then the expected meeting time can be reduced to @math The expected meeting time can be further reduced if the players use mixed strategies. We show that if player B rests, then the optimal strategy of player A is a mixture of geometric trajectories. It guarantees an expected meeting time not exceeding @math This value can be reduced even more (below @math ) if player B also moves according to a (correlated) mixed strategy. We also obtain a bound for the expected meeting time of the corresponding symmetric rendezvous problem.
  @cite_3: Two players are independently placed on a commonly labelled network X. They cannot see each other but wish to meet in least expected time. We consider continuous and discrete versions, in which they may move at unit speed or between adjacent distinct nodes, respectively. There are two versions of the problem (asymmetric or symmetric), depending on whether or not we allow the players to use different strategies. After obtaining some optimality conditions for general networks, we specialize to the interval and circle networks. In the first setting, we extend the work of J. V. Howard; in the second we prove a conjecture concerning the optimal symmetric strategy. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 256–274, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002 nav.10011
  @cite_24: 
  @cite_19: Leaving marks at the starting points in a rendezvous search problem may provide the players with important information. Many of the standard rendezvous search problems are investigated under this new framework which we call markstart rendezvous search. Somewhat surprisingly, the relative difficulties of analysing problems in the two scenarios differ from problem to problem. Symmetric rendezvous on the line seems to be more tractable in the new setting whereas asymmetric rendezvous on the line when the initial distance is chosen by means of a convex distribution appears easier to analyse in the original setting. Results are also obtained for markstart rendezvous on complete graphs and on the line when the players' initial distance is given by an unknown probability distribution. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 722–731, 2001
  @cite_15: 
  @cite_13: 
  @cite_12: We consider the problem of a rendezvous (coordinated meeting) of distributed units (intelligent agents in network computing or autonomous robots). The environment is modeled as a graph, the node labeling of which may not be “common knowledge” to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility of the environment. Meeting of such units is likely to be a basic procedure in the area of distributed “intelligent agent” computing and in the domain of coordinated tasks of autonomous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent (computing power, control and memory) than simple (traditional) pebbles or tokens, and our algorithms will make use of this capability for speeding up the convergence to a common place (e.g., we will allow units to meet exchange information and depart). We consider both randomized protocols and deterministic (but non-uniform) protocols; the problem is unsolvable by a uniform deterministic algorithm. The deterministic procedure employs ideas from design theory and achieves O(n) time, while the randomized methods are based on random walks and may achieve O(n) time where k is the number of agents.
  @cite_20: 
summary: The rendezvous problem was first mentioned in @cite_15 . Authors investigating rendezvous (cf. @cite_18 for an extensive survey) considered either the geometric scenario (rendezvous in an interval of the real line, see, e.g., @cite_28 @cite_19 @cite_7 , or in the plane, see, e.g., @cite_13 @cite_31 ), or rendezvous in networks, see e.g., @cite_20 @cite_35 @cite_12 . Many papers, e.g., @cite_22 @cite_3 @cite_33 @cite_28 @cite_24 study the probabilistic setting: inputs and or rendezvous strategies are random.