27
$\begingroup$

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.
Improve this question
$\endgroup$
3
  • $\begingroup$ (A supermarket may be a misleading example, as there is a semi-observable exit area.) Now, if both had a means to mark their path in a way that allows each to tell own from other, they could reverse at tripling intervals, problems starting when encountering own. $\endgroup$
    – greybeard
    Commented Jan 16, 2016 at 10:28
  • 7
    $\begingroup$ The logical answer is to call her mobile phone ;) $\endgroup$
    – DavidPostill
    Commented Jan 16, 2016 at 15:03
  • 2
    $\begingroup$ The non-CS answer is to go to a Schelling point. In a supermarket, that might be, e.g., the customer service desk or the exit. Note, however, that in human life, Schelling points often depend as much on human behavior and knowledge, rather than algorithmic analysis of connectivity patterns, so the CS perspective doesn't really provide much insight when we're talking about human agents. Do you really mean to ask about people in real life, or do you mean to ask a mathematical question about robotic agents in a idealized setting? $\endgroup$
    – D.W. ♦
    Commented Jan 16, 2016 at 18:14

1 Answer 1

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Marked as best as this points me to the relevant field of study. If my reading of this survey is right, it is not yet known whether there is an optimal solution to symmetric rendezvous. $\endgroup$
    – jl6
    Commented Jan 17, 2016 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.