10
$\begingroup$

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):

transducer to solve the maze

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?

$\endgroup$
  • $\begingroup$ @jmad and I had a pretty fruitful discussion in chat about this question. If you are thinking about the question (especially the definitions of better than) then I recommend checking out the transcript. $\endgroup$ – Artem Kaznatcheev Jun 2 '12 at 20:18
  • $\begingroup$ I fail to see how this question relates to AI (in particular our agents to not change their behaviour given instance data), but I am no expert in that field. $\endgroup$ – Raphael Jun 3 '12 at 14:17
  • 3
    $\begingroup$ @Raphael maze-solving and path finding (from review of BFS, DFS, to A*, and on-wards) are basic curriculum in an intro AI course. I agree, as an intelligence, this is not a particularly exciting one, but if AI has taught me anything: most of AI is just a search problem. $\endgroup$ – Artem Kaznatcheev Jun 4 '12 at 1:33
6
$\begingroup$

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:

enter image description here

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).

$\endgroup$
  • $\begingroup$ This is a cool trick for the case of entrance-exit on boundary (which is a sub-class of simply-connected mazes). It shows that in this restricted case, the ordering I defined has no minimum elements. I don't think it can be generalized to all simply-connected mazes though (which is the set left-hand following works on). $\endgroup$ – Artem Kaznatcheev Jun 3 '12 at 1:22
  • $\begingroup$ @ArtemKaznatcheev: I think that the trick works on mazes with entrance inside the maze and exit on the boundary, too. Furthermore it works on (infinitely many) mazes in which there is a submaze like the one in the figure). I will edit the question to clarify this point. $\endgroup$ – Vor Jun 3 '12 at 8:24
  • $\begingroup$ If I understand correctly, this can be interpreted as finite lookahead: output an action only after the next $k$ symbols have been read. If so then yes, that should always work. $\endgroup$ – Raphael Jun 3 '12 at 14:13
  • $\begingroup$ @Raphael: I will better call it a finite amount of memory: if the last $4k-1$ steps (actions) forms a (clockwise) square, then turning right would lead to the inner part of the square (a dead end), so it is safe to turn left. $\endgroup$ – Vor Jun 3 '12 at 14:24
5
$\begingroup$

Question 1

I think your definition of better is too strict in the sense that finite is too restrictive (but I don't have any better definition).

We build a family of mazes $R=(R_i)_i$. Each one $R_i$ is a corridor of length $i$ that ends with a turn on the right. The same with $L$ and left, respectively. We can build a transducer $A_R$ and $A_L$ that optimally solve the subsets $R$ and $L$, respectively. Then no transducer is better than $A_R$ or $A_L$.

Now the other way around : given $A_R$ we can build $R$ that proves that no solver is better than $A_R$. My point is that I think we can do the same for the left-hand maze solver, but the set of mazes would be more complex.

Probabilistic transducers can probably ruled out since a deterministic transducer will be faster on these infinite sets of mazes.

Question 2 (thanks to the discussion with OP)

No. (source: this groundbreaking paper by Lothar Budach. The theorem is more clearly stated in the abstract of this article by Frank Hoffmann.)

$\endgroup$
  • $\begingroup$ yeah, we would need to define some equivalence classes on mazes under standard transformations (like rotations and reflections) to make left-hand and right-hand wall following equivalent. Unfortunately, your question 1 section does not answer my first question. You show that there are incomparable (in the 'better-than' partial order) solvers (such as the left-hand and right-hand if we make no symmetry assumptions) but it doesn't prove that there isn't one that is better than the left hand. $\endgroup$ – Artem Kaznatcheev Jun 2 '12 at 18:30
  • $\begingroup$ i.e. if $A$ better-than $B$ is $A \leq B$ and call my left hand solver is $L$, then you show that $\exists R$ s.t. $R \not\leq L$ and $L \not\leq R$. What I ask you to show, thought, is that $\forall A$ we have ($A \not\leq L$ or $L \leq A$). These are very different statements. $\endgroup$ – Artem Kaznatcheev Jun 2 '12 at 18:35
  • $\begingroup$ @ArtemKaznatcheev: yes, I know that it does not answer the question, I should have been clearer. My point is that I think that we could apply this to the LH but also that $≤$ is too sensitive wrt this kind of easily infinite sets. (I think that $A≤B$ only if $B$ is very similar to (a subset of) $A$) $\endgroup$ – jmad Jun 2 '12 at 19:14
  • $\begingroup$ The alternative definition I can think of is to ask the bad-examples to be few (instead of finite); polynomial or smaller (maybe log?) number of bad-examples and many: super-polynomial/exponential number of good-examples. But I actually thought this was even more restrictive, since the $A$ has to outperform $B$ on SO MANY examples. $\endgroup$ – Artem Kaznatcheev Jun 2 '12 at 19:19
  • $\begingroup$ @ArtemKaznatcheev: you could do something that depends on the size of the maze (something like $\#\{A(M)<B(M) ∣ |M|≤n\}/\#\{M ∣ |M|≤n\} = o(1)$ but it is both questionable and non-practical). We can continue on chat. $\endgroup$ – jmad Jun 2 '12 at 19:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.