Parameterizations in the Configuration Space and Approximations of Related Surfaces

Abstract

This work covers three topics that can all be linked to the celebrated motion planning problem of planar robots. When considering a planar robot, which is represented by a convex polygon, it is natural to study an associated configuration space, where each point corresponds to a unique placement of the robot in its physical world. Obstacles in the world of the robot are represented as three-dimensional solids in the associated configuration space. The union of these solids is the so-called forbidden space. Each point of the forbidden space corresponds to a placement of the robot such that its interior intersects one or more obstacles. The remainder of the configuration space is the so-called free space. Of course, the boundary between the free and forbidden spaces is of tremendous interest. The first part of the dissertation provides a simple and geometrically motivated parameterization of the surfaces that constitute the mentioned boundary. Using this parameterization, it is easy to produce various visualizations of the boundary. Furthermore, standard computations that utilize the parameterization yield deep understanding of the differential geometry of the boundary. Clearly, these are two achievements that contribute to the general study of the motion planning problem. In particular, it is also shown that the elements of the boundary corresponding to contacts between an edge of the robot and a vertex of an obstacle are non- developable ruled surfaces --- thus having a negative Gaussian curvature. The negatively curved surfaces that emerge as portions of the discussed boundary, motivated a search for an optimal triangulation of simpler negatively curved surfaces. Specifically, hyperbolic paraboloids (also know as saddles) are considered. The second part of the dissertation provides both interpolating and non-interpolating triangulations of general saddle surfaces. The optimality of the yielded triangulation used for the approximation is twofold:(i) it maintains a fixed error bound, and (ii) minimizes the number of triangles needed to cover a given portion of the saddle. Finally, the third part of the dissertation provides a detailed account of a contribution to the 2D Arrangements package of the "Computational Geometry Algorithms Library". This part of the work considers the computation of arrangements of bounded piecewise linear curves (polylines) in the plane. More precisely, the initial package code, as shipped with version 4.3, was considerably improved in two senses. First, the computations of arrangements of polylines using the modified code improves execution time by about 5% (on average). Secondly, the modified code is much more generic and suitable for further generalizations. As a result, the improved code was accepted for integration into the library and is scheduled to be shipped with its next release. Together, the achievements presented in the dissertation can contribute to the ongoing study of the motion planning problem, as well as to numerous more general purposes.

Diese Arbeit betrachtet drei Themen, die alle dem berühmten Bewegungsplanungsproblem für Roboter in der Ebene zugeordnet werden können. Beim Arbeiten mit Robotern in der Ebene werden diese als konvexe Polygone dargestellt und es wird ein dazugehöriger Konfigurationsraum betrachtet, in welchem jeder Punkt einer eindeutigen Platzierung des Roboters in seiner physikalischen Umgebung entspricht. Hindernisse in der Welt des Roboters werden als dreidimensionale Festkörper im Konfigurationsraum betrachtet. Die Vereinigung aller dieser Körper bilden den sogenannten verbotenen Konfigurationsraum. Jeder Punkt des verbotenen Konfigurationsraum entspricht einer nicht realisierbaren Platzierung des Roboters zwischen den Hindernissen. Der Rest des Konfigurationsraumes ist der sogenannte freie Konfigurationsraum. Das Hauptinteresse liegt genau auf der Grenze zwischen dem freien und dem verbotenen Konfigurationsraum. Der erste Teil dieser Dissertation beinhaltet eine einfache und geometrisch motivierte Parametrisierung von jenen Oberflächen, die genau die erwähnte Grenze darstellen. Durch Benutzung dieser Parametrisierung ist es sehr einfach, unterschiedliche Visualisierungen der Grenze zu erzeugen. Zudem können tiefe Einblicke in die Differentialgeometrie der Grenze gewonnen werden, wenn Standardberechnungen unter Benutzung dieser Parametrisierung durchgeführt werden. Diese beiden Ergebnisse tragen eindeutig zur allgemeinen Arbeit an Bewegungsplanungsproblemen bei. Insbesondere wird auch gezeigt, dass die Elemente der Grenze, die Kontaktpunkte zwischen einer Kante des Roboters und einer Ecke eines Hindernisses darstellen, nicht abwickelbare Regelflächen sind --- und so eine negative Gaußsche Krümmung aufweisen. Die negativen gekrümmten Oberflächen, die als Teile der Grenze auftreten können, regten die Suche nach einer optimalen Triangulierung für einfachere negativ gekrümmte Oberflächen an. Insbesondere werden hyperbolische Paraboloide (auch als Sattelfläche bekannt) betrachtet. Im zweiten Teil der Dissertation werden interpolierende und nicht interpolierende Triangulierungen von allgemeinen Satteloberflächen präsentiert. Die Optimalität der erzeugten Triangulierung, die für die Approximation benutzt wird, ist durch zwei Eigenschaften charakterisiert: (i) sie garantiert eine feste Fehlerschranke und (ii) sie minimiert die Anzahl der benötigten Dreiecke um einen gegebenen Teil der Sattelfläche zu überdecken. Der dritte Teil der Dissertation liefert eine detaillierte Beschreibung eines Beitrages für das 2D Arrangements Paket der "Computational Geometry Algorithms Library" (CGAL). Hierbei wird die Berechnung von Arrangements von begrenzten teilweise linearen Kurven (polygonale Kurven) in der Ebene behandelt. Das ursprüngliche in der Version 4.3. enthaltene Codepaket wurde stark verbessert. Zum einen konnte die Berechnungszeit von Arrangements von polygonalen Kurven (im Durchschnitt) um 5 Prozent beschleunigt werden. Zusätzlich ist der geänderte Code generischer und daher besser geeignet für weitere Verallgemeinerungen. Daher wurde der verbesserte Code auch dazu ausgewählt in die Bibliothek (CGAL) integriert zu werden und es ist geplant, ihn in die nächste Version einzubinden. Alles in allem tragen die Ergebnisse dieser Arbeit sowohl zur Arbeit an Bewegungsproblemen bei, als auch zu zahlreichen allgemeineren Zwecken.