Entwurf und Entwicklung eines Werkzeugs zur automatischen Generierung von Routingnetzen aus Gebäudemodellen

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Zielsetzung
1.3 Aufbau der Arbeit

2 Anwendungsfall und Anforderungsanalyse
2.1 Überbliek über das Forsehungsvorhaben
2.2 Problematik des Brandalarmablaufes
2.3 Lösungsansatz

3 Grundlagen
3.1 Navigation und Routing
3.1.1 Definition
3.1.2 Gesehiehte
3.1.3 Heutiger Kenntnisstand
3.2 Einführung in Indoor-Xavigation
3.2.1 Positionierung
3.2.2 Routing
3.2.3 Guidanee
3.3 Graphentheorie
3.3.1 Einleitung
3.3.2 Definitionen
3.3.3 Beispiel
3.3.4 Speieherung von Graphen im Computer
3.4 Routingalgorithmen
3.4.1 Kürzeste Wege in Graphen
3.4.2 Algorithmus von Dijkstra
3.4.3 A*-Algorithmus
3.4.4 Bidirektionale Verfahren
3.4.5 Routenbereehnung im Straßenverkehr
3,5 Zusammenfassung

4 Untersuchung von Gebäudedaten für Routinganwendungen
4.1 Datenaustauschformate für Gebäude
4.1.1 Anforderungen
4.1.2 Datenaustausch im Bauplanungsprozess
4.1.3 Proprietäre Dateiformate
4.1.4 Offene CAD-Dateiformate
4.1.5 XML-Formate'
4.2 Vergleich der offenen Austausehformate

5 Indoor- Routing
5.1 Eigenschaften von Wegen
5.2 Definition der Wegekosten
5.3 Berechnung von Weglängen in Polygonen
5.4 Der Vorgang eines Routings
5.5 Graphenmodell
5.6 Modellierung mehrerer Stockwerke
5.7 Wahl des Routingalgorithmus

6 Verfahren der Routingnetzgenerierung
6.1 Manuelle Methoden
6.1.1 Wegpunktenetz
6.1.2 Polygonbasierte Umgebungen
6.2 Automatisierte Methoden
6.2.1 Raummittelpunkte und Türen
6.2.2 Gleichmäßige Rasterung
6.2.3 Quadtrees
6.2.4 Delaunay- Triangulierung und Voronoi- Diagramm
6.2.5 Skelettierung
6.3 Gegenüberstellung der Verfahren
6.3.1 Fazit

7 Entwicklung eines Werkzeugs zur Routingnetzherstellung
7,1 Fachliches Modell
7.1.1 Anwendungsfall
7.1.2 Funktionalitäten
7.1.3 Klassen
7.2 Datenschicht
7.2.1 Das Importformat: gbXML
7.2.2 Das Exportformat: AGF
7.3 Wahl der Programmierspache
7.4 Verwendete Bibliotheken
7.4.1 .net Framework
7.4.2 CGAL
7.5 Beschreibung der Methoden (Ansschnitt)
7.5.1 Erzeugung eines rasterbasierten Wegenetzes
7.5.2 Erzeugung eines Straight Skeletons

8 Anwendungsbeispiel
8.1 Automatische Generierung eines Wegenetzes
8.2 Durchführung von Routings auf einer Endanwendung
8.3 Ergebnisse

9 Fazit
9.1 Zusammenfassung
9.2 Ausblick

10 Literaturverzeichnis

A Anhang
A.l Codebeispiel - Polygonoperationen
A.2 Codebeispiel - Straight Skeleton
A.3 Klassendiagramm CFloor
A.4 Auszug aus dem AGF- Datenbankmodell

Abstract

In emergency situations, particularly within large buildings like office towers or airports, safety and co-ordination of the operations is the key to success. Knowing the exact lo­cation of building elements like fire alarms can support the response of rescue troops significantly. Utilizing indoor navigation systems could be a great help for such use eases.

While vehicle navigation systems already have high market penetration, perdestrian na­vigation based on handheld devices like Personal Digital Assistants (PDA), are getting more and more popular. For indoor applications, there are still some burdens to overcome: outdoor locating is based on GPS, indoor positioning techniques (i.e. RFID, WLAX) are just being researched. Secondly, the underlying outdoor map data is commonly based on street networks, but for buildings no standard is settled yet.

In this work, a prototype application is developed that supports an automated process of converting architectural CAD floorplans into a spatial data representation that is useful for a indoor navigation applications. In the first step, building elements (rooms, walls, doors, stairs, etc.) must be assembled in order to provide a suitable model for accessible areas within the building. Therefore, contemporary CAD- formats are being analyzed.

Then, a network of accessible paths has to be computed on the data model. The graph structure has a significant advantages in supporting navigation, since a path through a network is readily expressed as a series of decisions at links and nodes. Classical methods to find an optimal path are already developed, such as the wide range of shortest path algorithms like Dijkstra’s algorithm.

The developed prototype application imports gbXML building files and offers various me­thods to compute graph structures on the building environment. An export option of the graph and rendering objects is given for the AGF- format, used by navigation products of the company PTV AG. A client-application demonstrates and visualizes that shortest path algorithms are readily usable on the model. Department of Civil Engineering on the TU campus is used as a test-bed which is representative for many office bindings.

Kurzfassung

Große Verkehrsinfrastrukturen und Gebäudekomplexe unterliegen nicht nur einer potenti­eller Gefährdung z.B, durch Brandfälle, sondern auch kontinuierlichem Wartungsaufwand der Brandschutzeinrichtungen. Vor Allem im Alarmfall sind umfangreiche Maßnahmen erforderlich: Feuermelder und Löschsysteme müssen schnellstmöglich kontrolliert werden, d.h. die Einsatzkräfte müssen den Zielort in kürzester Zeit erreichen. Doch oft erschweren veraltete Gebäudepläne in Papierform einen optimalen Einsatz. Auf der anderen Seite sind heutige Gebäudekarten als CAD- Bestandspläne verfügbar. Diese können zum Ein­satz eines Indoor- Navigai ionssystems herangezogen werden.

Zur Navigation außerhalb von Gebäuden existieren bereits zahlreiche Anwendungen. Die Positionierung mit GPS ist ausgereift, und die Kartengrundlage ist durch das Straßennetz eindeutig definiert. Die Ortung und Navigation innerhalb von Gebäuden wird jedoch erst erforscht. Aufbauend auf den Kenntnissen bisheriger Xavigationssysteme wird in dieser Arbeit ein Datenmodell für Indoor- Anwendungen entwickelt.

Als Grundlage für ein solches Gebäudenavigationssystem wird in dieser Arbeit ein proto- typisches Werkzeug zur automatischen Generierung von Routingnetzen auf CAD- Daten vorgestellt. Hierzu werden offene Austausehformate auf ihre Eignung zur Repräsentation gebäudeinterner Verkehrswege hin untersucht. Außerdem werden mathematische Grund­lagen zur Wegenetzberechnung zusammengestellt. In diesem Werkzeug kann ein mehr­stöckiger Gebäudeplan eingeladen werden. Durch verschiedene geometrische Verfahren können Wegenetze aus dem Gebäudemodell automatisch generiert werden. Eine Export­funktion ermöglicht deren Nutzung auf einer PDA- Endanwendung. Diese ermöglicht die direkte Kurzwegeberechnung und Anzeige der Route auf dem erzeugten Netz modeli.

Tabellenverzeichnis

3.1 Vergleich Outdoor- Indoor- Navigation

4.1 Proprietäre CAD-Formate führender Softwareunternehmen

7.1 AGF- Tabellen für den Routing- Layer

7.2 AGF- Tabellen für Teleporter

7.3 AGF- Tabellen für den Rendering- Layer

7.4 AGF- Basistabellen

Abbildungsverzeichnis

2.1 Einsatzablauf bei Brandalarm

3.1 Laverkonzept |PTV 2008|
3.2 UML-Aktivitätsdiagramm Routenplanung
3.3 Basiskomponenten eines LBS
3.4 UML-Kommunikationsdiagramm eines Indoor-Routings
3.5 Reichweite und Genauigkeit verschiedener Positionierungssysteme |Glanzer 2007|
3.6 Darstellungsmöglichkeiten einer Route auf mobilen Endgeräten
3.7 Ein Beispielgraph
3.8 Ein vollständiger Graph
3.9 Ein Weg p auf G
3.10 Die 7 Brücken von Königsberg
3.11 Ein gewichteter, gerichteter Graph
3.12 Adjazenzmatrix
3.13 Adjazenzliste
3.14 Dijkstra-Algorithmus in Pseudocode
3.15 Beispielgraph zum Dijkstra-Algorithmus
3.16 Visualisierung verschiedener Routingalgorithmen

4.1 gemeinsames Produktmodell im Bauplanungsprozess
4.2 offenes CAD-Austausehformat

5.1 kürzester Weg eines Fußgängers von s nach t im Gebäude
5.2 konvexes und nicht konvexes Polygon
5.3 kürzester euklidischer Weg durch den Funnel- Algorithmus
5.4 UML-Aktivitätsdiagramm Routing
5.5 Teilgraphen der Geschosse

6.1 manuelle Xetzerstellung mit PTV VISUM
6.2 manuelle Xetzerstellung mit dem Tool Yamamoto
6.3 Graph aus Raummittelpunkten und Türen
6.4 Siehtbarkeitsgraph
6.5 Anbindeprobleme bei wenigen Knoten
6.6 Graph dureh gleiehmäßige Rasterung
6.7 Graph dureh Quadtree-Zerlegung
6.8 Graph als Voronoi- Diagramm einer Delaunay-Triangulation
6.9 Skelettierung eines Polygons |Haunert 2005|
6.10 Straight Skeletons der Raumpolygone
6.11 Vergleich der Weglängen
6.12 Vergleich der Anzeige

7.1 UML- Klassendiagramm: Graph
7.2 gbXML Building- Element
7.3 gbXML Surface- Element

8.1 Grundriss des IIB
8.2 Ergebnis der Verfahren 4 und 5
8.3 Einfügen eines Teleporters
8.4 Splashsereen PTV TourGuide
8.5 Routing auf dem IIB - Modell
8.6 Routing über 2 Stockwerke auf dem IIB - Modell

1 Einleitung

1.1 Motivation

Komplexe Gebäude und Verkehrsinfrastrukturen mit hoher Populationsdiehte wie z.B, Bürogebäude oder Flughäfen unterliegen stets potentieller Gefährdung (Terroransehlag, Brand, Erdbeben,,,,) wobei im Ernstfall immer Mensehenleben auf dem Spiel stehen, Doeh gerade in der heutigen Informationsgesellsehaft gibt es viele Beispiele, in denen sieh der Einsatz moderner Teehnologien und Verfahren als lebensrettend erwies, und einen Vorfall, der früher als Katastrophe eingestuft worden wäre gar nicht zustande kommen ließ.

Am Beispiel der Werksfeuerwehr am Frankfurter Flughafen, welcher mehrere tausend Alarme durch Feuermelder zu verzeichnen hat, ist festzustellen, das die Orientierung und Zielfindung der Einsatzkräfte im Gebäudebereieh im Einsatzfall, aber auch bei Alltags­aufgaben wie Wartung und Unterhaltung, häufig schwierig ist. Diese Kräfte verwenden derzeit herkömmliche Papierpläne (Laufkarten) zur Navigation zu den zu untersuchenden Brandsehutzeinriehtungen, Da der Flughafen fortwährend Umbaumaßnahmen unterliegt, sind diese Pläne zudem meist nicht auf dem aktuellen Stand, Auf der anderen Seite, wer­den schon seit geraumer Zeit Gebäudedaten im Rahmen der Bestandsplanung in CAD- und Facility Management- Software vorgehalten. Vor diesem Hintergrund stellt der Ein­satz mobiler Endgeräte zur Ortung und Navigation innerhalb komplexer Gebäudestruk­turen ein großes Potential zur Verbesserung der Orientierung und Einsatzabwieklung für Einsatzkräfte da.

1.2 Zielsetzung

Außerhalb von Gebäuden existieren bereits zahlreiche Anwendungen zur Navigation und Routenbereehnung, Auch mobile Endgeräte erweisen sieh großer Beliebtheit und sind zu Alltagsbegleitern geworden. In Deutschland sind ein Großteil der Straßen und Wege zur Verwendung in Routenplanern erfasst worden. Die Indoor-Navigation steht dagegen erst am Anfang, Ziel dieser Arbeit ist es, Methoden zur automatisierten Generierung von Wegenetzen innerhalb von Gebäuden aus bestehenden CAD-Gebäudeinformationen zu untersuchen und für den Anwendungsfall der Indoornavigation für Einsatzkräfte der Feu­erwehr nutzbar zu machen.Zentraler Aspekt ist es, die herkömmlichen Laufkarten durch ein digitales Informationssystem zu ersetzen, das die Probleme der veralteten Pläne und aufwendiger Zielsuche auf diesen zu lösen vermag.

Hierbei sollen Wegenetze nicht wie bei der Navigation im Outdoorbereieh mittels Abfahren direkt erfasst werden, sondern indirekt mögliche Wege aus den Raumgeometrien aus CAD- Plänen erzeugt werden. Der Prozess der Konvertierung zwischen digitalen Bestandsplänen zu Navigai ionsmodellen soll innerhalb einer Software möglichst automatisiert werden. Ziel ist ein Export auf eine mobile Lösung, die aufbauend auf diesen Wegenetzen Routenbe- reehnungen durchführen kann, und den Nutzern die Führung zum gewünschten Ziel in anschaulicher Weise ermöglicht.

1.3 Aufbau der Arbeit

In Kapitel 2 wird eine Einführung in das aktuelle Forsehungsprojekt "Kontextsensitives RFID-Gebäude-Leitsystem" der Technischen Universität Darmstadt gegeben. Dabei wird auf die Problematiken des Brandalarmablaufs der Flughafenfeuerwehr eingegangen.

Kapitel 3 stellt die Grundlagen zu den zentralen Themenbereiehen Navigation und Routing zusammen. Dabei wird ein Augenmerk auf den aktuellen Kenntnisstand von Outdoor- Lösungen gelegt. In einer Einführung in die Graphentheorie und Routingalgorithmen werden die mathematische Grundlagen aktueller Navigaiionssysteme beschrieben. Abgeschlossen wird mit einer Betrachtung der Unterschiede hinsiehtdieh der Anforderungen zwischen Outdoor- und Indoor- Navigation.

In Kapitel 4 werden vorhandene CAD- Schnittstellen im Hinblick auf den Anwendungsbereich zur Erhaltung der grundlegenden gebäudeinternen Wegenetze untersucht und verglichen. Hierbei wird sieh auf die marktführenden Programme beschränkt.

Kapitel 5 stellt die Anforderungen gebäudeinterner Routenbereehnungen zusammen. Dabei wird aufbauend auf geometrischen Überlegungen die Berechnung von Weglängen in Gebäudestrukturen analysiert. Zudem wird der zugrundelegende Graph mit seinen Elementen und Eigenschaften definiert.

Kapitel 6 vergleicht Verfahren zur manuellen und automatisierten Generierung von Wegegraphen auf Gebäudegrundrissen in der Ebene.

In Kapitel 7 wird aus den betrachteten Konzepten ein Werkzeug zur automatischen Generierung von Routingnetzen entworfen und implementiert. Hier werden die benötigten Klassen, Methoden, Bibliotheken sowie die Import- und Exportformate besehrieben,

Kapitel 8 zeigt ein Anwendungsbeispiel: aus einem digitalen Gebäudemodell wird ein Xavigationsmodell generiert, und auf einer mobilen Endanwendung getestet,

Absehließend werden in Kapitel 9 die Ergebnisse der Arbeit zusammengefasst, Mögliehe Erweiterungen werden im Ausblick aufgezeigt.

2 Anwendungsfall und Anforderungsanalyse

2.1 Überblick über das Forschungsvorhaben

Das Ausmaß terroristischer Bedrohung besonders für große Gebäude und Verkehrsinfra­strukturen und die Notwendigkeit der schnellen Hilfeleistung haben Anschläge, wie z.B, auf das World Trade Center in New York 2001 oder auf die Züge in Madrid 2004, vor Augen geführt. Nicht nur im Fall eines Terroranschlags, auch im normalen Betrieb, un­terliegen große Infrastrukturen (wie Hochhäuser, Flughäfen, Einkaufszentren, usw,,,) mit hohem Publikumsverkehr ständiger Gefährdung, wobei im Ernstfall immer Menschenle­ben auf dem Spiel stehen. Sei es ein Brandfall, Rauchausbreitung, oder ein Erdbeben - in Alarmsituationen müssen in sehr kurzer Zeit Maßnahmen eingeleitet und Einsatzkräfte koordiniert werden. Die Koordinierung durch die zuständigen Organisationen und Ein­satzleiter erweist sich als kritische Aufgabe, Die Orientierung und der Überblick über die Positionen von Opfern und Einsatzkräften innerhalb komplexer Gebäude (indoor) ist für die Einsatzleiter nahezu unmöglich.

Doch gerade in in der heutigen Kommunikationsgesellschaft der Industrieländern sind technische Kapazitäten und Potentiale vorhanden, solche Unzulänglichkeiten schon im Vorfeld zu vermeiden und im Rahmen der präventiven Gefahrenabwehr Schäden auf ein Minimum zu reduzieren. Es gibt viele Beispiele, in denen sich der Einsatz moderner Tech­nologien und Verfahren als lebensrettend erwies, und einen Vorfall, der früher als Kata­strophe eingestuft worden wäre gar nicht zustande kommen ließ. Dies legt nahe, ständig die aktuellen Entwicklungen zu verfolgen und die vorhandenen Schutzkapazitäten den sich verändernden Anforderungen, aber auch den technischen Möglichkeiten anzupassen. Gerade in diesem Sinne stellt der Einsatz computergestützter Informationssysteme eine große Hilfe bei der Bewältigung der gefahrenrelevanten Aufgaben in den komplexen Struk­turen moderner Gesellschaften dar.

Im Forschungsprojekt "Kontextsensitives RFID-Gebäude-Leitsystem" der Technischen Universität Darmstadt im Rahmen der Forschungsinitiative Zukunft Bau¹ werden Me­thoden zur Indoor-Ortung und -Navigation für Einsatzkräfte zur schnellen Wegfindung im Einsatzfall in Gebäuden am Beispiel des Frankfurter Flughafens entwickelt.

2.2 Problematik des Brandalarmablaufes

Die Flughafenfeuerwehr der Fraport AG ist integraler Bestandteil der Flughafensicher­heit, als Werkfeuerwehr anerkannt und blickt auf eine 50jährige Geschichte zurück. Seit jeher ist sie verantwortlich für die Organisation, den vorbeugenden und abwehrenden Brandschutz, die technische Hilfeleistung, und für die Abwehr von Gefahren für Mensch und Umwelt, Ständige Aus- und Weiterbildung ist Hauptaufgabe des Feuerwehr Training Center (FTC), einem international anerkannten Kompetenzzentrum für Brandsicherheit auf Flughäfen, Hier werden die Feuerwehrexperten an und mit modernster, mobiler Tech­nik geschult. Das FTC wird inzwischen europaweit zur Weiterbildung genutzt und steht darüber hinaus Kunden auch weltweit rund um das gesamte Thema Brandschutz bera­tend zur Seite |Fraport 2007|,

Trotz aller Technisierung und ständig verbesserter Brandschutzmanagementkonzepte gibt es Indizien, die Mängel in der Infrastruktur, Informationshaltung und Organisation er­sichtlich machen. Beispielsweise treten etwa 5000 Alarme pro Jahr auf dem Frankfurter Flughafen auf. In kürzester Zeit, innerhalb von spätestens zehn Minuten muss die Feuer­wehr nach internationaler Vorschrift der ICAO (International Civil Aviation Organization) an jeder Stelle des Gebäudes mit wirksamen Lösch- und Rettungsangriffen beginnen. Das Beispiel eines Brandalarmablaufes (Abb, 2,1, wie er derzeit von der Flughafenfeuerwehr ausgeübt wird, zeigt potentielle Störfaktoren,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2,1: Einsatzablauf bei Brandalarm

Hierbei fällt besonders die zeitaufwändige Suche nach Gebäudeelementen anhand her­kömmlicher, zum Teil nicht aktueller Laufkarten in Form von Papierplänen auf. Auch ausgelöste Brandmelder müssen umständlich auf diesen Papierplänen lokalisiert werden. Die räumliche Orientierung innerhalb der Flughafengebäudebereichs von 2,5 mio, qm2 ist ohnehin herausfordernd. Immerhin befinden sich auf dem gesamten Flughafengelände über 50,000 Brandmelder, welche an Brandmeldezentralen (BMZ) angeschlossen sind |Fraport 2007|, Es ist offensichtlich, dass eine Suche anhand von Laufkarten viel Zeit erfordert, die im Ernstfall Menschenleben kosten kann. Treten mehrere Alarme gleichzeitig auf, so gestaltet sich der Einsatz um ein vielfaches problematischer. Ein weiterer Aspekt betrifft die uneinheitliche Darstellung dieser Laufkarten, Obwohl Feuerwehrlaufkarten nach DIX 14095 standardisiert sind, fällt auf, dass häufig Pläne sehliehtweg nicht maßstäblich und nicht genordet sind und dass wichtige Symbole und Eintragungen fehlerhaft oder nicht vorhanden sind. Für ein effizientes Brandmanagement bei Einsatz und Wartungsaufgaben müssen diese Schwachstellen unbedingt behoben werden,

2.3 Lösungsansatz

Da die meisten für ein effektives Brandmanagement erforderlichen Daten einen Raumbe­zug erfordern, und in der Vergangenheit große Schritte auf die Digitalisierung vieler raum­bezogener Daten vonstatten gingen, hegt es Xahe ein solches Informationssystem für den beschriebenen Einsatzfall zu konzipieren. Viele der für die Gefahrenabwehr der Flugha­fenfeuerwehr relevanten Daten, wie Gebäudepläne, Brandmelderpositionen, Schutzgüter, usw... sind in den für die Alltagsaufgaben verschiedener Fachinstitutionen vorhandenen Datenbeständen enthalten. Von besonderem Interesse ist daher die Möglichkeit, diese in vernetzter Form zu integrieren und zu nutzen. In Zeiten von exakten Ortungsverfahren, preisgünstigen Xavigationssystemen und handlichen mobilen Endgeräten für den Massen­markt ist es an der Zeit, solche Technologien für das Xotfallmanagement in Gebäuden verfügbar zu machen. Dabei werden die angesprochenen Laufkarten durch digitale ange­reicherte Datenbestände ersetzt, und in ein komfortables Indoor- Xavigationssystem inte­griert, Angefragte Routen von der aktuellen Position einer Einsatzkraft zum gewünschten Ziel werden in Sekundenschnelle übersichtlich auf einer digitalen Karte angezeigt und ak­tualisiert.

Der Erfolg des Systems soll später in einer Testumgebung am Frankfurter Flughafen eva­luiert werden. Die in diesem Forschungsprojekt gewonnenen Ergebnisse und Erkenntnisse lassen sich aufgrund der inhomogenen Struktur des Flughafens auch direkt auf andere komplexe Bauwerke (Bürogebäude, Produktionshallen, Versammlungsstätten etc.) über­tragen, Es ist zu erwarten, dass dieses System die beschriebenen Problematiken löst, und ein unverzichtbares Equipment für zeitgemäß ausgestattete Organisationen im Rahmen des Katastrophenmanagements sein wird.

3 Grundlagen

3.1 Navigation und Routing

Das folgende Kapitel gibt eine Einführung in das Thema Navigation. Dabei wird ein Überblick über die geschichtliche Entwicklung der Methoden und Techniken gegeben. Der aktuellen Kenntnisstand der Outdoor-Navigation wird aufgezeigt, woraus sieh die Themenberieche ergeben, die für die Navigation innerhalb von Gebäuden relevant sind.

3.1.1 Definition

Unter Navigation (von lat. navigare: "Führen eines Schiffes") versteht man "die mit einer Standortbestimmung und Streckenauswahl verbundene Bewegung im Raum, insbesondere die Führung von Fahrzeugen auf dem Land, zu Wasser oder in der Luft." |Bollmann und Koch 20021, Sie ist eine der ältesten Wissenschaften der Menschheit und besteht im Grundsatz aus drei Teilbereichen:

1. Bestimmung der geographischen Position eines Individuums in unbekannter Umge­bung durch verschiedene Methoden (positioning, locating).
2. Berechnung des optimalen Weges vom aktuellen Standpunkt zu einem gewünschten Ziel oder Zielgebiet (routing).
3. Führung des Individuums zum Ziel und Halten des optimalen Kurses (guidance).

Zu allen drei Bereichen wurden im Laufe der Geschichte unzählige Methoden, Geräte und Technologien entwickelt.

3.1.2 Geschichte

Der Ursprung liegt, wie der lateinische Name sagt, in der Nautik, also in der Steuerung von Schiffen auf dem Meer. Die Beantwortung der grundlegenden Fragen "wo bin ich" und "wie komme ich nach..." war ausschlaggebend für erfolgreiche Expeditionen oder Handel­reisen, sichere Heimkehr, aber auch für das bloße Überleben. Hatten Seefahrer anfangs (ea. 3500 v.Chr.) noch keinerlei Hilfsmittel zur Hand, so mussten sie sieh an Landmarken, also an geographisch markanten Punkten orientieren. Diese Sichtnavigation, war jedoch nur in Küstennähe und bei Helligkeit brauchbar, Entfernungen berechneten sie ans der Abschätzung der Geschwindigkeit des Schiffes, multipliziert mit dem Zeitabgleich an ei­ner Sanduhr, So wurden Karten hergestellt, die durch diese grobe Entfernungsabschät­zung aber sehr ungenau, unmaßstäblieh und deshalb wenig hilfreich waren. Für weitere Fahrten auf hoher See bediente man sieh der astronomischen Navigation, also der Positi­onsbestimmung anhand von Himmelsgestirnen (Sonne, Mond, Planeten und Fixsternen), Das Interesse an der Astronomie war schon in den ersten Kulturen bekannt, und so wurde dieses Wissen auf die Abschätzung der eigenen Position in Relation zu den Sternen über­tragen, Erste Berechnungsmethoden für Längen, Winkel und Geschwindigkeiten halfen bei der Positionierung, Thaies von Milet (625 - 547 v, Chr.) entwickelte ein erstes Lehr­buch für Seefahrtsprobleme, Mit der Erfindung von Messgeräten wie dem Kompass, dem Astrolabium und dem Sextanten, die in verschiedenen Kulturkreisen weltweit vollzogen wurden, hatte man im Mittelalter geeignete Werkzeuge gefunden, um sieh auch auf dem Land zu orientieren und Vermessungskunde zu betreiben. Die Genauigkeit der Karten ver­besserte sieh in diesem Zuge ebenso, und man konnte erste Kartenwerke erstellen, welche die geographischen und topologischen Gegebenheiten in geeignetem Maßstab abbildeten. In der Neuzeit wurde dies vor Allem durch zweckmäßige winkeltreue Projektionsarten wie die Mercator-Projektion in Verbindung mit Koordinatensystemen (Gauss-Kriiger, UTM) erreicht.

3.1.3 Heutiger Kenntnisstand

Wie beschrieben, besteht Navigation aus Methoden der Positionsbestimmung mit Refe­renz auf eine kartographische Basis, In der heutigen Informationsgesellschaft werden die Kartendaten weitestgehend digital in Form geographischer Informationssysteme (GIS) aufbereitet. Diese dienen als mächtiges Werkzeug für die Planung und Analyse des mensch­lichen Lebensraums in vielen Teilgebieten der angewandten Wissenschaften, Für die Her­stellung und Bereitstellung dieser Daten sind entweder öffentliche Behörden wie Kataster- und Vermessungsämter, oder komerzielle Kartenhersteller wie z.B, die führenden Firmen NAVTEQ und TeleAtlas zuständig. Die Grundlagen sind z.B, herkömmliche Papierkar­ten, Feldvermessungen, Photos und Satellitenbilder, Die verkehrsrelevanten Kartendaten für aktuelle Navigationssysteme werden dann aus diesen Daten extrahiert. Aus diesen Informationen wird eine Datenbank produziert, die dann an diverse Kunden vertrieben wird.

Als gemeinsames Vektor- Austausehformat hat sieh für Navigation und Routenplanung das Geographie Data File-Format (GDF) etabliert. Seit 1995 ist das GDF in Europa Stan- dard und liegt als Entwurf für einen weltweiten Standard vor (GDF 4,0, ISO/TC-204), TeleAltas und XAVTEQ bieten ihre Daten in diesem Format an. Zentraler Bestandteil ist dabei das Objekt (Feature), das mittels der geometrisehen Primitive Punkt (Knoten) und Linie (Kante) alle Gegenstände der realen Welt abbildet. Dazu gehören u.a, Stra­ßen, Sehienenstreeken, Briieken, Tunnel, Wasserwege, Siedlungen, administrative Grenzen |GDF 19951, Die Kunden dieser Geodäten sind u.a, Hersteller von Xavigationsgeräten, Mobilfunkun­ternehmen, Logistikfimen oder Softwarehäuser für Routenplaner, Der Trend geht zu um­fassenden digitalen Karten, die die Straßennetze der ganzen Welt abbilden, und täglich aktualisiert werden, da die bebaute Umwelt ständigem Wandel unterliegt. Um mit der steigenden Informationsmenge umgehen zu können, wird die Ordnung und das Manage­ment dieser Daten, die meist weiter veredelt werden, immer wichtiger. Hierzu bedient man sieh z.B, der Layerteehnologie, die die Informationen nach Sinn- und Sachzusammenhang trennt (Abb, 3,1), In Xavigationskarten gibt es hierzu einerseits die Schicht der Points of Interest, also die geographische Lage der Orte, die ein Mensch als Ausgangs- oder Ziel­punkt wählt. Dazwischen liegt die Routing- Ebene, die Abbildung der Wegeverbindungen zwischen diesen Punkten, Im allgemeinen Fall ist damit das Straßennetz gemeint, die Au­tobahnen, Landes- und Kreisstraßen, aber auch Fußgängerzonen, Die dritte Schicht bildet der Rendering-Layer, also die Definition, wie die graphische Anzeige ausgeprägt wird.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Lavcrkonzcpt |PTV 20081

Eine bahnbrechende Entwicklung bezüglich der Positionierung, also die Frage nach dem "wo bin ich?" ist die Funk- und Satellitennavigation, aus der das weltweite Global Positio- ning System (GPS), das russische Glonass und das zukünftige europäische Galileo-System entstanden sind.

Eine dritte Entwicklung im Rahmen der modernen Computertechnologie, die in den letzten Jahren rasant den Markt erobert hat sind die mobilen Endgeräte, Die Geräte lassen sieh nach |Steiniger und Neun 20051 einteilen in Single Purpose Devices (Xavigati- onsgeräte, Mautboxen,,,,) und Multi Purpose Devices wie beispielsweise Personal Digital Assistants (PDA), Pocket PCs oder Mobiltelefone (Smartphones) mit hochauflösenden grafischen Displays, Im Prinzip sind dies Verkleinerungen herkömmlicher PCs mit Pro­zessor, Speicher, Ein- und Ausgabeschnittstellen im Westentaschenformat, Sie sind schon jetzt als multifunktionale Assistenten beliebt und ermöglichen weitaus mehr als die klas­sische Telekommunikation zweier Personen, Die Einschränkungen hinsichtlich Rechenge­schwindigkeit und Speicherkapazität wird durch die immer leistungsfähigere Hardware allmählich überwunden. Weitere Herausforderungen ergeben sieh hinsichtlich der Hand­habung, Akkulaufzeit, Datenübertragungsschnittstellen und Robustheit,

Zwei Anwendungsbeispiele, die Navigation mit neuester Informationstechnologie verei­nen sind die Auto-Xavigationssysteme und Location based services.

Ein Auto-Navigationssystem besteht aus einem GPS-Empfänger und einem fest installierten oder mobilen Endgerät mit Monitor, Die Hardware startet die GPS- und Xa- vigationsanwendung. Vom lokalen Speicher (SD-Card, DVD) werden nur die Kartendaten die gerade benötigt werden, in den Arbeitsspeicher geladen. Über die Benutzereingabe wählt der Autofahrer den gewünschten Zielort, das Anzeigeformat und die Stimme aus, die ihn zum Ziel führen sollen, Xaeh diesen Eingaben lokalisiert das GPS-Modul die ak­tuelle Position, indem es die Entfernung zu vier GPS-Satelliten mittels Triangulation und Zeitabgleich berechnet. Sind die Lageinformationen verfügbar, werden die Koordi­naten mit dem Kartennetz abgeglichen und an den nächsten Knoten angebunden, Xun kann mittels eines geeigneten Routingalgorithmus die optimale Route von der aktuellen Position als Startpunkt zum Zielort errechnet werden. Dabei kann der Fahrer zwischen dem schnellsten, dem kürzesten, oder etwa dem landschaftlich interessantesten Weg zum Ziel wählen. Die Leitfunktion während der Fahrt funktioniert über permanenten Abgleich der aktuellen Position mit den errechneten Routendaten, Die Anweisung für den Fahrer kann auf dreierlei Arten stattfinden: textlich, grafisch oder oder durch Spraehanweisun- gen. In aktuellen Systemen hat der Fahrer alle Kombinationen zur Auswahl, wobei im Sinne der eigenen Verkehrssicherheit die Nutzung detailliertester Weganweisungen mit 3D-Visualisierung der Route auch eine Ablenkung vom eigentlichen Geschehen bewirken können. Ein weiterer Komfort wird neuerdings durch den Empfang von Verkehrsinfor­mationen in Echtzeit erreicht. Dabei wandelt ein RDS-TMC- Empfänger (Radio Data System / Traffic Message Channel) eingehende Radioinformationen in Staumeldungen um und visualisiert sie auf dem Bildschirm. Somit kann man dynamische Verkehrsinfor­mationen nutzen, um Alternativrouten angesichts der aktuellen Verkehrslage zu berechnen und Staus und Blockaden zu umfahren. |TomTom 20081

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: UML-Aktivitätsdiagramm Routenplanung

Unter Location based services (Standortbasierte Dienste, LBS) werden Informati­onsdienste verstanden, die von einem mobilen Endgerät über ein Funknetzwerk abgerufen werden, und die Position des mobilen Gerätes zur Informationsgewinnung verwenden. Sie ähneln einem Auto-Xavigationssystem, sind aber auf den Fußgänger zugesehnitten und bieten ihm die Informationen zu seiner aktuellen Lage und Absicht. Location based Services bestehen aus folgenden Komponenten | Steiniger und Neun 20051:

- mobiles Endgerät zur Informationsanforderung (PDA, Handy)
- Positionierungsinfrastruktur zur Lokalisierung (GPS)
- Kommunikationsnetzwerk (Mobilfunknetz, WLAX,,,,)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,3: Basiskomponenten eines LBS

- Dienst - und Anwendungs-Provider, der die lokalen Informationen anbietet

Ein Beispiel: eine Person befindet sieh in einer fremden Stadt, und möchte Informa­tionen zu vorhandenen Sehenswürdigkeiten erhalten. Sie fordert diese Information auf ihrem PDA an. Es wird eine Route vorgeschlagen, wie man vom momentanen Standort die benachbarten Denkmäler erreicht. Diese kann als Fußweg aufgezeichnet werden, oder es erfolgt ein Vorschlag, welche öffentlichen Verkehrsmittel zu welchen Kosten genutzt werden können. Zusätzlich werden aktuelle Angebote, Eintrittspreise, und Schließzeiten angezeigt. Per Funk werden die Daten in Form von Sprache, Text, Bildern oder Videos auf das Gerät übertragen. Viele weitere Fragestellungen sind denkbar, wie: "Wo ist die nächste Pizzeria?", "ist ein Bekannter in der Nähe?", "Welche Veranstaltung findet gerade im Theater statt?". Man sieht, dass dies je nach Wunsch des Nutzers eine Informationsflut verursachen kann, die nicht nur die Kapazität des Endgerätes übersteigt, sondern auch den Nutzer regelrecht verwirren kann. Eine geeignete knappe Darstellung und Informati­onsfilterung ist hierbei unumgänglich.

Ältere PDAs müssen zur Positionierung an ein externes GPS-Empfängermodul ange­schlossen werden, wohingegen moderne Modelle bereits integrierte GPS-Empfänger besit­zen, Dies ermöglicht wiederum ganz neue Perspektiven hinsichtlich Komfort und Mobilität für den Endnutzer,

Die Wissenschaft der Navigation, vom anfänglichen Führen eines Schiffes bis zu heutigen Location based services hat sieh im Laufe der Geschichte stets weiterentwickelt, und ist eine Zukunftstechnologie mit unabsehbarem Entwicklungspotential.

3.2 Einführung in Indoor-Navigation

Durch die Einführung von GPS entstand eine Vielzahl an Location Based Services, Diese Entwicklung setzt sich zunehmend fort und erobert neue Märkte im Outdoor-Bereieh, Xach diesem Vorbild entstehen auch neue Technologien wie die Indoor-Xavigation, die als Fußgängernavigation innerhalb von Gebäuden verstanden wird. Um dies zu ermögli­chen müssen, wie im Outdoor-Bereieh auch, die drei o.g, Anforderungen Positionierung, Routing und Guidance nach (3,1,1) erfüllt sein. Mit dieser Definition ergeben sieh jedoch aus den neuen Randbedingungen der Kommunikations- und Ortungsinfrastrukturen sowie der Datengrundlagen zahlreiche neue Fragestellungen, Das Kommunikationsdiagramm in Abb, 3,4 zeigt den Weg der Daten für den Fall der Indoor- Routensuche,

Abbildung in dieser Leseprobe nicht enthalten

Zu potentiellen Einsatzbereichen der Indoor-Xavigation gehören Führungs- und Leit­systeme an Flughäfen, Bahnhöfen, Industrie-Anlagen, Messen oder Häfen, oder auch Informations- und Werbesysteme, Zum Beispiel Werbung in Einkaufszentren, für intel­ligente Besprechungsräume oder touristische Informationen über die aktuellen Sehens­würdigkeiten im Museum, Weitere Einsatzmöglichkeiten sind Anwendungsfälle der Per­sonenlokalisierung, zum Beispiel die Ortung von Patienten oder Pflegepersonal in medi­zinischen Einrichtungen, In dieser Arbeit werden Systeme zur Einsatzplanung im Facility Management und der Xotfallerkennung behandelt.

Warum sich die mobile Indoor-Xaviagtion noch nicht auf breiter Basis durchgesetzt hat mag vielerlei Gründe haben, |Anagnostopoulos u, a, 2004| belegt, das die Konzentration der Forschung auf Outdoor-Xavigationssysteme hauptsächlich auf die bessere vorhandene Positionierungsinfrastruktur (GPS) zurückzuführen ist, Forschung im Bereich der Indoor- Xavigation wird größtenteils durch die Roboternavigation motiviert, wobei zahlreiche Al­gorithmen zur Wegsuche und Erkennung entwickelt werden | Salomon 20031, Weiterhin könne man behaupten, Indoor- Xavigation für Menschen sei nicht so wichtig, da sich alles in kleinen, räumlich begrenzten Bereichen abspielt, und man keinen eminenten Zeit­verlust hinnehmen muss, wenn man den kürzesten Weg nicht findet. Diese Behauptung wird jedoch in Fällen entkräftet, wo sieh ältere, mobilitätseingeschränkte Personen in unbekannter Umgebung zurechtfinden müssen, oder wo Arbeits- oder Rettungspersonal in weiträumigen Gebäudekomplexen den optimalen Weg finden muss. Außerdem können kontextsensitive - d.h, in Verbindung zur aktuellen Situation des Nutzers stehende - In­formationen gute Entscheidungshilfen im Bereich des Facility Management bieten, z.B, bei der Wartung von RFID-markierten Brandmeldern |Ergen u, a, 2007|,

3.2.1 Positionierung

Die Positionierung innerhalb eines Gebäudes gestaltet sieh als Kernthematik, in der der­zeit viel Forschungsaufwand betrieben wird. Das Hauptproblem besteht darin, dass das am weitesten verbreitete satellitengestütze Positionierungssystem GPS innerhalb von Ge­bäuden und in stark bebauten Gebieten nicht eingesetzt werden kann |Glanzer 2007|, Dies merkt man schon beim durchfahren von Tunneln, in denen der Empfang aussetzt. Auch in dicht bebauten Gebieten werden die Signale schwach und setzen aus. Diesen Ef­fekt bezeichnet man als Abschattung, Dies liegt daran, dass die Signaldämpfung durch die Baustoffe zu hoch ist um ein ausreichend starkes GPS-Signal zu erhalten. Zwar sind messbare GPS-Signale in Gebäuden grundsätzlich vorhanden, jedoch wurden in der ver­gangenen Zeit nach aussichtsreicheren Alternativen mit höherer Genauigkeit gesucht, wel­che den Anforderungen eines Fußgängers in einem Gebäude entsprechen. Diese basieren auf drahtlosen Xaehriehtenübertragungsteehnologien und können neben der Positionie­rungsgenauigkeit nach unterschiedlichen Kriterien klassifiziert werden:

- Anwendungsgebiet
- Energieverbrauch
- Frequenz
- Reichweite
- Datenübertragungsrate

Das ideale Funksystem ist universell einsetzbar und verbraucht wenig Energie bei hoher Reichweite und Übertragungsrate |Zapotoczky 2006|, In Bezug auf die vier Basiskompo­nenten eines LBS ergibt sieh ein Vorteil dadurch, dass die Positionierungsinfraktuktur mit dem Kommunikationsnetzwerk identisch ist. Die Funktechnologien sind alle in der Lage, ausreichend hohe Datenmengen und Ortungssignale gleichzeitig zu übertragen. Der

Nachteil dieser Alternativen ist jedoch, dass die dazu notwendige Infrastruktur vor Ort installiert werden muss, was einen Zeit- und Kostenaufwand darstellt. Daher hat sieh auch noch kein Standard zur Indoorlokalisierung durchgesetzt. Der Trend geht eher zu hybriden Technologien, die aus mehreren Kerntechnologien zusammengesetzt sind. Dieser ressourcenadaptierte Ansatz |Butz u, a, 20011 ermöglicht flexible und großflächige An­wendungsmöglichkeiten. Ziel ist es, ein Maximum an Effizienz bei akzeptablen Kosten ermöglichen.

Im folgenden Überblick seien aktuelle Basistechnologien kurz vorgestellt, Indoor-GPS. Zwar werden Versuche unternommen, GPS-Signale (zukünftig auch Ga­lileo) auch innerhalb von Gebäuden verfügbar zu machen, jedoch erreicht man auch mit hochwertigen GPS-Empfängern und neuen Auswertungsmethoden der Signale nur Genau­igkeiten von 20m, was innerhalb von Gebäuden keineswegs ausreichend ist. Ein Ansatz diese Technologie trotzdem zu integrieren ist das Projekt INDOOR in |Mäs u, a, 20061,

Wireless Local Area Network (WLAN). WLAN, oder Wi-Fi ist die Standard­technologie (802,11) zur drahtlosen Vernetzung in abgeschlossenen Bereichen da es über hohe Datendurchsatzraten verfügt (aktuell 54 MBit/'s). Die Reichweite beträgt 10-150m, Durch die weite Verbreitung der WLAN- Hotspots ist die Infrastruktur häufig schon vor­handen, Darüber hinaus sind die benötigten Geräte relativ preiswert und kompatibel. Nachteilig ist jedoch der recht hohe Energiebedarf und geringe Positionierungsgenauig­keiten |Zapotoczkv 2006|, Der Anbieter Ekahau |eka00| vertreibt bereits kommerzielle WLAN- Ortungslösungen,

Ultrawideband (UWB). UWB ist eine Funktechnologie die mit hoher Frequenz (bei hohem Energieverbrauch), große Datenübertragungsraten (bis lGb/'s) erreicht. Die Reich­weite beträgt bis zu 35m, was geringer ist als WLAN, Dafür besitzen sie eine hohe Posi­tionierungsgenauigkeit, Nach Angaben des Herstellers Ubisense |ubi00|, der kommerzielle Echtzeitortungssysteme nach ISO/IEC 24730 anbietet, liegt diese bei unter 30cm.

Radio Frequency Identification (RFID). Die Radiofrequenzidentifikation ist eine Technologie zur automatischen Identifikation von Objekten, Ein RFID-System besteht aus einem Sehreib/Lesegerät (Reader) als Basisstation, welches die Informationen mit einem Transponder (Tag) austauscht. Diese Einheiten, die aus Antenne und Spule bestehen sind sehr klein und können ohne Batterie arbeiten, was für die mobilen Endgeräte von Vorteil ist. Die Reichweite dieser passiven Tags weniger als 5m, jedoch kann man durch aktive Tags bis zu 30m erreichen. Diese Ergebnisse sind jedoch stark von der Gebäudeausstattung abhängig, besonders beim Vorhandensein metallischer Elemente |Ergen u, a, 2007|, Ebenso schwanken die Genauigkeiten, liegen jedoch im brauchbaren Bereich,

Bluetooth. Der Vernetzungsstandard Bluetooth hat sieh im Feld der drahtlosen Daten­übertragung zwisehen mobilen Geräten auf Kurzdistanz weitgehend durehgesetzt. Derzeit werden Reiehweiten von 10-100m erreieht, die Datenübertragungsrate beträgt 2,lMBps, Die Positionierungsgenauigkeit liegt im Rahmen von WLAX- Verfahren.

Infrarot (IR). Die Infrared Data Association (IrDA) spezifizierte diesen verbreiteten Kommunikationsstandard, der Daten mittels infrarotem Lieht transportiert. Im Gegensatz zu den anderen Technologien muss bei dieser Technik eine direkte Sichtverbindung und ein Winkel kleiner 30° zwisehen Sender und Empfänger (Infrarotbaken) bestehen. Dies hat sehr geringe Reiehweiten von nur ea. Im zur Folge, jedoch können hohe Positionie­rungsgenauigkeiten erreieht werden. In der aktuellen Version 1.1 werden durchschnittliche Datenraten von 16MBps unterstützt. Ein weiterer Nachteil ist die Reflexion des Signals an Oberflächen. Dies macht man sieh bei der Laserdistanzmessung zu Nutze, wobei keine Senderknoten im Gebäude benötigt werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.5: Reichweite und Genauigkeit verschiedener Positionierungssysteme |Glanz- cr 2007|

3.2.2 Routing

Die prinzipielle Fragestellung "wie komme ich von A nach B" der Wegfindung von Per­sonen innerhalb eines Gebäudes ist im Grunde von gleicher Xatur wie die der Outdoor- Xavigation, So können zahlreiche Erkenntnisse und Algorithmen (siehe Kapitel 3.2) aus dem weit verbreiteten Feld der Fahrzeugnavigation übernommen und angewandt wer­den. Jedoch gibt es eine Reihe grundsätzlicher Unterschiede, die eine breite Anwendung bisher verhindert haben. Xeben den oben angesprochenen unterseheidliehen Positionie­rungssystemen spielt vor allem die Problematik der Modellierung der Routingdaten und des Wegegraphen eine große Rolle. Eine Literaturrecherche bietet einen kurzen Überblick.

Xaeh IWalter u, a. 2004| gibt es zwei Hauptgründe, weshalb bereits existierende Xa- vigationssvsteme nicht für eine Indoor- Xavigation geeignet sind. Die Basis der Argu­mentation ist, dass sieh Kurzweganalysen nur auf vorhandenen Vektordaten durchführen lassen. Einerseits ist es aber das Bewegungsmuster von Personen, das sieh im Gegensatz zu Fahrzeugen nur inadäquat durch festgelegte Vektoren beschreiben lässt. Während sieh Autos stets auf der Mittelachse einer Bahn in eine Richtung bewegen, nutzen Fußgänger typischerweise die kürzeste Distanz zwischen ihrer aktuellen Position und dem nächsten sichtbaren Ziel. Ein zweiter Grund ist die mangelnde freie Verfügbarkeit von Vektordaten für Fußgängerbereiche und Indoor- Umgebungen.

Xaeh |Anagnostopoulos u. a. 2004| muss sowohl eine geometrische, wie auch semanti­sche Modellierung der Wege vorgenommen werden. Abhängig vom Xutzerprofil bestehen verschiedene Interessen hinsichtlich der Informationszusammenstellung und Präsentation. Einer mobilitätseingeschränkte Person soll z.B. eher Aufzüge als Treppen vorgeschlagen werden. Eine Person die große Gegenstände transportiert, soll eher über breiten Passagen und Türen geleitet werden als über schmale. Diese Xutzerzentrische Sieht wird in einer so genannten Ontologie modelliert.

Das Konzept der ontologischen Modellierung von Routen wird auch von |Winter 20051 aufgegriffen. Bisher populäre Fragestellungen der Autonavigation sind die nach der schnellsten und kürzesten Route. Mitunter sind aber auch Routen bestimmter Länge (z.B. bei Wanderungen), sichere, leichte, besonders reizvolle, oder andere Arten von Routen denkbar. Auch Kombinationen sind möglich. Somit ist eine große Breite an angepassten Informationen erforderlich, die durchaus nicht nur geometrischer Xatur sind. Vielmehr orientiert sieh der Mensch an Landmarken, die sieh je nach Verkehrsraum unterscheiden; in Gebäuden können dies z.B. Türen, Flurdeeken oder Kreuzungen sein.

In |Franz u. a. 20051 wird die prinzipielle Eignung des Graphenmodells analysiert. Da­bei kommen Aspekte aus Architektur und Kognitiver Wissenschaft in Betracht. Demnach gibt es vielseitige Möglichkeiten, den Graphen als formales Modell zu benutzen. Der be­sondere Reiz liegt in seiner Flexibilität auf verschiedene Anwendungsbereiche, da Knoten und Kanten mit beliebigen Attributen versehen werden können, Sichtbarkeitsgraphen, die beschreiben, wie sieh Zonen in einem Gebäude eingrenzen lassen spielen eine große Rolle,

ILorenz u, a, 20051 gibt an, dass die topologische Struktur von Gebäuden wesentlich vielseitiger und komplexer ist, als die von Straßennetzwerken, Straßen können primär als eindimensionale Formen mit angereihten Landmarken gesehen werden, Gebäudeplä­ne hingegen sind faktisch zweidimensional, oder, wenn mehrere Stockwerke betrachtet werden, 2,5-dimensional, Eine Modellierung kann mithilfe eines stark strukturierten We­gegraphen erfolgen, der mit vielen qualitativen und quantitativen Zusatzinformationen über die Indoor- Umgebung angereiehert ist. Um Stockwerke abzubilden, müssen vertikale Konnektoren als Übergansknoten definiert werden, die zu Teilgraphen anderer Stockwerke führen.

In einer Arbeit zur "Modellierung und Analyse gebäudeinterner Verkehrswege" |Iwans- ky u, a, 20011 wird behauptet, dass bisher keine routinemäßig einsetzbaren computerge- stiitzten Modellierungssysteme zum Zweck der Indoor- Navigation verfügbar sind. Eine vollautomatische Generierung von Verkehrswege-Graphen soll angestrebt werden, da ein Großteil der Prozesse durchaus automatisiert werden kann. Dabei müssen im Gebäudemo­dell (hier: IFC) die funktionalen Teile wie Verkehrsfläehen, Treppen, Türen, etc,,, explizit spezifiziert sein. Dieser Vorgang der Modellierung gebäudeinterner Verkehrswege stellt weiterhin eine empfindliche Lücke bei der Analyse von Bauwerken hinsichtlich Facilitv- und Change- Managementaufgaben dar.

3.2.3 Guidance

Es existieren verschiedene Präsentationsmöglichkeiten für die Darstellung der Ergebnisse einer Routenberechnung. Die Absicht ist es, den Benutzer auf die bestmögliche Art und Weise zum Ziel zu navigieren. Unter Guidance versteht man die durch Informationen un­terstützende Zielführung des Benutzers, der sieh gerade auf dem Weg befindet. Aktuelle Forschungen richten sieh auf kontextbezogene Informationsdienste, d.h, es sollen nur die­jenigen Informationen und Darstellungen übermittelt werden, die für den momentanen Zustand der Person und der Umgebung wichtig sind. Selbst das beste Xavigationssystem mit genauester Positionierung und effizientesten Routingalgorithmen ist hinfällig, wenn es die Ergebnisse nicht in anschaulicher und verständlicher Weise übermittelt. Bei der Auf­nahme der Wegeinformationen werden die menschlichen Sinne beansprucht, insbesondere das Sehorgan und das Gehör, Xavigationssysteme verwenden daher meist eine kombinier­te audiovisuelle Ausgabe, Gleiche Aspekte gelten ebenso für Indoor-Umgebungen, Hierbei bilden Gebäudepläne die Grundlage,

Textausgabe

a) Bei einer einfachen Textausgabe wird praktisch eine Wegbesehreibung als Liste von Anweisungen ausgegeben, Neben der aktuellen Position im Streckenabschnitt wird eine Entfernungsangabe bzw, Zeitangabe getroffen, zu der die nächste Anweisung erfolgt (Bsp: "geradeaus, nach 20m rechts"). In |Anagnostopoulos u, a, 2004| und |Winter 2005| wird an ontologischen Konzepten gearbeitet, die näher an den Vorstellungen des Nutzers liegen, und weniger Fehlinterpretationen in der Wegweisung zulassen sollen.

Visuelle Präsentation.

Aktuelle Navigationsgeräte verwenden vielerlei graphische Darstellungsarten für Wege­information, Diese reichen von einfachen Richtungspfeilen bis hin zu komplexen 3D- Renderings der Umgebung, Visuelle Darstellungen sind sehr effektiv, da aus Bildern mit hohem Abstraktionsgrad die nötige Information sehr schnell gewonnen werden kann,

b) Einfache Pfeilgrafiken zeigen schnell und prägnant die nächste Weganweisung, Dies ist in vielen Fällen genau das richtige, denn der Benutzer muss wissen welchen Weg er als nächstes einsehlagen muss, um sein Ziel zu erreichen. Zusätzliche Textangaben wie "noch 100m" vervollständigen die notwendige Information,

e) 2D-Karten geben einen Überblick über die zurückzulegende Strecke, und zeigen die gesamte Umgebung in der Draufsicht an. Sie sind einfach erkennbar, übersichtlich, und verbrauchen wenig Ressourcen, Nachteilig ist, dass Entfernungen schlecht abgeschätzt werden können, Idealerweise dreht sieh die Karte mit dem Benutzer, so dass sie sieh im­mer in Sichtrichtung mitbewegt,

d) 3D-Karten bieten eine gute Abschätzung von Entfernungen und Proportionen, Hierbei muss unterscheiden werden zwischen einer geneigten 2D-Darstellung mit Horizont, und einer realen 3D-Darstellung mit angrenzenden 3D-Objekten, Dies ist jedoch abhängig von der Auflösung und der Größe des PDA- Displays, Komplexe Grafiken sind müssen ent­sprechend reduziert werden, um überhaupt erkennbar zu sein,

e) Gleiches gilt für neue Techniken aus dem Forschungsgebiet der Augmented Reality, Hierbei wird die Umgebung per Kamera aufgenommen, und durch zusätzliche Elemente und Informationen überlagert, sprich "erweitert". Die Einblendung geschieht kontextab­hängig, d.h, passend und abgeleitet vom gerade betrachteten Objekt, Solche VR-Systeme befinden sieh derzeit noch nicht auf dem Markt,

Akustische Präsentation.

Die Sprachausgabe eines Navigationssystems ist eine beliebte Option für den Autofahrer, da er seine Augen auf den Verkehr richten kann und der Blick nicht abgelenkt ist. Wei­terhin ist sie für Menschen mit Sehbehinderung interessant. Jedoch ist eine akustische Wegbesehreibung oftmals nicht sehr präzise. Der Satz "nach 50m rechts abbiegen" kann

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.6: Darstellimgsmöglichkeiten einer Route auf mobilen Endgeräten

bei komplexen Kreuzungssituationen sehr irreführend sein. Eine genaue Beschreibung der Kreuzung dagegen wird die Problematik auch nicht vereinfachen. Spraehausgabe funktio­niert also nur durch kurze, prägnante Aussagen bei einfachen Routenverhältnissen.

Interaktion.

Ein weiterer wichtiger Aspekt betrifft die Handhabung und die Interaktionsmöglichkeiten mit der Benutzeroberfläche des mobilen Endgeräts. Nach [de Avezedo 2006] sind Be­dienbarkeit und Verstellbarkeit die wichtigsten Qualitätskriterien einer GUI auf mobilen Geräten. Ein Benutzer muss sich ohne lange Einarbeit ungszeit zurechtfinden können. Wei­terhin sollen sämtliche Optionen, z.B. das Ein- und Ausblenden von Zusatzinformationen, schnell erreichbar und einstellbar sein. Die Handhabung bezieht sich hauptsächlich auf die Möglichkeiten und die Sensibilität des Touchscreens, da keine Tastatur, oder Maus zur Verfügung steht. Sprachsteuerung ist zwar denkbar und möglich, jedoch in vielen Anwen­dungsfällen aufgrund der häufigen Umgebungsgeräusche auszuscdi 1 iefsen.

Orientierungsfunktion. Durch eine Positionierung ist die Lage des Benutzers im Raum gegeben. Doch eine Routenanweisung fordert nicht nur die Lage sondern auch die Ausrichtung, bzw. die Blickrichtung der Person. Dies erfordert, dass das Endgerät mit einer Orient ¡erungsfunkt ionalität (Kompass) ausgestattet ist. Nur so kann die angezeigte Karte richtig gedreht und Pfeil- oder Rieht ungsanweisungen vom Nutzer richtig interpre­tiert werden.

3.3 Graphentheorie

Im folgenden Kapitel wird eine Einführung in die Graphentheorie gegeben. Diese ist ein Teilgebiet der Mathematik und beschäftigt sieh mit der Untersuchung von Graphenstruk­turen, deren Eigenschaften und Beziehungen untereinander,

3.3.1 Einleitung

Mit dem enormen Aufschwung der elektronischen Datenverarbeitung ist das Bedürfnis nach neuen Strategien zur Darstellung logischer Zusammenhänge in Form diskreter Zu­stände (0 und 1) entstanden |Steger 2007|, Graphen sind solche diskreten Strukturen, und finden heutzutage Anwendung in vielen Bereichen der Informatik, Ingenieur- und Wirtschaftwissenschaften. Man kann viele Problemstellungen auf Graphen reduzieren, um diese dann durch geeignete Algorithmen zu lösen, Beispiele hierzu sind im Bereich der wirtschaftlichen Planung und Logistik zu finden, wenn es darum geht, Materialfluss- und Prozessabäufe zu planen und zu optimieren, um Entscheidungshilfen zu geben. Dies wird auch als Operations Research bezeichnet. In der Xetzplanteehnik, als Teilgebiet des Baubetriebs, muss etwa die Frage nach dem günstigsten, aber dennoch sinnvollen Ar­beitsablauf der Baustelle unter Berücksichtigung verfügbarer Arbeitskräfte und Materi­alressourcen beantwortet werden. Ein anderes Beispiel aus der Computertechnik ist das Internet-Routing, bei dem Datenpakete auf schnellstem Weg an den Empfänger gesendet werden sollen, oder das Durchsuchen eines hohen Datenvolumens, Aber auch im Bereich der Physik, Chemie und den Sozialwissenschaften werden Graphenmodelle zur Problem­lösung herangezogen, Komplexe Sachverhalte mit einer Vielzahl an Variablen müssen al­so einfach dargestellt werden, sodass ein Algorithmus angewandt werden kann, der die Lösung zurückgibt. Dazu bildet die Graphentheorie eine geeignete Basis, Jedes System, welches aus Objekten und Beziehungen besteht, kann als Graph abgebildet werden,

3.3.2 Definitionen

Ein Graph G = (V,E) besteht aus einer nichtleeren Knotenmenge V (engl, "vertices") und einer Kantenmenge E (engl, "edges"), bei der jedem Element aus E genau ein Knotenpaar aus V zugeordnet wird |Domsehke und Drexl 2007|.

Abbildung in dieser Leseprobe nicht enthalten

Graphen sind als System von Objekten (Knoten) und Relationen (Kanten) zu verste­hen, also zunächst abstrakte Gebilde ohne besondere Eigenschaften, Über die Elemente der Graphen existieren vielerlei Begriffserklärungen, In dieser Arbeit werden jene aus

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,7: Ein Beispielgraph

|Domsehke und Drexl 2007| verwendet. Die Abbildungen stammen aus |Diestel 2006|,

Ein Graph G heißt ungerichtet, wenn die Verbindungen nicht richtungsabhängig, also keine Pfeile sind. Zwei Knoten mit Verbindung heißen hier Nachbarn, oder adjazent. Ein Knoten heißt inzident zu einer zugehörigen Kante, Spielt die Richtung eine Rolle, so heißt G gerichtet, oder Digraph (engl, "directed"). Hier spricht man dann bei den Knoten von Vorgängern und Nachfolgern.

Die Anzahl vorhandener Knoten im Graphen heißt Knotengrad n = |V|, analog Kanten­grad m = |E|, G ist vollständig, wenn jedes Knotenpaar miteinander verbunden ist. Hier gilt: [Abbildung in dieser Leseprobe nicht enthalten]. Ansonsten ist G zusammenhängend, wenn für jedes Knotenpaar ein Weg existiert. Ein zusammenhängender kreisloser Graph wird als Baum bezeichnet. Ein Graph, der aus mehreren Bäumen besteht heißt Wald,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3,8: Ein vollständiger Graph

Der Grad deg(v), bzw, die Parität eines einzelnen Knotens ist die Anzahl der von ihm abgehenden Kanten, Graphen, in denen jede Ecke vom gleichen Grad к ist, heißen k- regulär. Eine Folge von aufeinander folgenden Kanten, bei der alle Knoten voneinander verschieden sind, heißt Weg (engl, ’’path”) [Abbildung in dieser Leseprobe nicht enthalten].

[...]

---

¹ gefördert aus Mitteln des Bundesministeriums für Verkehr, Bau und Stadtentwicklung, sowie des Bun­desamts für Bauwesen und Raumordnung