Optimaler Myopic Labyrinthlöser

Ich habe mit der Maze-Demo von Google Blocky herumgespielt und mich an die alte Regel erinnert: Wenn Sie ein Labyrinth lösen möchten, halten Sie einfach Ihre linke Hand an der Wand. Dies funktioniert für jedes einfach verbundene Labyrinth und kann von einem endlichen Wandler implementiert werden.

Lassen Sie unseren Roboter durch einen Wandler mit den folgenden Aktionen und Observablen dargestellt werden:

Aktionen: vorwärts gehen ( ), links abbiegen ( ), rechts abbiegen ( ) $\uparrow$ $\leftarrow$ $\rightarrow$
Observables: Wand voraus ( $\bot$ ), keine Wand voraus ( $\top$ )

Dann können wir den linken Labyrinthlöser wie folgt erstellen (entschuldigen Sie meine faule Zeichnung):

Wandler, um das Labyrinth zu lösen

Wenn wir ein Observable sehen, folgen wir der entsprechenden Kante außerhalb des Zustands, während wir die mit dieser Kante verbundene Aktion ausführen. Dieser Automat löst alle einfach verbundenen Labyrinthe, obwohl es nach Sackgassen einige Zeit dauern kann. Wir nennen einen anderen Automaten besser als wenn: $B$ $A$

$B$ macht streng mehr Schritte auf nur einer endlichen Anzahl von Labyrinthen, und
$B$ unternimmt auf einer unendlichen Anzahl von Labyrinthen streng weniger Schritte (im Durchschnitt; für probabilistische Varianten).

Meine zwei Fragen:

Gibt es einen endlichen Automaten, der besser ist als der oben gezeichnete? Was ist, wenn wir probabilistische Wandler zulassen?
Gibt es einen endlichen Automaten zum Lösen von Labyrinthen, die nicht unbedingt einfach miteinander verbunden sind?

automata finite-automata artificial-intelligence Artem Kaznatcheev
quelle

@jmad und ich hatten eine ziemlich fruchtbare Diskussion im Chat über diese Frage. Wenn Sie über die Frage nachdenken (insbesondere über die Definitionen von besser als ), empfehle ich Ihnen , das Transkript zu lesen.

Artem Kaznatcheev

Ich verstehe nicht, wie sich diese Frage auf die KI bezieht (insbesondere unsere Agenten, um ihr Verhalten bei gegebenen Instanzdaten nicht zu ändern), aber ich bin kein Experte auf diesem Gebiet.

Raphael

@Raphael Labyrinthlösung und Pfadfindung (von der Überprüfung von BFS, DFS über A * bis hin zu On-Wards) sind grundlegende Lehrpläne in einem Intro-AI-Kurs. Ich bin damit einverstanden, dass dies als Intelligenz nicht besonders aufregend ist, aber wenn mir die KI etwas beigebracht hat: Der größte Teil der KI ist nur ein Suchproblem.

Artem Kaznatcheev

Antworten:

Wenn ich die Frage gut verstanden habe, denke ich, dass Sie einen Beschleunigungstrick anwenden können, um schnellere Automaten auf einer unendlichen Anzahl von Labyrinthen zu erhalten (vorausgesetzt, der Ausgang befindet sich an einer der Grenzen): Sie können einfach die internen Zustände verwenden, um a zu speichern endliche Anzahl von Schritten und Sackgassen wie in der Abbildung erkennen:

Geben Sie hier die Bildbeschreibung ein

Wenn sich ein rechts folgender Automat in Position und sein Zustand "signalisiert", dass er gerade einem geschlossenen Quadrat gefolgt ist ( mit fester Größe codiert, kein beliebiges großes Quadrat ), kann er sicher nach links abbiegen und vermeiden, die Sackgasse zu besuchen Zone. Wie in meinem Kommentar unten unterstrichen, wendet der Automat die Verknüpfung auf jedes Labyrinth an, das ein (oder mehrere) "Submazes" wie das in der Abbildung enthält, sodass er bei unendlich vielen Labyrinthen eine bessere Leistung erzielt. Auf den Labyrinthen, die kein Submaze wie das in der Abbildung enthalten, funktioniert es wie ein Standardautomat für die rechte Hand. $A$

Auf ähnliche Weise können Sie eine endliche Anzahl verschiedener Formen mit fester Größe codieren, um Sackgassen zu vermeiden und Ihren Automaten zu beschleunigen. Infolgedessen gibt es keinen "optimalen" kurzsichtigen Labyrinthlöser für einfach verbundene Labyrinthe, deren Ausgang an der Grenze liegt.

Der Trick funktioniert, wenn sich der Eingang im Labyrinth und der Ausgang auch an der Grenze befinden. Wenn sich der Ausgang jedoch im Labyrinth befindet, funktioniert dies nicht, da alle Standorte besucht werden müssen und in diesem Fall Ihr Kurzsichtigkeitslöser optimal ist.

Natürlich können Sie nicht denselben Trick anwenden, um nicht einfach verbundene Labyrinthe zu lösen (aber es sollte funktionieren, wenn es eine feste Obergrenze für die Größe jeder nicht verbundenen Komponente gibt).

Vor
quelle

Dies ist ein cooler Trick für den Fall des Ein- und Ausstiegs an der Grenze (eine Unterklasse von einfach verbundenen Labyrinthen). Es zeigt, dass in diesem eingeschränkten Fall die von mir definierte Reihenfolge keine Mindestelemente enthält. Ich denke jedoch nicht, dass es auf alle einfach verbundenen Labyrinthe verallgemeinert werden kann (das ist das Set, an dem links gearbeitet wird).

Artem Kaznatcheev

@ArtemKaznatcheev: Ich denke, dass der Trick bei Labyrinthen mit Eingang im Labyrinth und Ausgang an der Grenze funktioniert. Darüber hinaus funktioniert es bei (unendlich vielen) Labyrinthen, in denen sich ein Submaze wie in der Abbildung befindet. Ich werde die Frage bearbeiten, um diesen Punkt zu klären.

Vor dem

Wenn ich das richtig verstehe, kann dies als endlicher Lookahead interpretiert werden: Geben Sie eine Aktion erst aus, nachdem die nächsten Symbole gelesen wurden. Wenn ja, dann sollte das immer funktionieren.

k

$k$

Raphael

@Raphael: Ich nenne es besser eine endliche Menge an Speicher: Wenn die letzten Schritte (Aktionen) ein (im Uhrzeigersinn) Quadrat bilden, würde eine Rechtsdrehung zum inneren Teil des Quadrats (einer Sackgasse) führen Es ist sicher, nach links abzubiegen.

4 k - 1

$4k-1$

Vor dem

Frage 1

Ich denke, Ihre Definition von besser ist zu streng in dem Sinne, dass endlich zu restriktiv ist (aber ich habe keine bessere Definition).

Wir bauen eine Familie von Labyrinthen . Jedes ist ein Korridor der Länge , der mit einer Rechtskurve endet. Das gleiche gilt für bzw. links. Wir können einen Wandler und , die die Teilmengen bzw. optimal lösen . Dann ist kein Wandler besser als oder . $R=(R_i)_i$ $R_i$ $i$ $L$ $A_R$ $A_L$ $R$ $L$ $A_R$ $A_L$

: Mit wir , das beweist, dass kein Löser besser ist als . Mein Punkt ist, dass ich denke, dass wir dasselbe für den linken Labyrinthlöser tun können, aber die Labyrinthe wären komplexer. $A_R$ $R$ $A_R$

Probabilistische Wandler können wahrscheinlich ausgeschlossen werden, da ein deterministischer Wandler auf diesen unendlichen Labyrinthsätzen schneller ist.

Frage 2 (dank der Diskussion mit OP )

Nein. (Quelle: dieses bahnbrechende Papier von Lothar Budach. Der Satz wird in der Zusammenfassung dieses Artikels von Frank Hoffmann deutlicher formuliert .)

jmad
quelle

Ja, wir müssten einige Äquivalenzklassen für Labyrinthe unter Standardtransformationen (wie Rotationen und Reflexionen) definieren, um die linke und rechte Wand nach dem Äquivalent zu machen. Leider beantwortet Ihr Abschnitt zu Frage 1 meine erste Frage nicht . Sie zeigen, dass es unvergleichliche (in der Teilreihenfolge "besser als") Löser gibt (wie die linke und die rechte Hand, wenn wir keine Symmetrieannahmen treffen), aber es beweist nicht, dass es keinen gibt besser als die linke Hand.

Artem Kaznatcheev

dh wenn besser als ist und meine linke Hand nennen Solver ist , dann zeigen Sie , dass st und . Ich bitte Sie zu zeigen, dachte ich, dass wir haben ( oder ). Dies sind sehr unterschiedliche Aussagen.

A

$A$

B

$B$

A \leq B

$A \leq B$

L

$L$

\exists R

$\exists R$

R ≰ L

$R \not\leq L$

L ≰ R

$L \not\leq R$

\forall A

$\forall A$

A ≰ L

$A \not\leq L$

L \leq A

$L \leq A$

Artem Kaznatcheev

@ArtemKaznatcheev: Ja, ich weiß, dass es die Frage nicht beantwortet, ich hätte klarer sein sollen. Mein Punkt ist, dass ich denke, dass wir dies auf die LH anwenden könnten , aber auch, dass für diese Art von leicht unendlichen Mengen zu empfindlich ist. (Ich denke, dass A nur, wenn (einer Teilmenge von) sehr ähnlich ist )

\leq

$≤$

A \leq B

$A≤B$

B

$B$

A

$A$

jmad

Die alternative Definition, die ich mir vorstellen kann, besteht darin, die schlechten Beispiele zu bitten, wenige zu sein (statt endlich); Polynom oder kleinere (vielleicht log?) Anzahl von schlechten Beispielen und viele: Superpolynom / exponentielle Anzahl von guten Beispielen. Aber ich dachte tatsächlich, dass dies noch restriktiver ist, da das bei SO VIELEN Beispielen übertreffen muss.

A

$A$

B

$B$

Artem Kaznatcheev

@ArtemKaznatcheev: Sie könnten etwas tun, das von der Größe des Labyrinths abhängt (so etwas wie aber es ist sowohl fraglich als auch unpraktisch). Wir können weiter chatten .

# {A (M) < B (M) ∣ | M | \leq n} / # {M ∣ | M | \leq n} = o (1)

$\#\{A(M)<B(M) ∣ |M|≤n\}/\#\{M ∣ |M|≤n\} = o(1)$

jmad