05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
42 results
Search Results
Item Open Access Performance measurements for personalizable route planning for uncorrelated edge costs(2021) Bühler, FelixNowadays, ordinary route planners compute paths by choosing the shortest or fastest route. However, there exist additional metrics from which users with varying preferences could benefit. Personalized route planning offers the possibility to combine different metrics with personal preferences. Nevertheless, personalized route planning has mainly been tested with correlated metrics. But when including uncorrelated metrics, the computing time increases significantly. Previous work found that the speedup technique “Customizable Route Planning” can lead to feasible speedups for single metric calculations. Thus, in this work, we investigate how this speedup technique for Dijkstra improves the query performances of “Personalizable Route Planning” compared to “Personalizable Contraction Hierarchies”. Furthermore, we study the performances on uncorrelated metrics. We introduce a graph structure to compare the personalized speedup techniques “Personalizable Contraction Hierarchies”, “Personalizable Customizable Route Planning” and “Personalizable Route Planning”. Three graph partitioning algorithms have been implemented to realize “Customizable Route Planning”: K-means, Gonzales, and Merge. Our experiments show that Merge works well in combination with “Personalizable Contraction Hierarchies” preprocessing. We found that “Personalizable Customizable Route Planning” is a good alternative, as it uses much fewer edges for finding the costs of the shortest path. For uncorrelated metrics, “Personalizable Customizable Route Planning” and “Personalizable Route Planning” achieved speedups higher than “Personalizable Contraction Hierarchies”. Our contribution comprises a novel graph structure for comparing different Dijkstra variants. With our experiments, we provide a deeper understanding of the personalized route planning problem. Additionally, we propose improvements for “Personalizable Contraction Hierarchies” for less contracted graphs with uncorrelated metrics.Item Open Access OSM ticket to ride(2022) Friedsam, WenzelBoard games such as Ticket to Ride by Days of Wonder use game boards which are based on real geographic data. In this particular example the game map is an abstract railway graph consisting of a set of train stations, that are connected by train routes. Generating such maps by hand is a long and time consuming process. Therefore we present an algorithm that can generate playable maps for the game Ticket to Ride for different countries and continents. The result of this work is an application which is able to automatically create a game graph using OpenStreetMap data as input. We try to keep the generated graph as similar as possible to the original game in terms of important metrics that affect the gameplay, while trying to keep the result close to the geographic data during the abstraction process. The result is exported into a format that can be imported by an open source web version of Ticket to Ride, which allows players to play on the generated map.Item Open Access Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken(2022) Berner, LukasFür die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99,9 % aller kürzesten Pfade im Graph abgedeckt sind.Item Open Access Asynchronous programs on IoT devices(2022) Pflugfelder, ChristianThe ESP32 is a system-on-chip series developed by Espressif Systems. The chips are low-cost, have low power consumption, many connectivity options, and integrated Wi-Fi. Therefore, they are often used for IoT applications. The development framework distributed by Espressif Systems is largely based on C, so many applications are developed using C and C++. However, other programming languages can also be used on the ESP32. The ESP32 is often used in environments where it must respond to network or environmental events. Asynchronous programming is well suited for such an event-driven context. This thesis investigates how asynchronous programming can be implemented on the ESP32 with different programming languages (C, C++, Rust, Lua, and Python) and the possible limitations. For this purpose, an asynchronous web server is developed with each language. The performance characteristics such as memory consumption, response time, and the maximum number of parallel connections are compared. It is also examined how easy it is to implement asynchronous programs using the concepts supported by the different languages. The performance comparison shows that using operating system threads consumes significantly more memory than asynchronous programming with a runtime. Thus, runtimes are the better option in a context where many network connections are used in parallel. It also shows that the async/await pattern allows easy programming and much more compact code than callbacks.Item Open Access Experimental study of the AKS sorting network(2020) Fischer, AlexanderSorting networks are usually bound at a depth of O(log^2 n), since a perfect halver is of at least depth O(log n). However, the AKS Sorting Network, by Ajtai, Komlos and Szemeredi, can sort data with depth O(log n) by using so-called ε-halvers, which are of constant depth. Such ε-halvers are allowed to have some errors and will eventually be corrected by sending elements to a level above. In this thesis, a CPU and CUDA version are implemented following a paper by Vasek Chvatal and the original paper by Ajtai et al. Experiments are run on these versions to observe and improve parameters.Item Open Access Consistent pruning and simplification of administrative subdivisions in OpenStreetMap(2022) Bauer, FlorianAppealing and efficient map representations rely on simplifying their map elements in order to reduce the amount of data and rendered objects. However, simplifications inside the well-known OpenStreetMap database are not trivial due to nesting and the associated complex dependencies among elements. A good and consistent simplification of elements in a big way is, therefore, not feasible when working on this data. This thesis aims to develop a consistent simplification strategy for administrative boundaries inside the OpenStreetMap database. In order to achieve this goal, the relevant map data inside the database gets filtered and transformed into an independent graph representation. Based on this representation, we develop different approaches to simplify, store and unpack the administrative boundaries based on their administrative levels and structure. Therefore, we introduce multiple consistent simplification approaches based on approximation and pruning, a geographical data structure for efficiently storing and accessing geographical data, and different approaches for unpacking simplified data. Furthermore, we implement a progressive web application that uses the previously defined algorithms and an evaluation proxy for analysing the interaction between components. Finally, all components are benchmarked with static and dynamic analysis regarding the different approaches.Item Open Access Simulation and analysis of complex dynamics in a low-dimensional model of a vibration-machine(2021) Roggenbuck, KayIn the past decades, the importance of discontinuous piecewise-smooth models has been well-established. So far, the dynamics of such models are mostly analyzed based on functions with a single point of discontinuity. This class of functions is well-investigated in the literature and many theoretical results are known. Even though many physical phenomena can be described by this class, for more complex systems, a single point of discontinuity is not sufficient. In this thesis, this theory is extended by the analysis of a map in which the number of discontinuities varies based on different parameters. It is shown that this map does for integer-valued parameters result in clear dynamics, e.g. a sausage-shaped period-adding cascade. Even though these structures are already known in the literature, the understanding of its dynamics is key for the analysis of the structures for a more generalized range of parameter values. For example, for real-valued parameters the map show a much more complex structure consisting of a combination of period-adding and period-incrementing with different coexistence scenarios. Furthermore, it is shown that the iteratively increasing of a parameter related to the number of discontinuities destroys the sausage-shaped structure and transforms it for the next higher integer value to a more complex sausage-shaped structure. It is investigated how this structure is destroyed and how it evolves in the intermediate steps. Additionally, in this new structure an example configuration of the model is found where well-established results from a map with one discontinuity can not be applied.Item Open Access Integration of CH/HL-based route planning in OSCAR(2020) Makolli, SokolEfficient and fast shortest path routing on road networks is required to meet the demands of millions of users every day. In this work we document an implementation, which combines two popular speed up techniques. The results show that with little space overhead a speed up of one order of magnitude to conventional techniques is achievable, while also giving the choice of using either disk or RAM storage. The routing application is also integrated into the search engine OSCAR, which then allows for interactive exploration of locations along the route.Item Open Access Personalisierbarer Android-Offline-Routenplaner(2022) Ratnamaheson, NivenRoutenplaner sind heutzutage selbstverständlich geworden. Das Gebiet der klassischen Routenplanung bietet jedoch keine Antwort auf individuelle Anforderungen eines Nutzers. Diese Anforderungen eröffnen ein anderes Gebiet der Routenplanung: Das sogenannte personalized route planning. Das Hauptproblem des personalized route planning liegt bei der dynamischen Gewichtung der Kanten in dem zu untersuchenden Graphen. Diese Gewichtung verhindert die Nutzung etablierter Algorithmen der klassischen Routenplanung, die einen Vorbereitungsschritt benötigen. In dieser Bachelorarbeit wird die Konzeption und Entwicklung eines personalisierbaren Android-Offline-Routenplaners vorgestellt und dokumentiert. Dabei wird ein nachvollziehbarer Ansatz unter Berücksichtigung des Prinzips des personalized route planning und einer Offlinefunktion konzipiert und verfolgt. Die Entwicklung umfasst die Implementierung eines Servers mit Java 17 und einer Android-Applikation mit Kotlin. Die für die Implementierung benötigten Geoinformationen werden einerseits aus den SRTM-Datensätzen und andererseits über den OsmGraphCreator des FMI der Universität Stuttgart aus OpenStreetMap Datensätzen extrahiert. Das Ergebnis der Arbeit ist eine Android-Applikation, die das Smartphone zu einem unabhängigen Routenplaner macht. Der Nutzer der Applikation kann einen Kartenausschnitt des deutschen Straßennetzwerks herunterladen und eine durch drei Metriken (Zeit, Distanz und positive Höhendifferenz) personalisierbare Route berechnen lassen. In einer abschließenden Evaluation wird auf Hindernisse, die im Laufe der Arbeit auftraten, eingegangen, und die gesamte Implementierung auf Performance und Skalierbarkeit überprüft.Item Open Access Learning metrics for balancing load in street-networks(2020) Parga Cacheiro, DominicEspecially in daily rush-hour-scenarios, a street-network requires enough capacity to support the amount of drivers. On the other hand, a street-network of too much capacity would be inefficient outside of rush-hour-scenarios. Hence, the overload during rush-hour should be spreaded over the network to reduce the impact of the overload (\eg\ traffic-jams). To improve the distribution of routes, alternative routes in multicriteria settings are computed. To support multicriteria settings, Dijkstra's algorithm is combined with personalized routing. Here, these multicriteria or multiple metrics, \eg\ travel-time or travel-distance, can be reduced to scalars by applying preferences to them. Resulting routes or paths are called personalized paths. However, many previous approaches for computing alternative routes need too much parameter-tuning or simply lack in their computational complexity, their needed runtime or in the diversity of their found routes. Therefore, this thesis presents a combination of enumerating personalized paths with the creation of a new penalizing metric. The goal is to compensate other popular metrics with this new metric, which then improves the spread of many routes in the network. This new metric can be processed by every routing-algorithm, that is capable of dealing with multicriteria-routes. By enumerating personalized paths with this new penalization, found routes can be distributed successfully over the network. In addition, user-provided tolerances for preferred metrics are hold. In the end, some experiments on street-networks from OpenStreetMap are presented. Here, results are compared between routes from Dijkstra (with personalized routing) and the enumeration of personalized routes. To speed the route-queries up significantly, the underlying graphs of the networks are contracted via contraction-hierarchies before the searches happen. Here, the contraction is realized by a linear program to improve the performance with multicriteria contractions.