[Solved]: Optimal myopic maze solver

Problem Detail: 

I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and can be implemented by a finite transducer.

Let our robot be represented by a transducer with the following actions, and observables:

• Actions: go forward ($\uparrow$), turn left ($\leftarrow$), turn right ($\rightarrow$)
• Observables: wall ahead ($\bot$), no wall ahead ($\top$)

Then we can build the left-hand maze solver as (pardon my lazy drawing):

Where seeing an observable will make us follow the appropriate edge out of the state while executing the action associated with that edge. This automaton will solve all simply-connected mazes, although it might take its time following dead ends. We call another automaton $B$ better than $A$ if:

1. $B$ takes strictly more steps on only a finite number of mazes, and

2. $B$ takes strictly fewer steps (on average; for probabilistic variants) on an infinite number of mazes.

My two questions:

1. Is there a finite automaton better than the one drawn above? What if we allow probabilistic transducers?

2. Is there a finite automaton for solving mazes that are not necessarily simply-connected?

Asked By : Artem Kaznatcheev

Answered By : Vor

If I understood well the question, I think that you can apply a speedup trick to get faster automata on an infinite number of mazes (providing that the exit is placed on one of the border): you can simply use the internal states to store a finite number of steps and recognize dead ends like the one in the figure:

When a right-hand following automaton is in position $A$ and its state "signals" that it has just followed a closed square (with fixed size encoded, not an arbitrary large square), then it can safely turn left and avoid visiting the dead end zone. As underlined in my comment below, the automaton will apply the shortcut on every maze that contains one (or more) "submazes" like the one in the figure, so it will perform better on infinitely many mazes. On the mazes that don't contain a submaze like the one in the figure it will perform like a standard right-hand following automaton.

In a similar manner you can encode a finite number of different fixed size shapes to avoid dead ends and speed up your automaton. As a consequence, there is no "optimal" myopic maze solver for simply-connected mazes with the exit placed on the border.

The trick works if the entrance is placed inside the maze and the exit on the border, too; but if the exit is placed inside the maze, then it doesn't work because all locations must be visited and in this case your myopic solver is optimal.

Obviously you can't apply the same trick to solve non-simply connected mazes (but it should work if there is a fixed upper bound on the size of each unconnected component).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2201