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
1. Einführung in die Problematik
Daraus ergeben sich folgenden Effizienzkriterien für einen Algorithmus in unbekanntem Gelände:
-Die Rechenzeit die benötigt wird um einen Ausweg zu finden.
- Die Länge des Weges der bis zum Ausgang gegangen wurde im Verhältnis zum kürzesten existierenden Weg.
Einführung
- Es geht um Wegfindungsroutinen für unbekannte „Labyrinthe“ damit z.B. Roboter unbekannte Umgebungen kartographieren oder einen kürzesten Weg suchen.
Worum geht’s es überhaupt?
- Ein Labyrinth kann zum Beispiel ein klassisches sein (Lagerhalle und ähnliches) oder ein Gelände mit Start- und Zielpunkt welches Hindernisse enthält z.B. die Pathfindersonde.
- Das Problem dabei ist, dass derjenige welcher das Labyrinth kennt sofort einen kürzesten Weg zum Ausgang berechnen kann wohingegen man in einer unbekannten Umgebung nicht einmal weiß ob es überhaupt einen Ausgang gibt.
- Gibt es überhaupt einen Algorithmus der einen Weg aus einem Labyrinth findet, wenn dieser existiert ?