Actually any consistent pre-arranged scheme will do.
- Turn always left
- If on a dead-end backtrack to previous turn and turn right
- 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
- One agent stays in the same place
- While the other uses a consistent scheme to explore the maze (e.g using an Ariadne's thread approach).
- 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:
- Each agent throws a coin on which role to choose (e.g either staying in place or exploring the maze)
- 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"