Browsing by Author "Funke, Stefan (Prof. Dr.)"

Now showing 1 - 7 of 7

Open Access
Algorithms for vehicle navigation
(2012) Storandt, Sabine; Funke, Stefan (Prof. Dr.)
Nowadays, navigation systems are integral parts of most cars. They allow the user to drive to a preselected destination on the shortest or quickest path by giving turn-by-turn directions. To fulfil this task the navigation system must be aware of the current position of the vehicle at any time, and has to compute the optimal route to the destination on that basis. Both of these subproblems have to be solved frequently, because the navigation system must react immediately if the vehicle leaves the precomputed route or the optimal path changes e.g. due to traffic jams. Therefore solving these tasks efficiently is crucial for safe and precise navigation. In this thesis we first described a fully autonomous localization scheme based on the shape of the driven trajectory, which provides very accurately the position of the vehicle in the street network. In the second part we investigated route planning for electric vehicle, describing efficient algorithms which allow for retrieving paths with low energy consumption in a fraction of a second on large street networks.
Open Access
Contraction hierarchies: theory and applications
(2022) Rupp, Tobias; Funke, Stefan (Prof. Dr.)
Contraction Hierarchies describes a technique that enormously accelerates the calculation of shortest paths on road networks in practice. In the first part of this thesis, this acceleration is analyzed theoretically. For this purpose, we introduce the graph family of lightheaded grids. On one hand, light-headed grids have realistic properties as planarity and occur in real world road networks. On the other hand, their generic structure makes them suitable for theoretical analysis. We prove a lower bound Ω( n) for the average query phase of contraction hierarchies on lightheaded grids. At the cost of more disk space, hub labels is another technique which enables even quicker answering of shortest path queries than contraction hierarchies. For hub labels, we prove that the average hub label size of a node is in Ω( n) on lightheaded grids with the same idea as in the previous proof. Then we develop this proof idea even further into a schema which is able to compute instance-based lower bounds for both contraction hierarchies and hub labels on any arbitrary given graph. For some graph families such as balanced ternary trees, we show that this schema yields tight bounds, i.e. the lower bounds matches a concrete contraction hierarchy and hub labeling. In previous contributions concerning upper bounds, it was believed that it is meaningful to consider only explored nodes to upper bound the query time. For example, it was proven for one proposed contraction strategy based on separators, that during query time of contraction hierarchies, only sublinear many nodes are explored on average for a wide family of graphs which includes lightheaded grids. For lightheaded grids, we prove that this strategy yields linear many edges to be explored on average, therefore showing that considering only the number of explored nodes is not sufficient. We also show that it is not the contraction hierarchy framework which is necessarily flawed but the proposed strategy by giving another strategy for which only sublinear many edges need to be explored on average. In the second part of this thesis, contraction hierarchies are adapted to fit other purposes than answering short paths queries only. First, we show how trajectories, i.e. movement of individuals on the road network, can be stored efficiently if the contraction hierarchy data structure is present. When describing the compression process of raw trajectory data, we also prove that the compressed presentation is unique. Having the data compressed will also be beneficial for answering retrieval queries which ask for all trajectories intersecting a given space-time cube. We describe how to augment the contraction hierarchy data structure further to answer such queries quicker than state-of-the-art approaches. Interestingly, contraction hierarchies can also be instrumentalized to visualize graph simplifications 9as it was already demonstrated in the URAN framework. However, the URAN framework had some shortcomings which we address. We ensure that a simplified graph retains its original silhouette better and avoids some topological inconsistencies. Moreover, we apply similar techniques to visualize trajectory data sets within our framework PATHFINDERVIS which is also able to provide different flavors of visualization including heat-map based ones.
Open Access
Labeling interactive maps
(2020) Krumpe, Filip; Funke, Stefan (Prof. Dr.)
Navigationssysteme, beziehungsweise digitale Kartenapps, haben sich zu alltäglichen Begleitern entwickelt. Waren digitale Karten vor einem Jahrzehnt ein wertvolles Gut - Updates für Navigationssysteme wurden für viel Geld verkauft- sind sie heute durch die Verbreitung von Google Maps und Co. eine Selbstverständlichkeit. Neben der Verfügbarkeit und der Möglichkeit einfacher Updates, ermöglichen digitale Karten eine einfache, intuitive Interaktion. Das Zoomen, Verschieben und Drehen des Kartenausschnitts zum Erkunden von Details und der Ausrichtung in Blickrichtung des Nutzers, sind wohlbekannte Funktionen. Letzteres ist vor allem bei Navigationssystemen zentral. Dort wird die Kartenausrichtung generell in Fortbewegungsrichtung gewählt. Insbesondere für die Darstellung von Kartenbeschriftung, stellen diese Möglichkeiten eine Herausforderung dar. In der vorliegende Arbeit wird ein Konzept zur Gestaltung von Beschriftungen in interaktiven Karten, die stufenloses Zoomen, Verschieben und Rotieren des Kartenausschnitts ermöglichen, vorgestellt. Dabei wird insbesondere die Beschriftung von sogenannten ”Points of Interest” - also zu beschriftenden Punkten - thematisiert. Derartige Beschriftungen sind gewöhnlich horizontal ausgerichtet und überlappen sich somit tendenziell bei der Kartenrotation. Vor allem beim Zoomen der Karte sind verschiedene Konsistenzkriterien zu beachten - so soll beispielsweise eine Beschriftung während eines kontinuierlichen Zoomens nicht mehrfach hinzugefügt und wieder entfernt werden. Außerdem sollen Beschriftungen von wichtigeren Punkten länger sichtbar sein, als solche von weniger wichtigen Punkten. Bei der Beschriftung von Gebieten gilt, dass sich die Beschriftung im Gebiet befinden und die grobe Form des Gebiets adaptieren soll. Um letzteres zu erreichen, darf die Beschriftung entlang eines Kreisbogens gebogen sein. Rotation ist in diesem Szenario einfach - die Beschriftung muss lediglich in ihrer Ausrightung umgekehrt werden, sodass sie nicht auf dem Kopf steht. Beim Zoomen des Kartenausschnitts sollten Gebiete als Ganzes oder ihre Untergebiete beschriftet werden, abhängig von der Kartenskala der Gebietsbeschriftung. Für der Beschriftung von Punkten werden sogenannte ”Disk-Label” eingeführt. Bei diesen wird für jede Beschriftung ein kreisförmiger Bereich um den zu beschriftenden Punkt reserviert. Die Beschriftung des Punkts bleibt in beliebigen Ausrichtungen der Karte vollständig in diesem Bereich enthalten. Indem als Beschriftung in einer beliebigen Kartenskala eine überschneidungsfreie Untermenge der ”Disk-Label” gewählt wird, ist die lesbare Darstellung bei Rotation gewährleistet. Beim Herauszoomen aus dem Kartenausschnitt, werden die Beschriftungen bei konstanter Größe beibehalten. Entsprechend wachsen die zugehörigen Disks relativ zur Karte - entsprechend schrumpfen die Distanzen zwischen den Disks. Bei fortschreitendem Zoomen, kommt es zu Berührungen der Disks. Dabei muss eine der beteiligten Beschriftungen muss entfernt, um bei weiterem Zoomen die überschneidungsfreiheit zu erhalten. Wird der entsprechende Zoomprozess von ”unendlich 107weit hineingezoomt” zu ”unendlich weit herausgezoomt” betrachtet, ergibt sich eine sogenannte Eliminationssequenz der Beschriftungen. Diese kann für einen Datensatz im Voraus berechnet werden und ermöglicht dann eine einfache, effiziente Ableitung einer Kartenbeschriftung für ein gegebenes Darstellungszenario. Das Problem der Berechnung der Eliminationssequenzen kann verallgemeinert in einem d-dimensionalen Hyperraum betrachtet werden. Entsprechend der Disks in 2D, wachsen d-dimensionalen Hyperbälle. Eine Eiminationssequenz ist dabei nicht eindeutig - kollidieren Bälle der selben Wichtigkeit, ist die Entscheidung welcher der beiden Bälle eliminiert wird, essentiell für den weiteren Verlauf der Sequenz. Das Ziel ist die Berechnung einer optimalen Sequenz, in der die Summe aller Eliminationszeitpunkte maximiert wird. Es wird gezeit, dass die Berechnung einer solchen optimalen Sequenz N P − hart ist. Für ein vereinfachtes Szenario - in welchem die Sequenz eindeutig ist - wird ein effizientes Berechnungsverfahren vorgestellt und analysiert. Dieses Verfahren hängt stark von einer effizienten Methode zur Berechnung des nächsten Nachbarn sowie der Suche nach Punkten mit einer maximalen Distanz zu einem gegebenen Punkt ab. Je nach Szenario können diese Operationen effizienter oder weniger effizient gelöst werden. Für 2D und für höhere Dimmensionen werden zwei verschiedene theoretische Laufzeitschranken bewiesen. Für die praktische Beschriftung von digitalen Karten, werden Punkte auf einem virtuellen Globus betrachtet. Eine Berechnung der Sequenz für 13 Millionen Punkte ist auf einem herkömmlichen Computer in etwa 15 Minuten möglich. Das ursprüngliche, unvereinfachte Problem kann mittels eines Mixed-Integer Linearen Programms für wenige Punkte exakt gelöst werden. Allerdings nur mit erheblichem Rechen- und Speicheraufwand. Eine gute Approximation der optimalen Sequenz bieten Heuristiken. Mittels dieser kann der vorgestellte Algorithmus für das vereinfachte Szenario Lösungen für das unvereinfachte Problem berechnen. In der Güte liegen die Heuristiken bei 5% − 10% unter dem Optimum. Bei Berechnungszeiten von 15 − 20 Minuten auf einem herkömmlichen Computer. Eine Gebietsbeschriftung liegt vollständig innerhalb des Gebiets und ahmt die Form des Gebiets nach, indem sie entlang eines Kreisbogens plaziert ist. Für eine gute Beschriftung ist eine entsprechende Platzierung gesucht, welche die Größe der Beschriftung maximiert. Abhängig davon kann eine maximale und minimale Kartenskala berechnet werden, bei welcher die Beschriftung lesbar dargestellt werden kann. Entsprechend kann das Gebiet bei größeren Skalen in einer weiteren Verfeinerung dargestellt, oder bei kleineren Skalen durch eine Punkt-Beschriftung oder die Darstellung eines umfassenden Gebiets ersetzt werden. Für die Berechnung einer solchen guten Beschriftung wird in der vorliegenden Arbeit ein effizienter Algorithmus vorgestellt. Dieser basiert auf einem Algorithmus von 2001, von M. Barrault in [Mat01] publiziert. Durch verschiedene Optimierungen kann diese Berechnung auf Quasi-Echtzeit verbessert werden.
Open Access
On hierarchical search and preference-based routing in transportation networks
(2023) Proissl, Claudius; Funke, Stefan (Prof. Dr.)
In dieser Arbeit werden verschiedene Problemstellungen der Routenplanung in Transportnetzwerken behandelt.
Open Access
OSCAR: a textual and spatial exploratory search engine for OpenStreetMap data
(2020) Bahrdt, Daniel; Funke, Stefan (Prof. Dr.)
Open Access
Personalized route planning : on finding your way in theory and practice
(2022) Ihle, Florian Benjamin; Funke, Stefan (Prof. Dr.)
Personalisierung ist ein wichtiger Trend in der heutigen digitalen Welt. Im Bereich der Routenplanung hatte dieser jedoch noch keine starken Auswirkungen. Diese Dissertation beschäftigt sich mit dem multikriteriellen Routenplanungsansatz, der “personalized route planning model” genannt wird. Das Modell optimiert Konvexkombinationen von Routenplanungskriterien wie z.B. Reisezeit, Distanz oder Straßentyp und berechnet unterschiedliche Routen basierend auf den Präferenzen des Nutzers. Wir nennen die optimalen Pfade dieses Modells personalisierte Pfade. Das Angeben solcher Präferenzen ist keine einfache Aufgabe für einen Nutzer. Daher haben wir uns im praktischen Teil unserer Forschung auf Anwendungen konzentriert, die die Präferenzen im Backend verarbeiten ohne den Nutzer mit ihnen zu konfrontieren. Wir stellen drei praxisorientierte Anwendung und eine theoretische Analyse des Models vor. Für jede der Anwendungen entwickelten wir effiziente Algorithmen und verifizierten die Qualität und Laufzeit experimentell. Die erste Anwendung findet große Mengen von Alterantivrouten, die nicht zu sehr überlappen. Dazu entwickeln wir einen Algorithmus, der alle personalisierten Pfade aufzählen kann. Dieser wird dann erweitert um optional das Berechnen von Pfaden zu vermeiden, die zusätzliche Optimalitätskriterien nicht erfüllen. Darüber hinaus zeigen wir ‘erfundene’ Routenplanungskriterien, die die Ergebnisse noch weiter diversifizieren. In unseren Experimenten beobachteten wir große Mengen an sinnvollen Alternativrouten. Im Gegensatz zur ersten Anwendung sind die nächsten beiden Anwendung nicht an Endnutzer gerichtet, sondern dienen zum Lernen aus bestehenden Trajektorien. Die zweite Anwendung identifiziert Zwischenziele in Trajektorien. Wir nehmen an, dass Fahrer auf längeren Fahrten mit mehreren Zielen personalisierte Pfade zwischen den einzelnen Zielen wählen. Daher verwenden wir einen Trajektoriensegmentierungsansatz, der die Trajektorien in personalisierte Pfade aufteilt. Unser Ansatz konnte ca. 60% aller bekannten Zwischenziele in einem echt Welt Datensatz exakt erkennen und 90% waren sehr nahe an den errechneten Zwischenzielen. Unsere letzte Anwendung hat das Ziel Trajektorien nach Präferenzen zu clustern. Hier ist die Idee eine Menge an Trajektorien durch eine kleine Menge Präferenzen zu erklären, so dass jede Trajektorie für eine der Präferenzen optimal ist. Das erlaubt es wichtige Präferenzen für einzelne Fahrer zu finden oder eine Menge von Fahrern zu kategorisieren. Wir berechnen den Präferenzbereich für alle Trajektorien und lösen eine darauf basierende geometrische “Hitting Set” Instanz. Obwohl beide Schritte im schlimmsten Fall teuer zu berechnen sind, stellten wir fest, dass der gesamte Prozess häufig in Sekunden bis Minuten berechnet werden kann für Instanzen mit tausenden Trajektorien. Im letzten Teil der Dissertation analysieren wir wie viele personalisierte Pfade es abhängig von der Graphgröße zwischen zwei Knoten geben kann. Unsere Analyse basiert auf zwei speziellen Graphfamilien und wird dann auf alle Graphen generalisiert. Wir beweisen, dass die Anzahl der personalsierten Pfade subexponentiell in der Graphgröße und exponentiell in der Zahl der Routenplanungskriterien ist.
Open Access
Shortest path speed up techniques : lower bounds and applications
(2013) Eisner, Jochen; Funke, Stefan (Prof. Dr.)
The widespread proliferation of portable hand held computing devices in the form of mobile phones, rivaling 6 year old desktop computers in raw computational power and outclassing them in terms of communication interfaces and interoperability, gave rise to a plethora of new geospatial applications and services. One of the many roles a modern mobile phone can provide, is the complete substitution of printed maps with added functionality as navigation aid, for self localization, or - with more semantic back-end information - complex routing queries all around the world. With the computer-based compilation of the majority of the worlds' road networks, which are freely available to everyone in the form of OpenStreetMap, vast geospatial databases are to our disposal today. One of the most fundamental questions in such a network is to compute a shortest (or quickest) path between two designated points. This problem was solved by Dijkstra in 1959 in a provably optimal way, but his algorithm, although very elegant and simple in design, does not scale well on continent sized road graphs. Therefore a multitude of alternative approaches for the single-source-single-target shortest path problem and more complicated flavors were devised in the last decade. The motivation for highly efficient algorithms in this field is twofold. On the one hand they enable a real time user experience on a mobile phone, even for complex tasks, on the other hand these approaches scale well when a server back-end is employed, whose task is to server a large number of mobile agents. If used in combination these techniques enable us to compute different shortest path related problems in the order of ten milliseconds on the complete road network of Europe. This constitutes a speedup of more than three magnitudes compared to Dijkstra's approach. This work consists of three main parts, each addressing an exemplary problem in the field of geospatial application which are outlined in the following sections. - Transit Node Constructions Revisited In the first part we reconsider the concept of transit nodes as introduced by Bast et al. Transit nodes are an offline speed up technique which enables very fast point to point shortest path distance computations and are based on a precomputed point to point distance table of a small subsets of nodes - the transit nodes. For the first time we construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual and, as a side product, we achieve considerably smaller access node sets which directly improve the query time for non-local queries. We devise an algorithm to construct transit node sets for this theoretic framework and verify their properties with a practical implementation. This result was also published as ''Transit Nodes - Lower Bounds and Refined Construction'' at the 14th Meeting on Algorithm Engineering and Experiments (ALENEX) in 2012. - Applications of speedup Techniques: Path Prediction In the second chapter of this work we work on the path prediction problem - given the path a mobile user has moved along in a road network up to the current moment, predict where the user will move along in the near future. In contrast to known solutions to this problem we will compute our prediction not only based on the geometry of the known path (using extrapolation) or directional information implied by the underlying road network but make explicit use of the structure of the space of shortest paths in the network. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost. This work was published as path of the paper ''Algorithms for Matching and Predicting Trajectories'' in the 13th Meeting on Algorithm Engineering and Experiments (ALENEX) at 2011. - Applications of speedup Techniques: Sequenced Route Queries The third and final chapter considers the problem of a sequenced route query - the problem of planning an optimal route (quickest or shortest) that visits facilities of the respective type (for example a gas station or a super market) on the way home. The proposed solution, based on the combination of a distance sensitive doubling technique and contraction hierarchies, is orders of magnitudes faster than either a naive approach or previous results. In addition it produces the answers in an instant for realistic queries without compromising guaranteed optimality. With such fast query times, this type of route query becomes feasible even on mobile devices or for high-throughput web-based route planners. This work is published as ''Sequenced Route Queries: Getting Things Done on the Way Back Home'' in the Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL) in 2012.