12
$\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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Discrete lizard Feb 11 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 at 23:29

Your Answer

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

Browse other questions tagged or ask your own question.