Rendezvous problem

Last updated

The rendezvous dilemma is a logical dilemma, typically formulated in this way:

Contents

Two people have a date in a park they have never been to before. Arriving separately in the park, they are both surprised to discover that it is a huge area and consequently they cannot find one another. In this situation each person has to choose between waiting in a fixed place in the hope that the other will find them, or else starting to look for the other in the hope that they have chosen to wait somewhere.

If they both choose to wait, they will never meet. If they both choose to walk there are chances that they meet and chances that they do not. If one chooses to wait and the other chooses to walk, then there is a theoretical certainty that they will meet eventually; in practice, though, it may take too long for it to be guaranteed. The question posed, then, is: what strategies should they choose to maximize their probability of meeting?

Examples of this class of problems are known as rendezvous problems. These problems were first introduced informally by Steve Alpern in 1976, [1] and he formalised the continuous version of the problem in 1995. [2] This has led to much recent research in rendezvous search. [3] Even the symmetric rendezvous problem played in n discrete locations (sometimes called the Mozart Cafe Rendezvous Problem) [4] has turned out to be very difficult to solve, and in 1990 Richard Weber and Eddie Anderson conjectured the optimal strategy. [5] Only recently has the conjecture been proved for n = 3 by Richard Weber. [6] This was the first non-trivial symmetric rendezvous search problem to be fully solved. Note that the corresponding asymmetric rendezvous problem has a simple optimal solution: one player stays put and the other player visits a random permutation of the locations.

As well as being problems of theoretical interest, rendezvous problems include real-world problems with applications in the fields of synchronization, operating system design, operations research, and even search and rescue operations planning.

Deterministic rendezvous problem

The deterministic rendezvous problem is a variant of the rendezvous problem where the players, or robots, must find each other by following a deterministic sequence of instructions. Although each robot follows the same instruction sequence, a unique label assigned to each robot is used for symmetry breaking. [7]

See also

Related Research Articles

Algorithm Unambiguous specification of how to solve a class of problems

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks.

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Reinforcement learning (RL) is an area of machine learning concerned with how software agents ought to take actions in an environment in order to maximize the notion of cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.

Greedy algorithm This article describes a type of algorithmic approach that is used to solve computer science problems

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless, a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

Edge coloring

In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

Václav Chvátal

Václav (Vašek) Chvátal (Czech: [ˈvaːtslaf ˈxvaːtal] is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.

Greedy coloring

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In theoretical computer science, the Aanderaa–Karp–Rosenberg conjecture is a group of related conjectures about the number of questions of the form "Is there an edge between vertex u and vertex v?" that have to be answered to determine whether or not an undirected graph has a particular property such as planarity or bipartiteness. They are named after Stål Aanderaa, Richard M. Karp, and Arnold L. Rosenberg. According to the conjecture, for a wide class of properties, no algorithm can guarantee that it will be able to skip any questions: any algorithm for determining whether the graph has the property, no matter how clever, might need to examine every pair of vertices before it can give its answer. A property satisfying this conjecture is called evasive.

A search game is a two-person zero-sum game which takes place in a set called the search space. The searcher can choose any continuous trajectory subject to a maximal velocity constraint. It is always assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius and at this very moment capture occurs. As mathematical models, search games can be applied to areas such as hide-and-seek games that children play or representations of some tactical military situations. The area of search games was introduced in the last chapter of Rufus Isaacs' classic book "Differential Games" and has been developed further by Shmuel Gal and Steve Alpern. The princess and monster game deals with a moving target.

In computational complexity theory, the linear search problem is an optimal search problem introduced by Richard E. Bellman.

Shmuel Gal

Shmuel Gal is a mathematician and professor of statistics at the University of Haifa in Israel.

Iterated local search

Iterated Local Search (ILS) is a term in applied mathematics and computer science defining a modification of local search or hill climbing methods for solving discrete optimization problems.

In computer science, one approach to the dynamic optimality problem on online algorithms for binary search trees involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible in order to avoid rectangles with only two points on their boundary.

In computer science, an optimal binary search tree , sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time for a given sequence of accesses. Optimal BSTs are generally divided into two types: static and dynamic.

In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem.

References

  1. Alpern, Steve (1976), Hide and Seek Games, Seminar, Institut fur Hohere Studien, Wien, 26 July.
  2. Alpern, Steve (1995), "The rendezvous search problem", SIAM Journal on Control and Optimization, 33 (3): 673–683, doi:10.1137/S0363012993249195, MR   1327232
  3. Alpern, Steve; Gal, Shmuel (2003), The Theory of Search Games and Rendezvous, International Series in Operations Research & Management Science, 55, Boston, MA: Kluwer Academic Publishers, ISBN   0-7923-7468-1, MR   2005053 .
  4. Alpern, Steve (2011), "Rendezvous search games", in Cochran, James J. (ed.), Wiley Encyclopedia of Operations Research and Management Science, Wiley, doi:10.1002/9780470400531.eorms0720 .
  5. Anderson, E. J.; Weber, R. R. (1990), "The rendezvous problem on discrete locations", Journal of Applied Probability, 27 (4): 839–851, doi:10.2307/3214827, JSTOR   3214827, MR   1077533 .
  6. Weber, Richard (2012), "Optimal symmetric Rendezvous search on three locations" (PDF), Mathematics of Operations Research, 37 (1): 111–122, doi:10.1287/moor.1110.0528, MR   2891149 .
  7. Ta-Shma, Amnon; Zwick, Uri (April 2014). "Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences". ACM Transactions on Algorithms. 10 (3). 12. doi:10.1145/2601068. S2CID   10718957.