Alternative Routen in komplexen Umgebungen

Feld, Sebastian (2018): Alternative Routen in komplexen Umgebungen. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Durch die immense Verbreitung kostengünstiger GPS-Empfänger, eingebaut in mobile Endgeräte, wurde in den letzten Jahren eine beeindruckend starke Nutzung von ortsbezogenen Anwendungen und Diensten erreicht. Ein beliebter Anwendungsfall ist die Navigation im Straßenverkehr zusammen mit der Präsentation von alternativen Routen, die dem Anwender eine Auswahl nach eigenen Präferenzen oder Erfahrungen ermöglicht. Die Wegefindung in komplexen Umgebungen unterscheidet sich von der in Straßennetzen hauptsächlich durch die Tatsache, dass sich ein Anwender nahezu in alle Richtungen bewegen kann. Beispiele hierfür sind Fußgänger in Flughäfen, Krankenhäusern, Messehallen oder Parks, mobile Roboter in Industrieanlagen oder Lagerhallen, sowie Nicht-Spieler-Charaktere in Computerspielen. Auch in diesen Szenarien ist das Vorhalten von alternativen Routen sinnvoll, um beispielsweise eine personalisierte Navigation zu ermöglichen, proaktiv Stau zu vermeiden oder taktische Bewegungen durchzuführen. In der vorliegenden Arbeit werden Ansätze und Verfahren vorgestellt, die das Thema der alternativen Routen in komplexen Umgebungen auf unterschiedlichen thematischen Ebenen behandelt. Darunter fallen die Berechnung alternativer Routen in Freiflächen, der Vergleich geospatialer Trajektorien, sowie die Identifizierung von Strukturen in Gebäuden. Im ersten Teil der Arbeit werden alternative Routen in komplexen Umgebungen mittels des topologischen Konzepts der Homotopie definiert, sodass zwei Routen als Alternativen zueinander angesehen werden, wenn sie Hindernisse unterschiedlich umlaufen. Hierzu wird eine effiziente Annäherung des Tests auf Homotopie vorgestellt und es werden zwei Algorithmen zum Berechnen solcher Routen implementiert. Anschließend findet eine strukturierte Darstellung bestehender Qualitätsmetriken für alternative Routen und Alternativgraphen in Straßennetzen statt, woraufhin die Übertragbarkeit dieser Ansätze auf komplexe Umgebungen diskutiert wird. Im zweiten Teil der Arbeit werden Ansätze zum direkten Vergleich von Routen vorgestellt. Einerseits wird ein Scoring von Routen basierend auf der Annahme vorgeschlagen, dass Routen, die oft auf einem kürzesten Pfad liegen, auch oft durchlaufen werden. Andererseits wird ein System vorgestellt, das die Berechnung archetypischer Routen ermöglicht, indem es aus einer Menge von Routen die extremsten Exemplare extrahiert. Korrespondierend dazu wird die archetypische Distanz definiert, mit der Routen nicht nur geometrisch, sondern in einem mehrdimensionalen Merkmalsraum verglichen werden können. Schließlich wird im dritten Teil der Arbeit die quantitative Analyse der visuellen Wahrnehmung von Raum in den Kontext alternativer Routen integriert. Basierend auf der Idee sogenannter Isovisten wird die lokale Umgebung eines Anwenders angenähert, um somit alternative Routen zu berechnen, diese zu annotieren, und schließlich Strukturen in Gebäuden zu ermitteln. Zusammengefasst können die Beiträge der vorliegenden Arbeit in ihrer Gesamtheit als ein Werkzeugkasten verstanden werden, der von weiteren ortsbezogenen Anwendungen und Diensten verwendet werden kann.

Abstract

Due to the immense dissemination of low-cost GPS receivers built into mobile devices, an impressive use of location-based services has been achieved in recent years. A popular application is navigation in road networks in conjunction with the presentation of alternative routes that allows users a choice according to their own preferences or experiences. Route finding in complex environments differs from that in road networks mainly due to the fact that a user can move almost in all directions. Examples include pedestrians in airports, hospitals, exhibition halls, or parks, mobile robots in industrial facilities or warehouses, as well as non-player characters in computer games. In these scenarios the provision of alternative routes is useful, too, for example, to enable personalized navigation, to avoid jams proactively, or to carry out tactical movements. This thesis presents approaches which deal with the topic of alternative routes in complex environments at different thematic levels. This includes the calculation of alternative routes in open space, the comparison of geospatial trajectories, and the identification of structures in buildings. First, alternative routes in complex environments are defined using the topological concept of homotopy, so that two routes can be considered alternative if they pass obstacles differently. For this purpose an efficient approximation of the homotopy test is presented together with the implementation of two algorithms for the calculation of such routes. Subsequently a structured presentation of existing quality metrics for alternative routes and alternative graphs in road networks takes place, whereupon the transferability of these approaches into complex environments is discussed. Second, approaches for the direct comparison of routes are presented. On the one hand, a scoring of routes is suggested based on the assumption that routes, which often lie on a shortest paths, are also often traversed. On the other hand, a system is presented that allows the calculation of archetypal routes by extracting the most extreme instances from a set of routes. Corresponding to this, the archetypal distance is defined, with which routes can be compared not only geometrically but in a multi-dimensional feature space. Third, the quantitative analysis of the visual perception of space is incorporated into the context of alternative routes. Based on the idea of so-called Isovists, a user's local environment is approximated in order to calculate alternative routes, to annotate them, and to determine structures in buildings. In summary, the contributions of this thesis can be understood in their entirety as a toolbox which can be used by other location-based services.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Deutsch
• Datum der mündlichen Prüfung: 8. Mai 2018
• 1. Bericht­erstatter:in: Linnhoff-Popien, Claudia