Softwarepraktikum
"Navigation in unbekannten Umgebungen"
Sommersemester 2003
Prof. Dr. Susanne Albers
mit Markus Schmidt und Gereon Frahling
Neuigkeiten
Es gibt interessante Polygon-Instanzen zum Download. Damit könnt Ihr Eure Algorithmen testen. Falls Eure Offline-Algorithmen die Schnecke und die großen Polygone bearbeiten können, sollten sie eigentlich auch auf allen Landschaften korrekt funktionieren.
Weiterhin gibt es einige Testinstanzen für das Wall- und das Room-Problem.
Die Präsentationen vom 3./4. Juni als PDF:
In diesem Praktikum untersuchen wir das folgende Problem: Ein Roboter muss in einer Szene einen möglichst kurzen Pfad von einen Startpunkt S zu einem Zielpunkt T finden. Die Szene besteht dabei aus Rechtecken oder auch komplizierteren geometrischen Gebilden wie Polygonen.
Innerhalb des Praktikums sollen folgende Problemstellungen gelöst und in Java implementiert werden:
- Als erstes wird eine Simulationsumgebung erstellt, mit der man später implementierte Algorithmen visualisieren und testen kann. Diese bildet die Grundlage für die weiteren Aufgaben.
- Dem Roboter sei die gesamte Szene von Anfang an bekannt. Es soll ein möglichst kurzer Weg in der bekannten Szene vom Start- zum Zielpunkt ermittelt werden.
- Der Roboter befindet sich in einer für ihn unbekannten Szene. Trotzdem soll er durch intelligente Algorithmen möglichst schnell das Ziel erreichen. Dabei darf er die beim Umherlaufen gewonnene Information nutzen.
- Der Roboter soll jeden Gegenstand einmal berüren, z.B. um Lagerbestände zu prüfen.
Lernziele
des Praktikums:
Umgang mit Werkzeugen,
objektorientiertes Programmieren, Implementierung von Algorithmen,
Arbeit in Kleingruppen, Dokumentation
und Präsentation der Programme
Voraussetzungen: Kenntnisse in Java
Literatur:
- A. Blum, P. Raghavan and B. Schieber. Navigating In unfamiliar geometric terrain, SIAM Journal on Computing, 26:110-136, 1997 (.ps),(.pdf)
- P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosen and M. Saks. Randomized robot navigation algorithms, Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, 74-84, 1996. (.ps),(.pdf)
- G. Krüger Handbuch der Java-Programmierung, Addison-Wesley 2002, ISBN 3-8273-1949-8
- G. Krüger Handbuch der Java-Programmierung, online-Version
- P. Fischer Grafik-Programmierung mit Java-Swing, Addison-Wesley 2001, ISBN 3-8273-1910-2
- S. J. Metsker Design Patterns Java Workbook, Addison-Wesley 2002, ISBN 0201743973
- CVS (Concurrent Versions System) Manual http://www.cvshome.org/docs/manual/
- Java 1.4.1 Dokumentation http://java.sun.com/j2se/1.4.1/docs/
 |