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
Lemma 1: Der Winkelzähler nimmt niemals einen positiven Wert
an.
Lemma 2: Wenn der Roboter nicht herausfindet dann besteht sein
Weg bis auf ein endliches Anfangsstück
aus einem geschlossenem Weg, der immer wieder durchlaufen wird (Endlosschleife).
Lemma 3: Der Weg kann sich nicht selbst kreuzen. Der Roboter
läuft also keine Schleifen.
Beweis:
Angenommen der
Roboter durchliefe den Weg p gegen den
Uhrzeigersinn. Dann erhöht sich der WZ
bei jedem Durchlauf um 2pi und wird irgendwann
positiv. Dies ist jedoch wegen Lemma 1
unmöglich.
Der Roboter
durchläuft also den Weg p im Uhrzeigersinn und der WZ erniedrigt sich bei
jedem Durchlauf um 2pi. Irgendwann
ist ein Stadium erreicht wo der WZ auf keinem Teilstück von p größer oder
gleich 0 ist. Der Roboter wird sich also nie
mehr von einer Hinderniswand lösen und da er im Uhrzeigersinn läuft muss er
sich in einem Innenhof befinden, aus
dem es keinen Ausweg gibt, denn sonst würde er eine Schleife durchlaufen, was wegen Lemma 3 ausgeschlossen
ist.
Damit ist
bewiesen, das der Pledge-Algorithmus aus jedem Labyrinth entweder einen Ausweg
findet oder den Roboter in endlos im
Kreis laufen lässt falls kein Ausweg existiert.