 |
|
| 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. Das Beispiel zeigt die Erkundung einer gitterförmigen Umgebung.
Für das Ziel, die vom Roboter zurückgelegte Wegstrecke möglichst kurz zu halten, 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 von den bekannten Strategien erzeugten Wege sind jedoch relativ unbefriedigend wenn man sich vorstellt, der Roboter wäre ein Rasenmäher und würde so gewundene Bahnen fahren, wie sie von den Strategien erzeugt werden. Wünschenswert wäre hier, möglichst lange Bahnen zu fahren, oder die Anzahl der Knicke in den Bahnen zu minimieren.
Gegenstand der Arbeit ist, zu betrachten, welche anderen Kostenmaße neben der Weglänge für die Erkundung gitterförmiger Strategien in Frage kommen und ob bzw. wie sich vorhandene Strategien auf andere Kostenmaße anpassen lassen. Ein praktischer Teil der Arbeit könnte sein, das oben genannte Applet um weitere Strategien zu erweitern.
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Literatur
Die Suche nach einem Zielpunkt in einem einfachen Polygon ist im allgemeinen nicht kompetitiv, d.h. es gibt keine Konstante C, so daß für alle Polygone |ONL| <= C * |OPT| gilt, wobei |ONL| die Länge eines online berechneten Pfades ist und |OPT| die optimale Weglänge: der kürzeste Pfad vom Start zum Ziel.
Dennoch gibt es in Polygonen Pfade, die sich besser zum Suchen eines Zielpunktes eignen als andere. Mit einem anderen Qualitätsmaß als den Kompetitiven Faktor, nämlich der Search Ratio, können wir Suchwege klassifizieren. Leider ist bisher kein Algorithmus bekannt, den bzgl. der Search Ratio optimalen Pfad in einfachen Polygonen zu bestimmmen, jedoch ist eine Online-Approximation bekannt.
Ziel der Arbeit ist zunächst, ein Java-Applet zu erstellen, mit dem Suchwege und deren Güte in Polygonen berechnet werden können. Der Benutzer soll die Möglichkeit haben, ein einfaches Polygon und einen Suchweg einzugeben und die Güte dieses Suchweges berechnen zu lassen. Zur Implemtierung steht die Geometrie-Bibliothek des Lehrgebietes zur Verfügung, die u.a. schon einen Polygoneditor enthält; siehe www.geometrylab.de/Polyrobot/.
Im weiteren sollen Heuristiken/Approximationen von optimalen Suchwegen ausgedacht, implementiert und vergleichen werden.
Mehr Informationen bei: Elmar Langetepe oder Tom Kamphans
Literatur
Archiv: bereits bearbeitete Themen
[ Geometrie Labor ]
© Universität Bonn, Informatik Abt. I - webmaster - Letzte Änderung: Wed Jul 16 14:12:07 2008