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.
