23
Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckman Prof. Dr. Bernd Krieg-Brückner Dr. Bernd Gersdorf

Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Embed Size (px)

Citation preview

Page 1: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Topologische Navigation:Der Routengraph

Navigation Autonomer Mobiler Systeme

WS 07/08

Thomas Wolfram, Björn Beckmann

Prof. Dr. Bernd Krieg-BrücknerDr. Bernd Gersdorf

Page 2: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Route

Segment

• gerichtete Kante• verbindet 2 Plätze• Start und Ziel• Eingang, Verlauf,

Ausgang

Platz

• Knoten• Entscheidungspunkt• Position, Ausrichtung• Referenzsystem

Referenzposition

Page 3: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr
Page 4: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr
Page 5: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr
Page 6: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Beispiel Route: GW2

Page 7: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

• betritt GW2 durch Eingang

B1400

• gehe geradeaus auf die Treppe zu

• drehe Dich rechts, gehe zum nächsten Flur

• folge dem Flur bis zur Tür des ersten Raums auf der linken Seite

• drehe Dich zur Tür, tritt ein

Page 8: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Route Segment

• Start: Eingangstür GW2

• Eingang: drehe Dich zur Tür

• Verlauf: Folge dem Flur bis zur Treppe

• Ausgang: Drehe Dich zur Treppe

• Ziel: Flur, Ausrichtung zur Treppe

B1400

Page 9: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Route Segment

• Start: Flur, Ausrichtung zur Treppe

• Eingang: drehe Dich nach rechts

• Verlauf: Folge dem Flur bis zum nächsten Korridor

• Ausgang: Drehe Dich zum Flur

• Ziel: vor dem Korridor, Ausrichtung zum Korridor

B1400

Page 10: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Routengraph

• Vereinigung mehrerer Routen,also ihrer Segmente und Plätze

• Bedingung: Routen sind Homogen

• Schwierig: Integrieren von Plätzen– Allgemeines Referenzsystem und Referenzposition nötig

Page 11: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Lagen und Abstraktion

• Verschiedenartige Routengraphen trennen– Beispiel Bahnhof

• Routenwissen undÜbersicht

• Robotlevel – Userlevel

Page 12: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Transfer

• Verbindung heterogener Routen

• Im Bild:– Bahnstrecken– Fußwege– Transfer Segmente

Page 13: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr
Page 14: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Routenbasierende Navigation bei Tieren

• Nahrungssuche bei Tieren (Nagetiere, Insekten…)• Wanderung bei Tieren (Vögel, Fischen,

Meeresschildkröten…)• Modell von Poucet (1993)

– Platz Repräsentation– Platz: Ansammlung von verketteten Ansichten– Lokales Referenz-System

• Verbindung von 2 Plätzen

• Richtung, Distanz

– Topologisches Netzwerk• Verbundenheit der Plätze

• Reihenfolge

Page 15: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Beispiel: Wüstenameise

• Wege-Integration– Homing Vector = Richtungswechsel u. Distanz– Angeborener Kompass

• Fehlervermeidung• Richtungsanzeige

• Für alle Spezies die gleiche Thematik1. Plätze erkennen

2. Erwartungen aufbauen

3. Navigationsentscheidungen treffen

Page 16: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Routenbasierende Navigation bei Robotern

• Ähnlichkeit zwischen „biologischer“ und „künstlicher“ Navigation kein Zufall

• Unterschiede:– Moderne Technologie (Sensoren)– Kombination von Sensoren– Agenten kennen ihre Umgebung

• Vier Arten von Navigation– Guidance, Place Recognition - Triggered Response,

Topological Navigation, Metrical Navigation

Page 17: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Guidance

• Leiten des Agenten– bis das sensorische Bild passt– handelt um Kriterien zu maximieren

Beispiel:

Agent fährt entlang einer Wand

Page 18: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Platzerkennung - ausgelöste Reaktion

• Wenn Platz erkannt → bestimmte Aktion• Hauptproblem: Erkennung des Platzes

1. Ansatz: wahrzunehmender Input

2. Ansatz: Merkpunkte erkennen

‼ Problem: Verschiedene Plätze → ähnlicher Input

‼ Problem: Sensorische Störungen

Page 19: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Topologische Navigation

• basierend auf topologischen Netzwerken• Erweiterung von „Platzerkennung - ausgelöste Reaktion“

Navigation• Elemente: Plätze und deren Verbindungen

‼ Problem: Durch das navigieren– keine neuen Plätze– keine neuen Verbindungen

Page 20: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Metrische Navigation

• keine Unterteilung des Raumes in Plätze• Navigation durch Entfernung und Winkel (Euclidean)• Karten spezifieren metrische Relationen• Sensorische Erfassung, Triangulation• grobes Beispiel: Occupancy Grids

Vorteile– Agent kennt seine Position und– deren Beziehung zu anderen Objekten

Page 21: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Routenbasierende Navigation bei Menschen

• Weg- / Routenbeschreibung, Skizze• Startpunkt, Endpunkt, Zwischenpunkte• Sehenswürdigkeiten, charakteristische Elemente• Sequenz von Plätzen → jeder Platz neuer

Entscheidungspunkt

Modelling Navigational Knowledge by Route Graphs

Page 22: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Exkurs: Ontologie

Lehre des Seins, Disziplin der theoretischen Philosophie

Informatik: “An ontology is an explicit specification of aConceptualization.”

Wissensrepräsentation, Begriffe und Relationen

Page 23: Topologische Navigation: Der Routengraph Navigation Autonomer Mobiler Systeme WS 07/08 Thomas Wolfram, Björn Beckmann Prof. Dr. Bernd Krieg-Brückner Dr

Wir wissen:Place8210: Node_IndoorsKRegion8210: RegionOffice8210: OfficePlace8210 locatedIn Region8210 und Region8210 covers Office8210

Wissen ableiten:Place8210 containedIn Office8210