16
$\begingroup$

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze? I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands. Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance. We want this sequence to ensure our partner will escape, no matter where our partner was initially placed. Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences. I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem. Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case. I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.

Improve this question
$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Discrete lizard ♦
    Feb 11 '19 at 19:53
  • $\begingroup$ Eppstein's strategy for monotonic automata is to cluster states so that rather than looking for a path in the full power set of states he looks for a path in a graph with only polynomially many vertices. The most natural generalisation of intervals to 2D that I can think of is the convex hull, but unfortunately it's not clear that their number grows polynomially. $\endgroup$
    – Peter Taylor
    Feb 26 '19 at 23:29
0
$\begingroup$

One optimal solution for this problem is A* with iterative deepening (IDA*) as described in the accepted answer to my puzzle. I am not sure whether IDA* is a polynomial-time algorithm in general, but the following sheds some light.

Improve this answer
$\endgroup$
-1
$\begingroup$

An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).

Improve this answer
$\endgroup$
2
  • $\begingroup$ You cannot encode wall-following as a fixed sequence of Cardinal directions. The choices depend on the walls around you, which is specifically disallowed by the question. $\endgroup$
    – Curtis F
    Aug 16 '19 at 14:20
  • $\begingroup$ If you know the shortest path, you can encode it as "move left, then straight, then...". If you don't know the shortest path, you can't give such directions for the shortest way out. If you don't know a path, you can't give directions to get out. $\endgroup$
    – vonbrand
    Aug 16 '19 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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