Anleitung

Mit einem Linksklick auf die gestrichelten Feldränder können Wände gesetzt werden. Mit einem Rechtsklick auf eine Wand wird diese entfernt. Ein Linksklick auf die Mitte eines Feldes setzt den Startpunkt, ein Rechtsklick setzt das Ziel.

Der Algorithmus

Dieser Algorithmus findet ein Ziel in einem gitterförmigen Labyrinth. Dieses Labyrinth besteht also aus einzelnen quadratischen Zellen, zwischen denen sich der Roboter horizontal und vertikal bewegen kann. Jede Zelle kann auf jeder Seite durch eine Wand begrenzt werden, die den Roboter an der Bewegung in diese Richtung hindert. Folgende Schritte werden ausgeführt :

Dieser Algorithmus findet letztendlich immer die Zielzelle, jedoch ist der gelaufene Weg meistens sehr ineffizient. Der Roboter nimm einen recht großen Umweg oder läuft große Teile des Wegs zwischen Start und Ziel mehrfach ab.

Shannon demonstrierte den Algorithmus 1950 mit einer mechanischen "Maus" in einem 5x5 Felder großen Labyrinth. Die einzelnen Felder konnten mittels Aluminiumwänden abgetrennt werden. Die Maus konnte sich achsenparallel von Feld zu Feld bewegen und durch einen Touchsensor die an das Feld angrenzenden Wände erkennen sowie den Zielpunkt idendifizieren.

Autor: Jörg Wegener

Literatur:

[1]:Claude E. Shannon. Presentation of a maze solving machine. In H. von Foerster, M. Mead, and H. L. Teuber, editors, Cybernetics: Circular, Causal and Feedback Mechanisms in Biological and Social Systems, Transactions Eighth Conference, 1951, pages 169–181, New York, 1952. Josiah Macy Jr. Foundation. Reprint in [2].
[2]:Claude E. Shannon. Presentation of a maze solving machine. In Neil J. A. Sloane and Aaron D. Wyner, editors, Claude Shannon: Collected Papers, volume PC-03319. IEEE Press, 1993.
[3]:Rolf Klein, Elmar Langetepe, Tom Kamphans. Offline-Bewegungsplanung.