Algorithm Engineering for Hard Problems in Computational Geometry
Many practically relevant problems in Computational Geometry are provably hard to solve. In this thesis, we consider a series of these problems and tackle them with techniques from algorithm engineering, e.g., mixed integer programming or deep reinforcement learning. Additionally, we provide a number of results on complexity and algorithms for these problems. We start with a set of problems occurring in the context of large satellite systems, where communication requires a rotation of directional antennas. Here, we discover a close relationship to the vertex coloring problem, use constraint programming to obtain optimal solutions, and provide a practical auction-based algorithm that achieves good results in a realistic simulation. Then we continue with (partial) coverage path planning problems involving turn costs, which require different approaches than when minimizing only the traveled distance. We engineer an approximation algorithm based on linear relaxation and minimum-weight perfect matching to solve large instances in grid graphs. This approach is then generalized to complex polygonal instances, which allow modeling of difficult real-world scenarios. Afterward, we focus on probing a set of trajectories to maximize the captured information, where we successfully apply mixed integer programming and a set of heuristics. We also consider robots so small they need to be actuated by external forces like a magnetic field; applications for such robots include cancer treatment. Construction plans for miniature objects are computed using SAT-solvers, and control sequences to gather a swarm of these robots are optimized using deep reinforcement learning. Finally, we close the thesis with an excursion in hosting the CG:SHOP competition for three years and counting.
Viele der praktisch relevanten Probleme in der Computational Geometry sind beweisbar schwer zu lösen. In dieser Ausarbeitung betrachten wir eine Reihe solcher Probleme und lösen sie mit Techniken aus dem Algorithm Engineering, z.B., Mixed Integer Programming oder Deep Reinforcement Learning. Zusätzlich erlangen wir etliche Erkenntnisse zur Komplexität und Algorithmen für diese Probleme. Wir beginnen mit diversen Problemen, die im Kontext von größeren Satellitensystemen auftreten und bei denen die Kommunikation das Rotieren von gerichteten Antennen erfordert. Hier entdecken wir einen engen Zusammenhang zum Graphenfärbungsproblem, nutzen Constraint Programming zur Berechnung von optimalen Lösungen und entwickeln einen praktischen, auktionsbasierten Algorithmus, der gute Ergebnisse in realistischen Simulationen erzielt. Danach fahren wir mit dem (Partial) Coverage Path Planning Problem unter der Berücksichtigung von Abbiegekosten fort, welches andere Ansätze braucht, als wenn wir nur die gefahrene Distanz minimieren wollen. Hierfür implementieren wir einen Approximationsalgorithmus - basierend auf linearer Relaxierung und Minimum-Weight Perfect Matching - auf eine Art, die es ermöglicht, auch große Instanzen im Gittergraphen zu optimieren. Dieser Ansatz wird anschließend von uns für komplexe polygonale Instanzen erweitert, was die Modellierung von schwierigen, realistischen Szenarien erlaubt. Anschließend fokussieren wir uns auf die Maximierung von eingeschlossenen Informationen aus einer Menge von Trajektorien, wo wir erfolgreich Mixed Integer Programming sowie eine Menge von Heuristiken anwenden. Wir betrachten auch Roboter, die so klein sind, dass sie nur durch äußere Kräfte - wie etwa ein magnetisches Feld - bewegt werden können und einen potentiellen Einsatz in der Tumorbehandlung haben. Konstruktionspläne für Miniaturobjekte berechnen wir mittels SAT-Solvern, und Kontrollsequenzen zum Sammeln eines solchen Roboterschwarms optimieren wir mittels Deep Reinforcement Learning. Letztlich schließen wir diese Arbeit mit einem Ausflug in die Organisation der CG:SHOP Challenges.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved