Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 1
FußgängernavigationGraph – basierte Routenplanung
versusGeometrische Routenplanung
Philipp Zeimetz
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 2
Graph – basierte Routenplanung
Geometrische Routenplanung
109
8
76
54
32
1
Erinnerung und Ausblick
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 3
Graphen-basierte Routenplanung
Wir kennen aus der diskreten Mathematik II:• Algorithmus von Dijkstra
– Alle kürzesten Wege von einem Knoten– Laufzeit O(e + n log n) (mit fibonacci Heaps)
( n / e = Anzahl der Knoten / Kanten )
• Algorithmus von Floyd– Kürzesten Wege zwischen allen Paaren von Knoten– Kosten O (n³)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 4
Unterschiede Was unterscheidet die beiden Verfahren:• Graphen-basierte Routenplanung:
– Ableitung der Topologie aus der Geometrie– Repräsentation der Topologie durch Graphen Ableitung eines Graphen aus der Geometrie Der Graph besteht aus nicht negativ gewichtete Kanten
• Geometrische Routenplanung– Keine Abstraktion der Geometrie– Repräsentation der Geometrie durch Polygone– Geometrie dient als Grundlage der Berechnungen– Berechnung und Ausgabe einer Trajektorie
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 5
Motivation
• Bewegung wird nicht auf wenige Kanten beschränkt– Fußgänger bewegen sich freier als Züge oder Autos!
• Eine exakte Trajektorie wird berechnet– Robotik– Schifffahrt
Wo liegen die Vorteile der geometrischen Routenplanung?
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 6
geometrische Routenplanung
Vorgehen:• Zerlegung des freien Raums• Erstellung des Verbindungsgraphen• Punktlokalisierung in Landkarten• Berechnung der möglichen Wege
- Verwendung von Trichtern (funnel)• Ausgabe einer Wegebeschreibung
- Liefert eine Koordinaten Liste
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 7
Das Verfahren ist sehr Komplex!
Wir beschränken uns auf folgende Fälle:• Wir bewegen uns im zweidimensionalen• Die Karte ist uns bekannt• Die Karte besteht aus Polygonen• Die Position ist uns bekannt• Fußgänger haben keine Ausdehnung
- Existiert eine Verbindung zwischen zwei Hindernissen, so passen Fußgänger auch hindurch
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 8
Die Karte
freier Raum Hindernisse
Besteht aus:
Einem begehbaren Polygonmit
vielen unbegehbaren Löchern(ebenfalls Polygone)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 9
freier Raum Hindernisse
Zellzerlegung
Zerlegung der Karte in einfache Polygone:
• Bestimmung von Minima und Maxima
der Hindernispolygone
12 34 5
6 7
89
10
• Nummerierung der neuen Kacheln• Berechnungskosten: O (n)
• Einfügen Horizontaler Kanten
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 10
Gewinn der Zerlegung I
freier Raum Hindernisse12 34 5
6 7
89
10
• es entstehen einfache Polygone• der gesuchte Weg verläuft zwischen linker und rechter Begrenzung• „Auswüchse“ werden nicht besucht
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 11
Gewinn der Zerlegung II
freier Raum Hindernisse12 34 5
6 7
89
10
„Höhlen“ werden im Graph zu toten Enden
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 12
Punktelokalisierung
freier Raum Hindernisse12 34 5
6 7
89
10
I
II In welchem Polygon liegen End- und Anfangspunkt?
• Durch Zellzerlegung entsteht eine Karte, welche an die Trapezkarte aus GIS III
• Laufzeit: O (n log n)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 13
88
Verbindungsgraph
11
66
32
2 3
77
freier Raum Hindernisse
54
4 5
9
10
910
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 14
10
9
8
76
54
32
1
Jeder Knoten repräsentiert eine KachelJede Kante repräsentiert die Verbindungder begrenzenden KachelnVon jeder Kachel geht mindestens eine Kante und maximal vier Kanten ab
Verbindungsgraph
Eigenschaften des Verbindungsgraphen:
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 15
Laufzeitkosten
freier Raum Hindernisse12 34 5
6 7
89
10
Betragen zusammen: O (n log n) (n ist die Anzahl der Knoten)
I
II
Zellzerlegung+
Verbindungsgraph+
Punktlokalisierung
Die Laufzeitkosten für:
O (n)+
O (n)+
O (n log n)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 16
freier RaumHindernisse
12 34 5
6 7
89
10
I
II 10
9
8
76
54
32
1
Suche möglicher Wege
Algorithmus: A*
Laufzeit: O (n)
Nachteil: jeder Kante muss geprüft werden
Aber: auch jede Region max. zwei mal
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 17
Trichtern (funnel)
Linke Kette Rechte Kette
• Der Quellpunkt liegt stets auf dem kürzesten Weg
• Der kürzeste Weg verläuft stets über konvexe Punkte
Quellpunkt
• Die linke Kette verläuft über konvexe Punkte der linken Begrenzung
• Die rechte Kette verläuft über konvexe Punkte der rechten Begrenzung
Konvexe Punkte
• Die Ketten bewegen sich voneinander weg
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 18
freier Raum Hindernisse12 34 5
6 7
89
10
I
II
86421
Ein einfaches Beispiel
• Der kürzeste Weg verläuft stets über konvexe Punkte
• Der Winkel zwischen den Ketten ist minimal
• Die Ketten bewegen sich voneinander weg
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 19
Geometric Route Planning
1
3
2
4
6
78 9
10
5
A*
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 20
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 21
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 22
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 23
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 24
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 25
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 26
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 27
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 28
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 29
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 30
1
3
2
4
6
78 9
10
5
Geometric Route Planning
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 31
Beschreibung des Weges
Die Koordinaten aller Knickpunkte werden ausgegeben.
Die Streckenlänge berechnet sich nach:
Freier Raum Kartenobjekte
1
1
21
21
m
iiiii yyxxS
Wobei m die Anzahl der Stützpunkte ist
12 34 5
6 7
89
10
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 32
Ein Problemfall ???
8
10
9
6
7
4
5
32
1
21
34
5 67
8 910
12
13
11
13
11 12
n = # Knoten = 16h = # Löcher = 4
Für n = 50 max h = 15# Wege: 32768# d. Regionen: 61
Tiefe des Baums:2h + 1 = 9 (max)
# möglicher Wege:2h = 16
Anzahl Regionen:3h + 1 = 13 (max)Durchlaufene Regionen:4h + 1 = 17 (max)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 33
Ein Problemfall ???
Anzahl der Sichtbarkeitsüberprüfungen: n²
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 34
Ein Spezialfall
Freier Raum Kartenobjekte
Endpunkt und Startpunkt liegen in einem Polygon
Lösung: • Ergänzung der Zellzerlegung• Algorithmus von Lee und Preparata• ... weitere Methoden ...
Problem: Bei komplexen Polygonen ist die Orientierung schwierig
I
II
Freier Raum Kartenobjekte12 34 5
67
89
10
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 35
Ergänzung der Zellzerlegung
Ergänzung:
Einfügen zweier weiterer horizontaler Kanten an Start- und Endpunkt
Beachte:• der Verbindungsgraph verändert sich• die Nummerierung muss erneuert werden
11
12
I
II
Freier Raum Kartenobjekte12 34 5
67
89
10
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 36
Algorithmus: Lee und Preparata
1. Schritt:• Triangulation des beliebigen, lochfreien Polygons• Berechnungskosten: O (n) wobei n die Anzahl der Knoten ist
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 37
Algorithmus: Lee und Preparata
2. Schritt:• Erstellung eines Graphen• zwei Dreiecke sind benachbart, wenn sie gemeinsame Seiten haben
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 38
Algorithmus: Lee und Preparata
3. Schritt:• Suche des einzigen Weges
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 39
Algorithmus: Lee und Preparata
3. Schritt:• Suche des einzigen Weges
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 40
Algorithmus: Lee und Preparata
4. Schritt:• Anwendung der Trichter
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 41
Trichter AlgorithmusDie Regeln für die Trichter sind hier etwas anders:
• die Endpunkte der Ketten müssen keine Konvexe Punkte sein
• die Ketten verlaufen immer über die nächst möglichen
konvexen Punkte Kriterium der kleinsten Winkel gilt nicht
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 42
Algorithmus: Lee und Preparata
4. Schritt:• Anwendung der Trichter
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 43
Algorithmus: Lee und Preparata
4. Schritt:• Anwendung der Trichter
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 44
LaufzeitkostenKosten für die Suche in einem einfachen PolygonAlgorithmus nach Lee und Preparata: O (n)Setz die Polygon-Triangulation voraus: O (n)
Kosten für die Suche in einem komplexen PolygonZellzerlegung + Verbindungsgraph + Punktlokalisierung: O (n log n)Wegsuche mit A*-Algorithmus: O (n)
Gesamtlaufzeitkosten: O(n²) + ... Trichterkonstruktion: O (n²)
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 45
Vergleich der Verfahren ILaufzeitkosten der Algorithmen:
• Graphbasierte Routenplanung- Dijkstra O(e + n log n)
• Geometrische Routenplanung- O (n²) + ...
Ergebnis des Vergleichs:Die geometrische Routenplanung ist Aufwendiger
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 46
Vergleich der Verfahren IIProjektrelevante Eigenschaften I• Geometrische Routenplanung erfordert einen größere
Rechenleistung- Rechenleistung mobiler Endgeräte noch beschränkt
• Fußgänger wollen wissen welche Straße sie gehen sollen; nicht wie sie entlang der Straßen laufen sollen
• Die Ausgabe der Routen soll per Video erfolgen, wodurch bereits eine linienhafte Abstraktion des Weges gegeben ist
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 47
Vergleich der Verfahren III
Projektrelevante Eigenschaften II• An Plätzen will der Fußgänger wissen in welche Straße er biegen muss; wie er das macht weiß er vermutlich
• Die Modellierung von z.B. Straßenübergängen oder Ampel- anlagen ist bei der geometrischen Variante schwieriger
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 48
Vergleich der Verfahren IV
Graph – basierte Routenplanung:• Modellierung von Rolltreppen, Aufzügen etc. durch Kanten
Voraussetzungen:Routenplanung in mehreren „Kaufhausebenen“:
Zukunftsaussichten:In der Zukunft soll auch die „Kaufhausnavigation“ möglich sein
76
54
32
1
DamenabteilungEG 1110
129
14813
Herrenabteilung UG
Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 49
Vergleich der Verfahren V
Graph – basierte Routenplanung:• Modellierung von Parkplätzen durch Knoten
Zukunftsaussichten:In der Zukunft soll auch „park and go“ möglich seinVoraussetzungen:Kombination mehrerer Verkehrsmittel:
76
54
32
1
1110
129
813
Auto3
Fußgänger
76
54
32
1
1110
129
813
Auto3
Fußgänger
Parkplatz