Wie komme ich im Dunklen aus einem Labyrinth wieder heraus?



1. An der Wand entlang
Wenn der Roboter auf ein Hindernis trifft, dreht er sich rechtsherum und läuft an der Wand entlang. Die Wand befindet sich dabei immer links von ihm.
Problem: kein Erfolg bei z. B. einer Säule







2. Möglichst in Anfangsrichtung
Roboter läuft in die Anfangsrichtung, wenn seine Nase in diese Richtung zeigt.
Problem: Endlosschleifen drohen







3. Pledge Algorithmus
Der Pledge-Algorithmus findet in jedem Labyrinth von jeder Startposition aus, von der überhaupt ein Ausweg existiert, einen Weg ins Freie.

Ein Zähler wird in den Roboter eingebaut. Am Anfang ist der Zähler auf 0 eingestellt.
Trifft der Roboter auf ein Hindernis, so dreht er sich nach rechts und der Zähler wird um 1 verringert.
Nun läuft der Roboter an der Wand entlang. Jedes Mal, wenn er sich dabei wieder in die selbe Richtung dreht, wird vom Zähler 1 abgezogen; dreht er sich linksherum, so zählt man 1 dazu.
Ist der Zähler gleich 0, so verlässt der Roboter die Wand und läuft geradeaus weiter, bis er das nächste Hindernis erreicht.

Formel des Pledge-Algorithmus

wähle Richtung := beliebig;
Winkelzähler := 0;
repeat
repeat folge Richtung until Wandkontakt;
repeat folge der Wand until Winkelzähler = 0
until entkommen