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
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.