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
2. Der Sichtbarkeitsgraph
Berechnung des kürzesten Weges in einem bekannten Labyrinth:
Die Berechnung lässt sich mittels eines Algorithmus bewerkstelligen der das Problem auf Graphen reduziert.
-Der Graph enthält als Knoten den Start- und Zielpunkt und alle Hindernisecken.
-Alle Knoten, welche direkten Sichtkontakt haben werden miteinander verbunden
Nun wendet man auf diesen Graphen den Algorithmus von Dijkstra an um den kürzesten Weg von vom Anfangsknoten zum Endknoten zu finden.
Sichtbarkeitsgraph