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 the person is given the "move right" command when there's a wall on the right, he will simply stay where he is.
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.
