How do I find my wife in a supermarket?

Problem Detail: 

If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using?

I think there are some characteristics that this algorithm will have:

• Each person must be able to derive it using logic that makes no assumptions about what the other person is deciding, but as each person knows the other is in the same position they may make deductions about what the other must be deciding.
• An identical algorithm must be derived by both people as there is total symmetry in their situations (neither has any knowledge about the starting position of the other, and the maze is a fixed size, and fully mapped by both). Note that the algorithm is not required to be deterministic: it is allowed to be randomized.

Asked By : jl6

Answered By : hengxin

This is called rendezvous problem.

As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:

Two astronauts land on a spherical body that is much larger than the detection radius (within which they can see each other). The body does not have fixed orientation in space, nor does it have an axis of rotation, so that no common notion of position or direction is available to the astronauts for coordination. Given unit walking speeds for both astronauts, how should they move about so as to minimize the expected meeting time T (before they come within the detection radius)?

In the survey paper above,

Abstract: Recent results on the problem of mobile agent rendezvous on distributed networks are surveyed with an emphasis on outlining the various approaches taken by researchers in the theoretical computer science community.

It covers both "Asymmetric Rendezvous" (in Section 4) and "Symmetric Rendezvous" (in Section 5).

---

For symmetric rendezvous, the paper by Alpern shows:

It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51918