Benutzer-Werkzeuge
paper:motionplanning:section01
Eine Heuristik zur realistischen Bewegungsplanung bei beschränkter Geschwindigkeit und beweglichen Hindernissen
|
|
|
1. Einführung in die Aufgabenstellung und grundlegende Definitionen
1.1 Zur Vorgeschichte dieser Bachelorarbeit
Das Thema der Arbeit entstand während der erfolgreichen Teilnahme bei dem ausgeschriebenen Wettbewerb der Gesellschaft für Informatik e.V, dem “Informaticup 2009”, den der Author zusammen mit Tobias Wenzel (Technische Universität Berlin) und Carl Witt (Freie Universität Berlin) gewonnen hat. Dabei haben wir uns der Problematik gestellt, wie man einen schwer lenkbaren Roboter, den “Agenten”, in kürzester Zeit kollisionsfrei zu seinem Zielpunkt durch ein Areal mit beweglichen Hindernissen manövrieren kann. Die Wettbewerbsaufgabe war in fünf ineinander aufbauende Abschnitte unterteilt. Von der einfachen Kollisionsüberprüfung, über den Fall, dass der Roboter sich mit konstanter Geschwindigkeit direkt zum Ziel hinbewegt, bis zur komplexen physikalischen Steuerung, bei der der Roboter sich im 2-dimensionalen Areal durch gewählte Beschleunigungen frei bewegen kann.
Die Problematik, einen kollisionsfreien zeitoptimierten Weg zu finden, hörte sich für uns simpel an und jeder hat schnell einen ersten Lösungsansatz entwickelt. Mit jedem Abschnitt der Aufgabenstellung nahm die Komplexität zum finden einer optimalen Lösung zu. Der zuerst favorisierte analytische Ansatz stieß an seine Grenzen. Wir sind Kompromisse eingegangen und haben uns entschieden, eine diskretisierte heuristische Wegsuche zu entwickeln.
Das Projekt startete am 01.01.2010 und unsere Lösung wurde Mitte Februar eingereicht. Bis zur Präsentation am 21.03.2010 in Bonn arbeiteten wir rund um die Uhr weiter. Nach dem Wettbewerb im April 2010 hat der Autor sich mit dem Projekt alleine weiterbeschäftigt und viele der Ziele realisiert, die wir bis zum Wettbewerbsende aus zeitlichen Gründen nicht mehr geschafft haben. Im Juli 2010 ist das Projekt zum Thema meiner Bachelorearbeit geworden. Ziel dieser Arbeit ist es, die dabei entstandene Datenstruktur und Weiterentwicklung des ursprünglichen Lösungsansatzes vorzustellen, sowie mögliche zukünftige Modifikationen und Verbesserungen zu diskutieren.
1.2 Aufbau der Arbeit
Die Arbeit gliedert sich in fünf Kapitel. In dem ersten Kapitel wird die Vorgeschichte dieser Bachelorarbeit erwähnt und der Aufbau und die Gliederung geschildert. Desweiteren werden die Grundlagen der Aufgabenstellung genannt und mit realistischen Anwendungsbeispielen illustriert. Anschließend wird die Problematik formalisiert und wichtige Definitionen eingeführt.
Das zweite Kapitel erklärt die benötigten physikalischen Berechnungen und zeigt, dass jede dieser Berechnungen wie z.B. eine Kollisionsüberprüfung in konstanter Zeit in einem entsprechenden Registermaschinen-Modell erfolgen kann.
Das dritte Kapitel erläutert zunächst einige motivierende Vorüberlegungen und anschließend den entwickelten Lösungsansatz mittels einer heuristischen Wegsuche, die im Detail beschrieben und erklärt wird. Ein beispielhafter Ablauf und eine Laufzeitanalyse schließen das Kapitel ab.
Das vierte Kapitel beschäftigt sich mit der Java-Implementierung des Algorithmus und dem dabei entstandenem Programm. Zur Bewertung der Implementation wurden einige Diagnosewerkzeuge entwickelt, die kurz beschrieben werden. Anschließend wird die Performance des Programmes mit Charts visualisiert.
Das fünfte und letzte Kapitel bietet eine Diskussion über die Entwicklung der RAMP-Heuristik und den Erkenntnissen aus dem Verfassen dieser Arbeit. Anschließend folgt ein Ausblick, dabei wird nach einer kritischen Betrachtung des heuristischen Algorithmus mögliche Verbesserungen für künftige Arbeiten skizziert, die Komplexität der Bewegungsplanung im Allgemeinen grob zusammengefasst und ein Ausblick auf die Komplexität des behandelten Problems beschrieben. Am Schluss der Arbeit wird eine Modifikation in Richtung Online-Algorithmus in Aussicht gestellt.
1.3 Beschreibung, Formalisierung und Einordnung der Aufgabe als Bewegungsplanungsproblem
Diese Bachelorarbeit behandelt ein spezielles Bewegungsplanungsproblem, bei dem ein zeitlich optimierter Weg unter Beachtung physikalischer Bedingungen für einen Agenten zwischen Start- und Zielpunkt gesucht wird.
Zum besseren Verständnis wollen wir das Problem anhand eines realistischen Alltagsszenario illustrieren: Wie überquert man zeitsparend und sicher eine Straße? Im verallgemeinerten Fall kann man die Aufgabenstellung mit dem alltäglichen Problem vergleichen, wenn man eine dichtbefahrende Straßen überqueren möchte. Diese Straße wird von Hindernissen (Motorräder, Autos, Lastwagen) mit verschiedener Größe und verschiedenen Geschwindigkeiten befahren. Der Agent muss, um seinen Zielpunkt zu erreichen, die Straße entlang laufen und überqueren. Angenommen wir können den Verkehr abschätzen und damit Bewegung der Hindernisse voraussagen, dann ist es möglich günstige zeitsparende Wege zu finden. Ein optimaler Weg könnte, wie man aus Alltagserfahrung weiß, so aussehen, dass der Agent sich erst vom Ziel wegbewegt, um eine größere Lücke im Verkehrsstrom abzupassen und anschließend zum Ziel läuft um damit schneller zu sein, als wenn er direkt bis vor das Ziel läuft und wartet bis er die Straße überqueren kann.
paper/motionplanning/section01.txt · Zuletzt geändert: 2011/12/30 18:09 von ben