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:
$B$ takes strictly more steps on only a finite number of mazes, and
$B$ takes strictly fewer steps (on average; for probabilistic variants) on an infinite number of mazes.
My two questions:
Is there a finite automaton better than the one drawn above? What if we allow probabilistic transducers?
Is there a finite automaton for solving mazes that are not necessarily simply-connected?