Labyrinthalgorithmen

Schon seit 1977 gibt es bei Roboterwettkämpfen die Disziplin "Micromouse". Die Roboter starten dabei zunächst in einer der vier äußeren Ecken, erkunden den Irrgarten und berechnen den kürzesten Weg von der Startecke zum Ziel in der Mitte. Anschließend durchfahren sie diesen Weg in möglichst kurzer Zeit. Micromouse-Fahrzeuge können Geschwindigkeiten von mehr als 3 Metern pro Sekunde erreichen, die schnellsten unter ihnen durchfahren ein Labyrinth in wenigen Sekunden. (Dies sieht sehr verrückt aus, siehe z.B. https://www.youtube.com/watch?v=NqdZ9wbXt8k)

Diese Irrgärten stellen für die Algorithmen große Herausforderungen dar, da es manchmal zahlreiche Sackgassen und Inseln gibt, manchmal aber auch überhaupt keine Sackgassen und es hierbei vor allem auf das Finden eines möglichst kurzen Weges ankommt.

Labyrinthe sind Spezialfälle von Irrgärten, "unicursale Irrgärten" genannt, denn in ihnen gibt es nur einen einzigen, jedoch ziemlich langen Weg vom Eingang zum Zentrum. Als Sinnbild für den Lebensweg des Menschen findet man Labyrinthe in mittelalterlichen Kathedralen (Amiens, Chatres) und in Klostergärten. Um aus diesem herauszufinden, braucht man keinen Algorithmus, nur Ausdauer. Allerdings war das namensgebende Labyrinth von Knossos, in dem der Minotaurus gefangen war und aus dem Ariadne mit dem Ariadnefaden wieder herausfand, ein verwinkelter Palast, also ein Irrgarten.

Algorithmen

Die Rechte-Hand-Methode ist die bekannteste Regel, einen Irrgarten zu durchqueren. Man legt einfach seine rechte (oder linke) Hand an eine Wand des Irrgartens und hält dann beim Durchlaufen ständigen Kontakt. Falls alle Mauern, die man berührt, zusammenhängen oder mit der Außenseite verbunden sind, erreicht man entweder einen anderen Ausgang, oder man kehrt wieder zum Eingang zurück.

Random Maze Generator

In diesem Scratch-Projekt wird zuerst ein zufälliger Irrgarten (mit nur einem Weg zwischen zwei beliebigen Orten!) gezeichnet und dann mit der Linken-Hand-Methode ein Weg gesucht. Die Wände des Irrgartens sind weiß, der Zielpunkt ist rot, die Figur hinterlässt eine gelbe Spur und die suchende Figur hat am Scheitel einen blauen Punkt und am rechten Ohr einen roten. Dadurch sind Abfragen wie "Farbe blau berührt weiß?" möglich. Wenn der blaue Punkt der Figur weiß (also die Wand des Irrgartens) oder gelb (die eigene Spur) berührt, dann soll die Figur nach links abbiegen (also mit der linken Hand der Wand folgen). Wenn das rote Ohr weiß oder gelb berührt, dann soll die Figur vorwärts gehen, ansonsten rechts abbiegen.

Der von Canthiar in seinem "Random Maze Generator" verwendete Lösungsalgorithmus läuft bei dem Irrgarten des oben verlinkten Youtube-Videos in eine Endlosschleife:

Auch versagt dieser Algorithmus, wenn der Startpunkt im Inneren des Irrgartens bei einer Insel liegt:

Der Pledge-Algorithmus wurde von dem 12-jährigen John Pledge erfunden. Er folgt auch Wänden, aber kann auch Hindernisse umrunden. Dabei werden bei jedem Abbiegen die Abbiegewinkel addiert. Trifft man auf ein Hindernis, legt man eine Hand (zum Beispiel immer die rechte) auf das Hindernis und hält auf dem weiteren Weg den Kontakt aufrecht. Ist die Summe der gemachten Drehungen gleich Null, dann ist man wieder in die ursprüngliche Richtung ausgerichtet. Man löst die Hand vom Hindernis und geht wieder geradeaus weiter. Mit dem Pledge-Algorithmus kann man aus einem Irrgarten herausfinden. Für das Finden des Zentrums ist er nicht geeignet. Damit ein Mensch diese Methode verwenden kann, benötigt er einen Kompass.

Das Rekursive Rücksetzverfahren findet mit Sicherheit eine Lösung, aber nur eine, die nicht unbedingt die kürzeste sein muss. Durch die Verwendung von Rekursion benötigt es einen Stapelspeicher. Dieses backtracking macht depth first search ("Tiefe-Zuerst-Suche"), der Algorithmus versucht also möglichst weit in den Irrgarten einzudringen. Gelangt er in eine Sackgasse, dreht er um bis zur letzten Kreuzung, markiert den gegangenen Weg als besucht und nimmt einen anderen Weg.

Der Algorithmus von Trémaux ist ein rekursives Rücksetzverfahren, das von Menschen ausführbar ist. Der Algorithmus ist sehr gut in Wikipedia beschrieben.

Der Mathematiker Gaston Tarry verbesserte und verallgemeinerte den Algorithmus von Trémaux. Seine Methode funktioniert hinein und hinaus. Sollte es keinen Ausgang geben, dann endet der Algorithmus wieder am Startpunkt.

1. Wenn du einen Gang betrittst, markiere den Eingang mit dem Wort Stopp. Betritt nie einen Gang, der mit Stopp markiert ist.
2. Betrittst du das erste Mal eine Kreuzung (daran erkennbar, dass an keinem Gang eine Markierung angebracht ist), markiere den eben verlassenen Gang mit dem Wort zuletzt.
3. Gibt es an einer Kreuzung Gänge, die keine Markierung besitzen, wähle einen beliebigen davon, um weiterzugehen. Sollte es keine unmarkierten Gänge mehr geben, betritt den mit zuletzt markierten Gang.

Der Kürzesten-Weg-Finder macht breadth first search, er sucht also in die Breite. Das ist vergleichbar damit, wenn man vom Startpunkt (und in Folge von jeder Kreuzug aus) alle Wege mit "Wasser" füllt. Damit werden gleichzeitig mehrere, aber immer gleich lange Wege untersucht. Derjenige Weg, der das Ziel erreicht, ist der kürzeste.

Beim Amöbenlöser wird wie beim Kürzesten-Weg-Finder vorgegangen, nur wird an jeder Stelle, wo zwei Suchwege aufeinander treffen, eine Mauer eingezogen. Dieser Algorithmus findet alle kürzesten Wege (wenn es mehr als einen gibt).

Der gängigste Micromouse-Algorithmus ist der Überschwemmungsalgorithmus (flood-fill algorithm). Bei Micromouse-Wettbewerben liegt das Ziel immer in der Mitte des Irrgartens. Die Maus verwendet eine Landkarte des Irrgartens, bei der jeder Zelle eine Entfernung zur Mitte zugeordnet ist. Anfangs haben alle Ecken den Wert 16, die Mitte hat 0. Und die Landkarte hat keine Mauern, da der Maus der Irrgarten noch nicht bekannt ist. Beim Fahren durch den Irrgarten trägt die Maus alle Mauern in die Landkarte ein und verändert entsprechend die Entfernungswerte. Die Maus bewegt sich immer in Richtung niedrigerer Werte.

weitere Algorithmen

• Sackgassenfüller (dead end filler)
• Schlingenfüller (cul-de-sac filler)
• Sackgassenversiegler (blind alley sealer)
• partition-central algorithm
• genetische Algorithmen

weitere Informationen

• Wikipedia: Lösungsalgorithmen für Irrgärten