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 von Lemma 2 (Endlosschleife) :
Behauptung: Wenn der Roboter nicht herausfindet dann besteht sein Weg bis auf ein endliches Anfangsstück aus einem geschlossenem Weg p, der immer wieder durchlaufen wird.
Erklärung:
- Der Weg des Roboters besteht aus einer polygonalen Kette deren Knoten die Eckpunkte der Hindernisse darstellen.
-Wenn der Roboter einen Punkt seines Weges mehrmals und mit dem gleichen Zählerstand wie beim vorherigen Mal betritt, wiederholt er den Weg zyklisch, d.h er ist in einer Endlosschleife.
-Wenn aber jeder Eckpunkt höchstens einmal mit dem selbem Zählerstand besucht wird, erreicht der Roboter nur endlich oft Eckpunkte mit ZS=0. Sobald diese Besuche erfolgt sind, kann der Roboter nie wieder eine freie Bewegung ausführen; er folgt also danach nur noch einer Wand, und sein Weg wird zyklisch.
Lemma2