 |
|
| Informatik Abt. I | Diplomarbeiten im Bereich Bahnplanung für Roboter |
|
|
|
| Informatik Abt. I | Diplomarbeiten im Bereich Bahnplanung für Roboter |
Zur Berechnung einer kollisionsfreien Bahn für eines nicht-konvexen Roboters in einer polygonalen Umgebung, der nur Translationsbewegungen durchführen kann, gibt es einen effizienten Algorithmus, der auf der Theorie von Davenport Schinzel Sequenzen basiert. Aus Effizienzgründen wird nicht der gesamte Teilraum berechnet, in dem sich der Roboter kollisionsfrei bewegen kann. Viel mehr ist man an diejeniege Zelle interessiert, in der der Roboter zu Beginn steht. Der Algorithmus ist ein Divide and Conquer Verfahren, dass im Merge-Schritt die Zusammenmischung zweier Arrangements effizient löst (Red-Blue-Merge).
Aufgabe dieser Arbeit ist, diesen Algorithmus in ein bestehendes Java-Applet zu integrieren. Dieses Applet stellt bereits einen sehr komfortablen Polygoneditor (siehe Screenshot) und grundlegende Funktionen zur Simulation von Roboterstrategien zur Verfügung. Es soll jedoch nicht nur das Endprodukt (der berechnete Weg) angezeigt werden. Vielmehr soll der Benutzer einen Einblick in die vom Algorithmus benutzten Datenstrukturen und Zwischenergebnisse bekommen. Dies soll zum einen Studenten beim Verständnis des Algorithmus helfen, zum anderen die Forschung in diesem Bereich unterstützen. So ist auch die Frage interessant, ob der vorgestellte Algorithmus nicht stellenweise vereinfacht werden kann. Dieser Aspekt kann auch im Rahmen der Diplomarbeit untersucht werden.
Literatur
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Unter einer gitterförminge Umgebung verstehen wir ein Polygon, das aus einzelnen Zellen zusammengesetzt ist. Wenn der Roboter sich in einer Zelle befindet, kann er ertasten, welche der Nachbarzellen zum Polygon gehören und welche Hinderniszellen sind, und kann sich auf eine benachbarte Zellen des Polygons bewegen. Die Aufgabe des Roboters ist, jede Zelle zu besuchen und dabei möglichst wenige Zellen mehrfach aufzusuchen. Das Beispiel zeigt die Erkundung einer gitterförmigen Umgebung im 2D.
Für den zweidimensionalen Fall sind bereits einige Strategien bekannt und sowohl theoretisch als auch exprimentell eingehend untersucht. Eine Experimentierumgebung in Form eines Java-Applets befindet sich unter http://web.informatik.uni-bonn.de/I/GeomLab/Gridrobot/
Die Ziele dieser Arbeit sollen sein:
Eine Experimentierumgebung für die Erkundung gitterförmiger Umgebungen in 3D zu erstellen, dazu zählt ein Editor für dreidimensionale Umgebungen und die Simulation von Erkundungsstrategien. Eine gute Vorlage für den gewünschten Funktionsumfang ist das Applet für den zweidimensionalen Fall.
Das Verhalten von vorhandenen Erkundungsstrategien im 3D zu untersuchen: wie weit lassen sich bekannte Strategien einfach auf den 3D Fall erweitern?
Natürlich ist der Entwurf einer eigenen Erkundungsstrategie nicht unerwünscht, aber auch nicht unbedingt notwendig.
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Literatur
Unter einer gitterförminge Umgebung verstehen wir ein Polygon, das aus einzelnen Zellen zusammengesetzt ist. Wenn der Roboter sich in einer Zelle befindet, kann er ertasten, welche der Nachbarzellen zum Polygon gehören und welche Hinderniszellen sind, und kann sich auf eine benachbarte Zellen des Polygons bewegen. Die Aufgabe des Roboters ist, jede Zelle zu besuchen. Das Beispiel zeigt die Erkundung einer gitterförmigen Umgebung.
Wir wollen in einer solchen Umgebung Roboter betrachten, deren Orientierungssinn sehr eingeschränkt ist, konkret: sobald sich ein Roboter von der Wand löst, ist seine Position unbekannt, und er bewegt sich auf einer geraden Bahn, bis er wieder auf eine Wand oder auf einen anderen Roboter trifft. In der Umgebung befinden sich jedoch mehrere Roboter, die von einem zentralen System gesteuert werden und sich gegenseitig als 'Markierungen' benutzen können.
Im praktischen Teil der Arbeit soll das vorhandene Java-Applet http://web.informatik.uni-bonn.de/I/GeomLab/Gridrobot/ erweitert werden, um mit Robotern dieses Typs experimentieren zu können.
Im experimentellen/theoretischen Teil sollen mit Hilfe des Applets und in Zusammenarbeit mit dem Betreuer strukturelle Erkenntnisse über dieses Problem gewonnen werden. So kann z.B. an folgenden Fragen gearbeitet werden:
Gibt es für bestimmte Typen von Szenen untere Schranken für die Anzahl der Roboter, so daß jedes Feld der Umgebung erreicht werden kann?
Gegeben eine Szene, ein Zielpunkt und mehrere Roboter. Wie schwierig ist es zu entscheiden, ob der Zielpunkt erreicht werden kann? Existiert ein effizienter Algorithmus?
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Literatur
Zur Berechnung einer kollisionsfreien Bahn für einen konvexen Roboter in einer polygonalen Umgebung, der sowohl mit Translations- als auch mit Rotationsbewegungen durchführen kann, gibt es einen relativ aufwendigen Algorithmus.
Aufgabe dieser Arbeit ist, diesen Algorithmus in ein bestehendes Java-Applet zu integrieren. Dieses Applet stellt bereits einen sehr komfortablen Polygoneditor (siehe Screenshot) und grundlegende Funktionen zur Simulation von Roboterstrategien zur Verfügung. Es soll jedoch nicht nur das Endprodukt (der berechnete Weg) angezeigt werden. Vielmehr soll der Benutzer einen Einblick in die vom Algorithmus benutzten Datenstrukturen und Zwischenergebnisse bekommen. Dies soll zum einen Studenten beim Verständnis des Algorithmus helfen, zum anderen die Forschung in diesem Bereich unterstützen. So ist auch die Frage interessant, ob der vorgestellte Algorithmus nicht stellenweise vereinfacht werden kann. Dieser Aspekt kann auch im Rahmen der Diplomarbeit untersucht werden.
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Literatur
[ Geometrie Labor ]
© Universität Bonn, Informatik Abt. I - webmaster - Letzte Änderung: Wed Jul 16 14:12:07 2008