Browsing by Author "Storandt, Sabine"

Now showing 1 - 3 of 3

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
Group diagrams for simplified representation of scanpaths
(2023) Schäfer, Peter; Rodrigues, Nils; Weiskopf, Daniel; Storandt, Sabine
We instrument Group Diagrams (GDs) to reduce clutter in sets of eye-tracking scanpaths. Group Diagrams consist of trajectory subsets that cover, or represent, the whole set of trajectories with respect to some distance measure and an adjustable distance threshold. The original GDs allow for an application of various distance measures. We implement the GD framework and evaluate it on scanpaths that were collected by a former user study on public transit maps. We find that the Fréchet distance is the most appropriate measure to get meaningful results, yet it is flexible enough to cover outliers. We discuss several implementation-specific challenges and improve the scalability of the algorithm. To evaluate our results, we conducted a qualitative study with a group of eye-tracking experts. Finally, we note that our enhancements are also beneficial within the original problem setting, suggesting that our approach might be applicable to various types of input data.
Open Access
Sublinear search spaces for shortest path planning in grid and road networks
(2021) Blum, Johannes; Funke, Stefan; Storandt, Sabine
Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures - which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.