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 3 (Der Weg des Roboters kann sich nicht kreuzen):
A
B
Gegeben:
-Am Punkt z trifft das Wegstück B auf A (beides Segmente des Weges p). Seien Wa(z´) und Wb(z´) die Zählerstände am Punkt z´ kurz hinter z.
-Wb(z´) = -ß mit 0 <=  ß < Pi
-Wa(z´) = -ß + k2pi mit k e Z
Lemma3
Fallunterscheidung für k:
-k >= 1 : Wa(z´) = -ß + k2pi > -Pi + 2pi = Pi. Das widerspricht allerdings Lemma 1.
- k = 0 : Wa(z`) = Wb(z`). Das würde nach Lemma 2 bedeuten, das sich A und B nicht wieder trennen und nur ein Segment der beiden wieder auf z treffen würde
- k <= -1 : Wa(t) < Wb(t) für z`< t < v und da bei v Wb(v) = 0 und Wa(v) <> 0 trennen sich beide Segmente wieder. Sie haben sich also berührt und nicht geschnitten.