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 ?