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] In 2012 the conjecture was proved for n = 3 by Richard Weber. [6] This was the first non-trivial symmetric rendezvous search problem to be fully solved. 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

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

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 interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent ought to take actions in a dynamic environment in order to maximize the cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.

<span class="mw-page-title-main">Simulated annealing</span> Probabilistic optimization technique and metaheuristic

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound.

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.

In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .

<span class="mw-page-title-main">Multi-armed bandit</span> Resource problem in machine learning

In probability theory and machine learning, the multi-armed bandit problem is a problem in which a decision maker iteratively selects one of multiple fixed choices when the properties of each choice are only partially known at the time of allocation, and may become better understood as time passes. A fundamental aspect of bandit problems is that choosing an arm does not affect the properties of the arm or other arms.

<span class="mw-page-title-main">Rapidly exploring random tree</span> Search algorithm

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. They easily handle problems with obstacles and differential constraints and have been widely used in autonomous robotic motion planning.

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 and vertex ?" 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. The game is zero sum with the payoff being the time spent in searching. 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 and independently considered by Anatole Beck.

<span class="mw-page-title-main">Shmuel Gal</span>

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

<span class="mw-page-title-main">Iterated local search</span>

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 the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

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 to avoid rectangles with only two points on their boundary.

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). 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, vol. 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, S2CID   122587972 .
  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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.