This work is devoted to the design of efficient algorithms for special instances of robot motion planning problems and the prediction of motion of fluids. The intricate nature of these problems may manifest itself in increased computational complexity. For instance, the well-known NP- and PSPACE-hardness results for various classes of motion planning and motion optimization problems seem to imply exponential worst-case running time. Although these results characterize worst case instances, they nevertheless are indicative of the computational difficulty of the problems. The goal of this work is to develop a framework of symbolic-numerical algorithms and software packages using Computer Algebra System Maple, which would allow to increase the efficiency of solving special motion planning and motion prediction problems and provide the possibility to develop efficient approximation methods for computationally hard problems. The main contribution of this work is a novel approach for the motion planning problem for multiple tasks distributed in space, which have to be executed by the robot. We describe an algorithm which computes the minimum-time robot motion due to given velocity and orientation constraints of the robot end-effector during task execution, as well as limits on velocities and accelerations during the overall work-cycle. Given equations of robot motion in matrix form, we utilize the freedom in position and orientation of the robot end-effector during task execution and express the solution space for our optimization task explicitly using computation of Moore-Penrose pseudoinverses of matrices with polynomial entries. Furthermore, we discuss the usage of polynomials to speed-up algorithms for grid generation and numerical solution of two-dimensional incompressible Navier-Stokes equations.     «

This work is devoted to the design of efficient algorithms for special instances of robot motion planning problems and the prediction of motion of fluids. The intricate nature of these problems may manifest itself in increased computational complexity. For instance, the well-known NP- and PSPACE-hardness results for various classes of motion planning and motion optimization problems seem to imply exponential worst-case running time. Although these results characterize worst case instances, th...     »

Die vorliegende Arbeit beschäftigt sich mit dem Algorithmenentwurf für einige spezielle Klassen der Berechnungsprobleme aus den Bereichen Roboterbewegungsplanung und numerische Strömungsmechanik. Die meisten Berechnungsprobleme auf diesen Gebieten zeichnen sich durch eine hohe Berechnungskomplexität aus. Die wohlbekannten komplexitätstheoretischen Ergebnisse zeigen, zum Beispiel, dass viele Bewegungsplanungprobleme NP- und PSPACE-hart sind. Das Ziel dieser Arbeit ist daher der Entwurf symbolisch-numerischer Algorithmen und Softwarepaketen unter Verwendung von Computer Algebra System Maple, die möglichst effeziente Lösung spezieller Klassen der Bewegungsplanungprobleme und Berechungsprobleme der numerischen Simulationen ermöglichen würden. Das Hauptergebnis dieser Arbeit ist ein neuer Ansatz der Bewegungsplanung eines industriellen 6R-Roboters für die Bearbeitung der Aufgaben, die im Raum verteilt sind. Wir stellen einen Alogrithmus für die Berechnung der zeitoptimaln Roboterbahnen vor, der sowohl geometrische Einschränkungen der Bewegung und Orientierung des Roboterwerkzeuges als auch Einschränkungen in der Form der Geschwindigkeiten und Beschleunigungen berücksichtigt.Wir parametrisieren den Lösungsraum für diesen Optimierungsproblem durch die Berechnung der Moore-Penrose-Inversen der Matizen mit polynomiellen Einträgen. Darüber hinaus betrachten wir die Anwendung der Polynome für die Beschelunigung der Algorithmen für Gittergenerierung und für numerische Lösung zweidimensionaler Navier-Stokes-Gleichungen.     «

Die vorliegende Arbeit beschäftigt sich mit dem Algorithmenentwurf für einige spezielle Klassen der Berechnungsprobleme aus den Bereichen Roboterbewegungsplanung und numerische Strömungsmechanik. Die meisten Berechnungsprobleme auf diesen Gebieten zeichnen sich durch eine hohe Berechnungskomplexität aus. Die wohlbekannten komplexitätstheoretischen Ergebnisse zeigen, zum Beispiel, dass viele Bewegungsplanungprobleme NP- und PSPACE-hart sind. Das Ziel dieser Arbeit ist daher der Entwurf symbol...     »