Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.
share|cite|improve this question
    
(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. – greybeard Jan 16 at 10:28
6  
The logical answer is to call her mobile phone ;) – DavidPostill Jan 16 at 15:03
2  
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? – D.W. Jan 16 at 18:14
up vote 19 down vote accepted

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.

share|cite|improve this answer
    
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. – jl6 Jan 17 at 20:22

Actually any consistent pre-arranged scheme will do.

For example:

  1. Turn always left
  2. If on a dead-end backtrack to previous turn and turn right
  3. One will have to walk double the (pre-arranged) speed of the other (or in more number-theoretic terms, the speeds of the two agents should be relatively prime, or more generaly be linearly-independent).

Or even simpler

  1. One agent stays in the same place
  2. While the other uses a consistent scheme to explore the maze (e.g using an Ariadne's thread approach).
  3. Eventualy, in finite time, they will meet.

This scheme will guarantee that the people will meet eventualy (but it might take some time)

Why? Because the scheme is consistent for both and does not lead either to a dead-end. So since the maze is finite and is connected, after a finite time they will meet.

If the scheme is not consistent, there is no guarantee they will meet since they can result in closed loops.

If they have the same speed then depending on the architecture of the maze, e.g a cyclic maze, then it is possible they can always be at anti-diametrical points of the maze, hence never meet, even though the scheme is consistent.

It is clear from the above that the scheme needs to be pre-arranged, but any consistent pre-arranged scheme will do.

Else one can rely on probabilistic analysis and infer that with a large probability they will meet, but this probability is not one (i.e under all cases).

One can also consider the converse of the rendezvous problem, the avoidance problem where the objective is for the agents to always avoid each other.

The solution to the avoidance problem is for the agents to reflect each other exactly. Meaning that what one agent does the other should do the reflection of that. Since the avoidance problem also has a solution, it is clear that strategies for the rendezvous problem that may lead to reflection behaviour of the agents, cannot guarantee solution.

One can say that the strategy for the avoidance problem is parallelization (ie maximum divergent point) whereas the strategy for the rendezvous problem is orthogonality (i.e least convergent point)

The above analysis can be turned into an randomised algorithm which does not assume pre-arranged roles for the agents, like the following:

  1. Each agent throws a coin on which role to choose (e.g either staying in place or exploring the maze)
  2. Then they proceed as described above.

This on average will lead to people eventually meeting, but is not guaranteed under all cases.

If we assume that the agents can leave traces, e.g labels of their (current) direction and speed. Then, the other agent, can use these traces as information to adjust both its own direction and speed (see below).

This kind of problem is an example of global optimisation using only local information. Or, in other words, a way to map global constraints to local constraints. This, more general, problem (which subsumes the rendezvous problem) is tackled in this math.se post (and references therein) "Methods to translate global constraints to local constraints"

share|cite|improve this answer
    
"One agent stays in the same place" violates the symmetry property that OP wants. where both agents follow the same strategy. – AndyG Jan 21 at 12:52
    
@AndyG, yes this part is answered below, using a number of approaches Plus it is answered by noting that solution is not guaranteed in this case – Nikos M. Jan 21 at 12:56
1  
@NikosM. I don't believe any sort of synchronization is necessary. One can model this problem as a pursuit evasion scenario where both agents regard the others as an evader. Probabilistic approaches to solve this problem exist, and in a 3D environment one can show the minimum number of pursuers required to guarantee a capture. – AndyG Jan 21 at 13:37
1  
"Always turn left" doesn't work. Suppose that you're on aisle 2 and your wife is on aisle 5. You will walk up and down aisles 2 and 3 (or 1 and 2, depending on which way you were initially facing) forever, and your wife will walk up and down 5 and 6 (or 4 and 5). Alternatively, if your're in a small supermarket whose connectivity graph is a cycle, you could just end up walking around the cycle forever, in the same direction and at the same speed. – David Richerby Jan 22 at 0:37
1  
"One agent stays in the same place, the other does something else" doesn't work since both agents might elect to stay still and wait for the other one forever. If the agents can communicate to agree who will stand still, they may as well instead communicate the fact that one of them is standing by the bananas. – David Richerby Jan 22 at 0:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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