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 waits at his original location and the other player looks for him using a random permutation of the locations.

Steve Alpern is a professor of Operational Research at the University of Warwick, where he recently moved after working for many years at the London School of Economics. His early work was mainly in the area of dynamical systems and ergodic theory, but his more recent research has been concentrated in the fields of search games and rendezvous. He informally introduced the rendezvous problem as early as 1976. His collaborators include Shmuel Gal, Vic Baston and Robbert Fokkink.

Richard Robert Weber is a mathematician working in operational research. He is Churchill Professor of Mathematics for Operational Research in the Statistical Laboratory, University of Cambridge.

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.

Synchronization coordination of events to operate a system in unison

Synchronization is the coordination of events to operate a system in unison. The conductor of an orchestra keeps the orchestra synchronized or in time. Systems that operate with all parts in synchrony are said to be synchronous or in sync—and those that are not are asynchronous.

Operating system collection of software that manages computer hardware resources

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.

Operations research, or operational research (OR) in British usage, is a discipline that deals with the application of advanced analytical methods to help make better decisions. Further, the term operational analysis is used in the British military as an intrinsic part of capability development, management and assurance. In particular, operational analysis forms part of the Combined Operational Effectiveness and Investment Appraisals, which support British defense capability acquisition decision-making.

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]

Symmetry breaking Physical process transitioning a system from a symmetric state to a more ordered state

In physics, symmetry breaking is a phenomenon in which (infinitesimally) small fluctuations acting on a system crossing a critical point decide the system's fate, by determining which branch of a bifurcation is taken. To an outside observer unaware of the fluctuations, the choice will appear arbitrary. This process is called symmetry "breaking", because such transitions usually bring the system from a symmetric but disorderly state into one or more definite states. Symmetry breaking is thought to play a major role in pattern formation.

See also

In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies.

In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.

In computer science, the sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none, and doing so in an orderly manner.

Related Research Articles

Search algorithm Any algorithm which solves the search problem

In computer science, a search algorithm is any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values. Specific applications of search algorithms include:

Shortest path problem computational 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.

Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.

Reinforcement learning field of machine learning

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

Graph coloring assignment of labels traditionally called "colors" to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

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 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.

Multi-armed bandit

In probability theory, the multi-armed bandit problem is a problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation, and may become better understood as time passes or by allocating resources to the choice. This is a classic reinforcement learning problem that exemplifies the exploration-exploitation tradeoff dilemma. The name comes from imagining a gambler at a row of slot machines, who has to decide which machines to play, how many times to play each machine and in which order to play them, and whether to continue with the current machine or try a different machine. The multi-armed bandit problem also falls into the broad category of stochastic scheduling.

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.

In game theory, a princess and monster game is a pursuit-evasion game played by two players in a region. The game was devised by Rufus Isaacs and published in his book Differential Games (1965) as follows:

The monster searches for the princess, the time required being the payoff. They are both in a totally dark room, but they are each cognizant of its boundary. Capture means that the distance between the princess and the monster is within the capture radius, which is assumed to be small in comparison with the dimension of the room. The monster, supposed highly intelligent, moves at a known speed. We permit the princess full freedom of locomotion.

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

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 Israeli mathematician

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

Iterated local search kind of metaheuristic algorithm

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.

Variable neighborhood search (VNS), proposed by Mladenović, Hansen, 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving linear program problems, integer program problems, mixed integer program problems, nonlinear program problems, etc.

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.

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., 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, 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.