Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/031 Fußgängernavigation Graph –...

Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/03 1

FußgängernavigationGraph – basierte Routenplanung

versusGeometrische Routenplanung

Philipp Zeimetz

Graph – basierte Routenplanung

Geometrische Routenplanung

Erinnerung und Ausblick

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³)

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

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?

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

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

Die Karte

freier Raum Hindernisse

Besteht aus:

Einem begehbaren Polygonmit

vielen unbegehbaren Löchern(ebenfalls Polygone)

Zellzerlegung

Zerlegung der Karte in einfache Polygone:

• Bestimmung von Minima und Maxima

der Hindernispolygone

12 34 5

• Nummerierung der neuen Kacheln• Berechnungskosten: O (n)

• Einfügen Horizontaler Kanten

Gewinn der Zerlegung I

freier Raum Hindernisse12 34 5

• es entstehen einfache Polygone• der gesuchte Weg verläuft zwischen linker und rechter Begrenzung• „Auswüchse“ werden nicht besucht

Gewinn der Zerlegung II

„Höhlen“ werden im Graph zu toten Enden

Punktelokalisierung

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)

Verbindungsgraph

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:

Laufzeitkosten

Betragen zusammen: O (n log n) (n ist die Anzahl der Knoten)

Zellzerlegung+

Verbindungsgraph+

Punktlokalisierung

Die Laufzeitkosten für:

O (n)+

O (n log n)

freier RaumHindernisse

12 34 5

Suche möglicher Wege

Algorithmus: A*

Laufzeit: O (n)

Nachteil: jeder Kante muss geprüft werden

Aber: auch jede Region max. zwei mal

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

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

Geometric Route Planning

Beschreibung des Weges

Die Koordinaten aller Knickpunkte werden ausgegeben.

Die Streckenlänge berechnet sich nach:

Freier Raum Kartenobjekte

iiiii yyxxS

Wobei m die Anzahl der Stützpunkte ist

12 34 5

Ein Problemfall ???

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)

Ein Problemfall ???

Anzahl der Sichtbarkeitsüberprüfungen: n²

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

Freier Raum Kartenobjekte12 34 5

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

Freier Raum Kartenobjekte12 34 5

Algorithmus: Lee und Preparata

1. Schritt:• Triangulation des beliebigen, lochfreien Polygons• Berechnungskosten: O (n) wobei n die Anzahl der Knoten ist

2. Schritt:• Erstellung eines Graphen• zwei Dreiecke sind benachbart, wenn sie gemeinsame Seiten haben

3. Schritt:• Suche des einzigen Weges

4. Schritt:• Anwendung der Trichter

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

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²)

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

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

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

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

DamenabteilungEG 1110

Herrenabteilung UG

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:

Fußgänger

Parkplatz

Philipp Zeimetz - Navigation mit GIS - 7. Semester - WS 02/031 Fußgängernavigation Graph –...

Documents

Über Routenplanung und Suchmaschinen

Johann Philipp Ries

Algorithmen für Routenplanung€¦ · Juni 2011 14. Sitzung, Sommersemester 2011 Algorithmen für Routenplanung INSTITUT FÜR THEORETISCHE INFORMATIK ROFALGORITHMIK I P . DR. DOROTHEA

Kalibrierung von GNSS- Antennen in Hörsaal 16 · Philipp Zeimetz, Barbara Görres, Heiner Kuhlmann (Uni-Bonn) Matthias Becker, Erik Schönemann (TU-Darmstadt) Bonn, 21.09.2006 Kalibrierung

Algorithmen für Routenplanung - KIT - ITI Algorithmik I · Heute: Routenplanung in Bahnnetzen (Fahrplanauskunft) Thomas Pajor – Algorithmen für Routenplanung 20. Juni 2011

Algorithmen für Routenplanung -- Vorlesung 7

Algorithmen fur¨ Routenplanung - KIT - ITI Algorithmik I · Probleme z. B. Vertex-Cover, 3-Color, Independent Set Mehr dazu spater¨ Ben Strasser – Algorithmen f¨ur Routenplanung

Danke, philipp!

Georg Philipp Telemannlievens.biz/gitaar/sheet/telemann_konzert_fur_4_violinen...Konzert für 4 Violinen ohne Bass D-Dur Georg Philipp Telemann Georg Philipp Telemann, Duitsland, 14

PHILIPP Flachstahlanker...PHILIPP Flachstahlanker 2 219 PHILIPP mbH, 63741 Aschaffenburg Technische nderungen sowie Irrtümer vorbehalten Oktober 219 Transport- und ontagessteme für

Intermodale Routenplanung

Meilen- und Ausbildungstörns · – Manövertraining – Boat handling – Routenplanung – Wetter – Sicherheit auf See – Einkaufslisten – Chargenplan – Crew Einweisung

Kerncurriculum für das Fach Mathematik Klasse 2 Philipp ...philipp-reis.gelnhausen.schule.hessen.de/fach/mathematik...Kerncurriculum für das Fach Mathematik – Klasse 2 Philipp-Reis-Schule

Philipp vorndran

Algorithmen für Routenplanung · wegen Dreiecksungleichung (M-UGL) ku vk 2 +kv tk 2 ku tk 2 Thomas Pajor – Algorithmen für Routenplanung Folie 8 – 24.04.2013 Institut für Theoretische

Praktikum Routenplanung - Themenvorstellung ... · INSTITUT F ¨UR THEORETISCHE INFORMATIK ALGORITHMIK PROF. DR. DOROTHEA WAGNER Praktikum Routenplanung Themenvorstellung & Gruppeneinteilung,

Andreas Hartknopf · 2006. 6. 28. · Andreas Hartknopf Author: Karl Philipp Moritz Subject: Karl Philipp Moritz: Andreas Hartknopf. Eine Allegorie Keywords: Karl Philipp Moritz:

Praktikum Routenplanung - Vorbesprechung, Wintersemester ......Praktikum Routenplanung Vorbesprechung, Wintersemester 2018/2019 Valentin Buchhold, Jonas Sauer, Tim Zeitz, Tobias Z¨undorf

Runenhäuser - Philipp Stauff

Georg Philipp Telemann