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
10. Beweisstrategie:
Behauptung: Der Pledge-Algorithmus findet in jedem Labyrinth von jeder Startposition aus einen Weg ins Freie, wenn dieser Weg existiert.
Beweisstrategie
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.
q.e.d (Erklärung folgt...)