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