Navigation Autonomer Mobiler Systeme Füßgängernavigation Veranstalter Prof. Dr. Bernd Krieg-Brückner Dr. Bernd Gersdorf Hoang Thach Vu Saber Bedoui Bremen

Navigation Autonomer Mobiler Systeme

Füßgängernavigation

Veranstalter

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

Hoang Thach Vu

Saber Bedoui

Bremen 06-12-2007

http://www.informatik.uni-bremen.de/%7Ebkb

http://www.informatik.uni-bremen.de/%7Ebernd

http://www.informatik.uni-bremen.de/%7Ebernd



Inhalt:1. Anwendungsbereiche

2. Besonderheiten

3. Positionierungsteknik

4. Algorithmen für Polygonen & Graphen im Innenraum

4.1 Angepasste Umgebungsmodellierung

4.2 Lösungsansatz

4.3 Optimierter Ansatz

5. Räumliche kognitive Landkarte und ein Human-Like Gedächtnis-Modell



1. Anwendungsbereichen

Tourismus Freizeit Navigationshilfe für Behinderte und ältere

Menschen, etc.



2. Besonderheiten

Füßgänger bewegen frei & nicht streng an Straßen gebunden → schwer zu realisieren

Erfordert umfangreichen Datenbestand und Modellierung aller möglichen Gehwege

Benötigt einige Modifikationen an Daten:

Füßgänger brauchen mehr Detailinformationen Straßen nicht als Kanten sondern als Gehwege

dargestellt Objekte wie Füßgängerzonen,Platzüberquerungen,

Ampel,Bahn,Busse,Unter-, Überführungen,Parks, dynamische Daten, Objektebezogene Informationen werden berücksichtigt



2. Besonderheiten

Genauigkeit :

Füßgänger legt kleinere Distanzen zurück . Durch geringere Geschwindigkeit und größeres

Blickfeld mehr Details in der Umgebung wahrnehmen

→ Hohe Speicherkapazität erforderlich und Rechenleistung, die bei tragbaren PCs beschränkt ist

Erhöht sich Anfoderung an Genauigkeit der Positionisierungsverfahren.



2. Besonderheiten



2. Besonderheiten

Abbildung 3: Besonderheiten der Füßgängernavigation beim Überquenren größer Plätze



2. Besonderheiten

Abbildung 4: Füßgänger benutzen in Gebäuden nicht den mathematischen kürzesten Weg



3. Positionierungstecknik

Bestimmt die Position kontinuierlich Wichtige Kriterien:

Transportfähigkeit Hohe Positionsgenauigkeit

Fahrzeugnavisys verwendet relative Sensoren zur Positionierung

Aber bei Füßgängern ist schwer zu verwirklichen → Realisiert mit absoluter Positionierung

Zusätzlich werden Bewegungssensoren verwendet wie zB. Schrittzähler




Absolute Sensoren: liefern direkt eine oder mehrere Komponenten der aktuellen dreidimensionalen Position des Nutzers

GNSS (Global Navigation Satellite System):• Sehr hohe Genauigkeit• Sehr exakte Punktbestimmung (< 1m)• Nachteile : Die Abschattung der Signale durch

Gebäude und der Einfluss des Mehrwegeffektes• Speziell negative Auswirkung auf die

Positionslösung in bebauten Gebieten




Absolute Sensoren: GNSS :

Um zu überdecken

und kontinuierliche

Positionierung zu

ermöglichen müssen

noch weitere Sensoren

verwendet werden

Abbildung 24 : Abschattung und Mehrwegeffekt eines GNSS (Plasinski et al., 2000)




Absolute Sensoren:

LPS: (Local Positioning System)• Ähnlich wie GPS, verwendet zur Positiobestimmung

in Gebäuden• Positionslösung wird bestimmt mittels

Distanzmessung zwischen mehreren Sendern und Antennen.

• Die Empfänger sind direkt im Gebäude installiert• Die Sender sind von den Nutzern mitzuführen

Höhenbestimmung, etc…




Relative Sensoren:

Zum Messen den zurückgelegte Weg, Geschwindigkeit, Richtung sowie die räumliche Ausrichting und die Beschleunigung



4.1 Angepasste Umgebungmodellierung

Die Darstellung der Umgebung mit Knoten und Kanten nicht ausreichend

Zu ermöglichen beliebigen Weg muss das Modell alle begehbaren Flächen beschreiben und darf diese nicht zu Strecken vereinfachen

Mit Editor Yamamoto können solche Umgebungsmodell erstellt werden

Die Kannte besitzen Attribute wie : begehbar für Füßgänger oder nicht begehbar.



4.1 Angepasste Umgebungmodellierung

Abbildung 5 : Beispiel für polygonbasiertes Umgebungsmodell



4.2 Algorithmen für Polygonen und Graphen

Wichtig sind das Ergebnis (kürzer und schöner Weg), sowie Laufzeit und Speicherplatzverbrauch

Grundsätzliche Frage: Polygon- oder graphbasierter Algorithmus besser geeignet?

Polygonbasierte Algorithmen:

Wird verwendet wenn die Modelle nicht als Graph vorlagen, sondern als ein Netz von Polygonen. (Abbildung 5)




Graphenbasierte Algorithmen: Algorithmen für die Wegsuche in folgende Graphen

Abbildung 6: Wegsuche auf dem Campus der Universität Saarbrücken




Graphbasierte informierte Suche:

Graphbasierter Algorithmus, der zielgerichtet sucht und immer den kürzesten Weg findet

Ziel: aus vorhandenen polygonbasierten Umgebungsmodellen die Wegenetz-Graphen zu erzeugen

Zu finden einen “schönen” Weg muss der Wegenetz-Graph möglichst detailiert sein. Aber nicht viele Wegpunkte und Wegkanten um die Suche effizient durchzuführen




Graphbasierte informierte Suche:

Abbildung 7 : Erzeugung der Wegpunkte durch ein Rasterverfahren



4.3 Lösungsansatz zur Generierung von Wegenetzgraphen

Rasterbasierter Ansatz: Erzeugt Wegpunkte in gleichmäßigen Abständen

Wegpunkte: Wegpunkte werden nur innerhalb von Polygonen erzeugt Nur modellierte Flächen sind begehbar

Wekkanten: Nur 2 direkt benachbarte Wegpunkte werden verbunden

um die Anzahl der Wegkante gering zu halten. Sofern keine Wandkante geschnitten wird




Wegpunkte: Werden nur erzeugt wenn Bewegungsrichtung

geändert wird Beim Übergang von einem Polygon ins nächste (bei

der Überquerung von begehbaren Polygonkanten) Bei Bewegungen innerhalb eines Polygons, das

nicht konvex ist (beim Umlaufen einer Polygonecke, die einen Winkel von mehr als 180 Grad einschließt)

Wegkanten: Zwischen 2 Wegpunkten wird eine Wegkanten

erzeugt wenn zwischen beiden Punkten eine Sichtlinie besteht (schneidet keine Wandkante)




Abbildung 8: Optimierte Erzeugung der Wegpunkte nur an relevante stellen




Die Umgebung(THI Graph) Kognitive Karte(THI filter) Arbeitsspeicher Landgraph Speicher controller

Abbildung 9: Navigation system architecture




Füßgängervorstellung

Menschliche Denkweise Personelle Vision Virtuelle Objekt

Abbildung 10: Füßgänger




Konstruktion von Polygonen

Ein sehr einfache Kreuzung Geometrische Figuren (Polygonen) Topologische Verbindung Semantische Bedeutung

Abbildung 11: Polygon




Umgebung (THI Graph) Diese Graph spielt die Rolle von Datenbank Globale Oberflächen Einfache Oberflächen Berechnung von Kern und Umfang

Abbildung 12: hierarchical topologische Graph




Berechnungen

von Polygonen

Komplizierte Algorithmus Unterscheidung zwischen Gebäuden und freien Oberflächen Je stärker die Farbe ist desto integrierter die Oberfläche ist

Abbildung 13: polygonen

radiation

Abbildung 7: Polygon




Kognitive Karte(THI filter) Speicherung von Daten in die kognitive Karte Filterung von die Daten Aktivierung von Daten

Abbildung 14:

spatial kognitive map




Lokalen Oberflächen:

Generator : Generierung von Lokalen OberflächenEin beschränkte Vision zu bekommen

Abbildung 15: lokale Oberfläche




Verbindung zwischen THI Graphund THI Graph Filter

Abbildung 16: Einfügen von lokaler Oberfläche




Speicher Model Semantische Speicher(IHT Graph) Associative Speicher (Landgraph) Arbeitspeicher Speicher Kontroller

Abbildung 17: Navigation System Architektur




Verschieden Situationen beim Weg finden

Bekannte und erkannte Oberflächen Bekannte und aufgerufene Oberflächen Bekannte und nicht aufgerufene Oberflächen Unbekannte Oberflächen

Abbildung 18: Parameter von Speicher Oberflächen




Datenübertragung zum Arbeitsspeicher

Abruf Test Erkennungstest Aktivierung Der Transfer zum Arbeitsspeicher

Abbildung 19: Speicherkontoller




Abbildung 20: Weg erzeugen von Anfang bis ende




Assoziative Speicher (Landgraph)

Landmark Referenz Punkt für jede einfache Oberfläche Landgraph ist eine Sammlung von referenzierte einfache oberflächen . Speicherung in Arbeitsspeicher

Abbildung 21: Die Rolle von Landgraph




Navigation(1)

Verschiedene Lokale oberflächen durch Lern Wege suchen

Abbilung 22 : Erste vier Navigation




Navigation(2)

53 einfache Oberfläche Landgraph besteht aus 26 Landmark (Referenzpunkt)

Abbildung 23: fertige Karte

Documents

Navigation Autonomer Mobiler Systeme Füßgängernavigation Veranstalter Prof. Dr. Bernd Krieg-Brückner Dr. Bernd Gersdorf Hoang Thach Vu Saber Bedoui Bremen