Uni-Logo
Algorithms and Complexity
 


Software-Praktikum "Exploration von unbekannten Umgebungen"
Wintersemester 2004/05
Prof. Dr. Susanne Albers und Markus Schmidt



Anmeldung


in der zentralen Software-Praktika-Veranstaltung: Mittwoch, 20.10.2004, 14 Uhr, Gebäude 82, Hörsaal 6  


Praktikum

mittwochs 14-18 Uhr, Gebäude 79, Raum 12.  


Inhalt der Veranstaltung

Wir betrachten einen Robotor, der in einer ihm unbekannten Umgebung abgesetzt worden ist und dessen Aufgabe darin besteht, von dieser Umgebung eine Karte anzufertigen. Hierzu muss er die gesamte Fläche der Umgebung ablaufen, wobei sich in dieser auch Hindernisse befinden können. Es handelt sich hierbei um ein Online-Problem, d.h. der Roboter weiß anfangs nichts über die Lage der Hindernisse. Ein solches wird ihm erst dann bekannt, wenn er gegen es stößt. Da er sie nicht überwinden, sondern nur an ihnen entlang laufen kann, erschweren die Hindernisse dem Roboter die weitere Vervollständigung der Karte. Ziel ist es, den Roboter so durch die Landschaft zu steuern, dass er eine komplette Umgebungskarte erstellt und dabei möglichst wenig Weg zurücklegt.

Im Praktikum arbeiten wir in Teams von zwei bis drei Personen und benutzen die Entwicklungsumgebung Eclipse. Zunächst erstellen wir unter Verwendung von Java-Swing eine grafische Benutzeroberfläche, in der man mittels Mauszeiger navigieren kann. In diese Oberfläche betten wir unsere Szenarien, bestehend aus Hindernissen und Roboterbewegungen, ein.  Wir erzeugen zufällige Hindernislandschaften und implementieren verschiedene Explorationsalgorithmen in Java. Die Implementierungen werden an vorgegebenen Beispielinstanzen getestet. Wir modellieren unser Projekt mit UML und dokumentieren die von uns geschriebenen Klassen ausführlich mit JavaDoc.


Erfolgreiche Teilnahme

Voraussetzung für die erfolgreiche Teilnahme sind die korrekte Implementierung der Oberflächensteuerung und der Explorationsalgorithmen sowie eine Präsentation am Ende des Praktikums


Literatur
  • S. Albers, K. Kursawe und S. Schuierer. Exploring Unknown Environments with Obstacles, Algorithmica 32, 123-143, 2002
  • M. Betke, R.L. Rivest und M. Singh. Piecemeal Learning of an Unknown Environment, Proceedings of the 5th Conference on Computational Learning Theory, 277-286, 1993
  • B. Daum. Java-Entwicklung mit Eclipse 2, dpunkt.verlag 2003, ISBN 3-89864-227-5
  • P. Fischer. Grafik-Programmierung mit Java-Swing, Addison-Wesley 2001, ISBN 3-8273-1910-2
  • G. Krüger. Handbuch der Java-Programmierung, 3. Auflage, Addison-Wesley 2002, ISBN 3-8273-1949-8
Startkonfiguration
Exploration
Wellenfronten