Die Arbeit behandelt ein Bewegungsplanungsproblem, bei dem es darum geht, einen zeitoptimierten kollisionsfreien Weg für einen Agenten zwischen Start- und Zielpunkt in einer quadratischen Umgebung mit sich bewegenden kreisförmigen Hindernissen zu finden. Der Agent darf für beliebige Zeitabschnitte eine Beschleunigung mit einem vorgegebenen maximalen Betrag wählen und kann seine Position und Geschwindigkeit nur durch die Beschleunigung ändern, deswegen bewegt er sich auf Bahnkurven und ist in seiner Manövrierbarkeit stark eingeschränkt.

Die in der Arbeit vorgestellte Lösung der Aufgabe beruht auf einer Diskretisierung des Problems, die zu einer heuristischen Wegsuchstrategie führt. Die entwickelten Algorithmen wurden implementiert, ihre Güte und mögliche realistische Anwendungsszenarien werden diskutiert.

This bachelore thesis deals with a motion planning problem, which is about finding a time optimized collision-free path for an agent between two points in a square environment with moving circular obstacles. The agent may choose different time intervals with a fixed limited acceleration. He changes his position and velocity by his acceleration, which impacts his trajectory and reduces his maneuverability.

The thesis presents a discretization of the problem which leads to a heuristic path searching strategy. The developed algorithm has been implemented, both its quality and possible realistic applications are discussed.

1. Einführung in die Aufgabenstellung und grundlegende Definitionen
   1. Zur Vorgeschichte dieser Arbeit
   2. Aufbau der Arbeit
   3. Beschreibung, Formalisierung und Einordnung der Aufgabe als Bewegungsplannungsproblem
   4. Realistische Anwendungsszenarien
2. Physikalische Grundlagen und Berechnungen
   1. Bewegungsberechnung für Hindernisse
   2. Bestimmung einer elementaren Bewegung
   3. Kollisionsprüfung für bewegliche Objekte
3. Der Lösungsansatz durch die RAMP-Heuristik
   1. Vorüberlegung
   2. Aufbau der RAMP-Heuristik
   3. Reach - Finden von Wegpunkten
   4. Eval - Bewertungsfunktion für Wegpunkte
   5. Beispielhafter Ablauf der RAMP-Heuristik
   6. Laufzeitanalyse
4. Implementierung der RAMP-Heuristik
   1. Übersicht und Funktionalitäten des Programmes
   2. Klassenmodell
   3. Diagnosewerkzeuge
   4. Performance der Implementierung
5. Diskussion und Ausblick
   1. Diskussion: Entwicklung der RAMP-Heuristik
   2. Kritische Betrachtung der RAMP-Heuristik
   3. Verbesserungsmöglichkeiten für zukünftige Arbeiten
   4. Ausblick: Komplexitätsstatus des Problems
   5. Ausblick in Richtung eines Online-Algorithmus

• [1] Esther M. Arkin, Joseph S. B. Mitchell, and Valentin Polishchuk. MaximumThick Path in Static and Dynamic Environments. ACM Symposium on Computational Geometry, 2008. pp. 1-2.
• [2] John Canny and John Reif. Lower Bounds for Shortest Paths and RelatedProblems. 28th Annual IEEE Symposium on Foundations of Computer Science, 2006. pp. 18-22.
• [3] M. Sharir and J. Reif. Approximate Kinodynamic Planning Using L2-NormDynamic Bounds. Journal of the Association for Computing Machinery Vol 41, 1994. pp. 44.
• [4] M. Sharir and J. Reif. Motion Planning in the Presence of Moving Obstacles. Journal of the Association for Computing Machinery Vol 41, 1994. pp. 765-768.
• [5] Kenneth O. Stanley. Efficient Evolution of Neural Netweorks throughComplexification. The University of Texas at Austin, 2004. pp. 77-89.
• [6] Carl Witt, Tobias Wenzel, and Benjamin Eckstein. Wettbewerb Informaticup2009. vgl. Jahresbericht 2009/2010 Gesellschaft für Informatik E.V. pp. 23-24.
• [7] H. J. Wolfson and Rigoutsos. Geometric Hashing: An Overview. IEEE Computational Science and Engineering, 1997. pp. 12-13.