2000 By Alexander Hombach
Bewegungsplanung bei unvollständiger Information
Übersicht - Einführung – Sichtbarkeitsgraph - Definition eines Modells – Lozano-Pérez – Der Roboter - Problemstellung - Strategie 1 – Strategie 2 – Der Pledge-Algorithmus – Beweis des Pledge-Algorithmus 1/2/3 Beweis
6. Problemstellung
Gegeben ist ein punktförmiger Roboter, der nur über einen Tastsensor und einen Winkelzähler verfügt.
Der Winkelzähler addiert bei einer Linksdrehung den Winkel zum aktuellen Stand und bei einer Rechtsdrehung wird der Drehwinkel subtrahiert. Bei Beginn steht der Zähler auf 0
Wenn der Roboter auf ein Hindernis trifft dreht er sich immer nach rechts um seinen Weg fortzusetzen.
Gesucht ist eine Strategie, mit deren Hilfe dieser Roboter aus jedem unbekannten Labyrinth herausfindet, aus dem es überhaupt einen Ausweg gibt.
Der Roboter ist aus dem Labyrinth entkommen, wenn er die konvexe Hülle der Hindernisse erreicht oder passiert hat. Wenn dies schon zu Anfang zutreffen sollte bleibt er stehen.
Problemstellung