Uni-Logo
Algorithms and Complexity
 


Softwarepraktikum
"Navigation in unbekannten Umgebungen"
Sommersemester 2003
Prof. Dr. Susanne Albers
mit Markus Schmidt und Gereon Frahling




Di, 14-16 Uhr, Geb 79, Poolraum 1.Stock

Mi, 14-16 Uhr, Geb 79, Poolraum 1.Stock


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:
  1. 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.
  2. 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.
  3. 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.
  4. 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/