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
Beweis
Aus den Lemmas folgt:
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.