05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
66 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 Fully-polynomial-time approximation schemes for the Euclidean shortest path problem(2024) Schneewind, AxelThe shortest path problem is a well-studied problem in computer-science. For transport networks, there exist natural graph representations and highly efficient algorithms that can compute shortest paths on millions of nodes within milliseconds. In contrast, computing shortest paths in space (e.g. in R^2) poses some challenges. Shortest path computations in space have applications in robotics, naval routing or video games. As shortest paths in a continuum are hard to compute (with the Euclidean shortest-path problem in 3D even proven to be NP-hard), approximations can be necessary to obtain acceptable runtimes. In this thesis, an approximation scheme is studied that guarantees solutions with cost at most (1+ε) times the optimum. It uses a triangulation of the domain and, given ε, construct a discretization. By performing a Dijkstra search, one can then approximate shortest paths with the given quality guarantee. This scheme is implemented and its practicality evaluated on larger instances.Item Open Access Berechnung kürzester Wege mit negativen Kantenkosten(2024) Holtz, PatrickDas Kürzeste-Wege-Problem ist ein elementares Problem der Graphentheorie. Während sich für Graphen mit positiven Kantenkosten schon lange nahe-lineare Algorithmen wie der Dijkstra-Algorithmus etabliert haben, sind im Allgemeinen für Graphen mit beliebigen, also auch negativen Kantenkosten, nur Algorithmen mit schlechterer Komplexität bekannt. Bekannte Beispiele hierfür sind der Bellman-Ford Algorithmus oder der Goldberg-Algorithmus, die in O(nm) bzw. O(m√n log W ) laufen. Der 2022 vorgestellte Algorithmus von Bernstein et al. verspricht mit O(m log⁸(n) log W) erstmals eine nahe-lineare Komplexität, die die bestehenden Algorithmen in der Theorie verbessert. In dieser Arbeit wird Bernsteins Algorithmus vereinfacht und von Grund auf erklärt und eine praktische Implementierung vorgestellt. Außerdem wird durch Laufzeittests untersucht, wie Bernsteins Algorithmus im Vergleich mit ausgewählten bestehenden Algorithmen abschneidet. Die Tests erfolgen auf drei verschiedenen Graphklassen. Es konnte festgestellt werden, dass Bernsteins Algorithmus auf zufällig generierten Graphen mit etwa 106 Knoten um ein Vielfaches langsamer ist als eine effiziente Implementierung von Bellman-Ford (SPFA). Trotzdem konnte gezeigt werden, dass die nahe-lineare Komplexität erreicht wird. Somit ergibt sich bei der Anwendung auf praktische Probleme für Bernsteins Algorithmus kein Laufzeitvorteil, weshalb er die anderen Algorithmen erst bei weitaus größeren Eingabegraphen zeitlich überbieten kann.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 von Minecraft Welten aus OpenStreetMap-Daten(2024) Dürr, FriedrichDiese Arbeit erforscht die Konvertierung von OpenStreetMap-Daten in spielbare Minecraft Welten. Durch die Nutzung von Höhendaten und Daten aus OpenStreetMap (OSM) wird eine nahtlose Integration von realen Straßen, Gebäuden und Geländemerkmalen in Minecraft ermöglicht. Der Fokus liegt auf der Automatisierung des Prozesses, um vom Nutzer ausgewählte OSM-Datensätze effizient in Minecraft zu übertragen. Verschiedene Herausforderungen wie Datenaufbereitung, Effizienz und Detailgenauigkeit werden untersucht, um realistische Minecraft-Welten zu schaffen. Die resultierenden Welten dienen nicht nur als unterhaltsame virtuelle Umgebungen, sondern auch als nützliche Schablone, um die echte Welt in Minecraft nachzubauen und als Werkzeug für städtische Planung und Geoinformatik-Anwendung.Item 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.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 Quadratic equations in free groups and free monoids(2024) Natterer, SilasWe consider word equations over a free monoid or group where every variable occurs at most twice, also called quadratic equations. First, we recount some previously established facts about quadratic equations. We then present the classic solution algorithm for quadratic equations over free monoids based on Nielsen transformations. Next, we prove a theorem that is in some ways analogous to the Pumping Lemma for regular languages: If a quadratic equation permits infinitely many solutions, this already implies the existence of solutions with arbitrarily high exponent of periodicity; this statement is proven both for free monoids and free groups. Finally, we present an algorithm which computes the exponent of periodicity for general equations over free monoids.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.