Ubiquitous Navigation

Ortsbezogene Dienste (Location-based Services, LBS) sind in den
letzten Jahren durch die weite Verfügbarkeit von GPS zu einem
Massenphänomen gewachsen. Insbesondere für die Steuerung von
mobilen Endgeräten wird mehr und mehr Kontextinformation
hinzugenommen, da sowohl die Bedienbarkeit als auch die
Informationsdichte auf den kleinen Smartphones im Kontrast zur
Informationsfülle des Internets stehen. Daher werden vielfach
Dienste nicht mehr allein auf der Nutzereingabe basierend erbracht
(reaktiv), sondern bieten dem Nutzer relevante Informationen
vollautomatisch und kontextabhängig (proaktiv) an. Durch die
proaktive Diensterbringung und ortsbezogene Personalisierung wird
die Benutzbarkeit der Dienste verbessert. Leider kann man derzeit
solche Dienste nur außerhalb von Gebäuden anbieten, da zum Einen
kein einheitliches und günstiges Positionierungssystem verfügbar
ist, und zum Anderen die notwendigen Kartendaten nicht vorliegen.
Vor allem bei den Kartendaten fehlt es an einfachen Standards und
Tools, die es dem Eigentümer eines Gebäudes ermöglichen, qualitativ
hochwertige Kartendaten zur Verfügung zu stellen. In der
vorliegenden Dissertation werden einige notwendige Schritte zur
Ermöglichung ubiquitärer und skalierbarer Indoornavigation
vorgestellt. Hierbei werden die Themenfelder Positionierung,
Modellierung und Kartographie, sowie Navigation und Wegfindung in
einen umfassenden Zusammenhang gestellt, um so eine tragfähige,
einfache und skalierbare Navigation zu ermöglichen. Zunächst werden
einige Verbesserungen an Terminal-basierten
WLAN-Indoorpositionierungssystemen vorgeschlagen und diskutiert,
die teils auf der Verwendung neuer Sensorik aktueller Smartphones
basieren, und teils auf der Verwendung besonders kompakter
Umgebungsmodelle auf mobilen Endgeräten. Insbesondere werden
Verfahren vorgeschlagen und evaluiert, mit denen sich aus typischen
CAD-Daten mit geringem Bearbeitungsaufwand die notwendigen
Zusatzinformationen für eine flächendeckende Indoornavigation
modellieren lassen. Darüber hinaus werden Methoden untersucht, die
diese semantischen Erweiterungen teil- bzw. vollautomatisch aus
Zeichnungen extrahieren können. Ausgehend von dem Ziel,
flächendeckende Navigation basierend auf CAD-Daten zu ermöglichen,
stößt man auf das Problem, eine Menge an interessanten Punkten so
zu ordnen, dass der Reiseweg kurz ist.Dieses Problem ist mit dem
NP-vollständigen Travelling-Salesman-Problem verwandt. Allerdings
ist die geometrische Situation in Gebäuden derart komplex, dass
sich die meisten derzeit bekannten heuristischen Lösungsalgorithmen
für das Travelling-Salesman-Problem nicht ohne Weiteres auf die
Situation im Inneren von Gebäuden übertragen lassen. Für dieses
Problem wird ein heuristischer Algorithmus angegeben, der in
linearer Laufzeit kleinere Instanzen des Problems mit akzeptablen
Fehlern lösen kann. Diese Verfahren wurden im Rahmen eines Projekts
mit dem Flughafen München erarbeitet und umgesetzt. In diesem
Projekt sollten die ungelösten Probleme einer bereits existierenden
kleinflächigen Demonstrator-Implementierung eines
Fluggastinformationssystems gelöst werden. Auf diesen Algorithmen
und Verfahren basiert die Navigationskomponente des
Fluggastinformationssystems InfoGate, das die flächendeckende
Navigation in den Terminals des Flughafen München mit verteilten
Anzeigesystemen ermöglicht und seit dem 6. Juni 2011 im
Produktivbetrieb ist. So konnten die Verfahren dieser Arbeit in
einer real existierenden, komplexen Umgebung evaluiert werden.