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
3. Definition eines Modells
Um nun einen funktionierenden Algorithmus für fremde Labyrinthe auf die Beine stellen zu können müssen wir zuerst das Labyrinth und den Roboter genauer definieren.
Das Labyrinth:
-endliche Menge von einfach geschlossenen polygonalen Ketten.
-Je zwei von ihnen sollen sich nicht schneiden.
-Die Ketten bilden die Ränder der Hindernisse (Wände).
-Hindernisse müssen nicht massiv sein.
-Um zu wissen was Hindernis und was freier Raum ist wird das Gebiet von Außen nach Innen eingefärbt (Sind zwei Knoten eines Graphen benachbart, dürfen sie nicht die gleiche Farbe haben) .
Modelldefinition