Dieses Projekt befaßt sich mit dem aktuellen Stand der Forschung
auf dem Gebiet der Exploration unbekannter Umgebungen. In einem unbekannten,
durch ein einfaches Polygon modellierten Raum ohne einbeschriebene Hindernisse
soll ein Roboter eine möglichst kurze Fahrstrecke zurücklegen,
um jeden Punkt des Raums mindestens einmal gesehen zu haben. Das Problem
kann mit der neuen Technik der Angle Hull auf 26.5 mal der optimalen Watchman-Tour
angenähert werden. Dabei ist die optimale Watchman-Tour [CN88]
eine Problemvariante, da dort das Polygon bekannt ist [HIKK98a] [HIKK98b].
Ziele:
Erstes Ziel des Projekts sollte es sein, sich mit dem Problem der Explorationgegebener Polygone vertraut zu machen und den O(n2)-Algorithmus zur Berechnung der optimalen Watchman-Tour zu implementieren.
Mittels des Konzepts der Angle-Hull, welches erst im Oktober 1998 vorgestellt wurde, soll dann in einem zweiten Schritt der 26.5 kompetitive Online-Algorithmus implementiert werden.
Eine Fortführung der Arbeit im Rahmen einer Diplomarbeit ist
möglich.
Weitere Informationen:
| Voraussetzungen: | C++ Kenntnisse, Vordiplom, selbständiges Arbeiten |
| Anzahl der Teilnehmer: | 1-2 |
| Scheinvergabe: | großer Praktikumsschein |
| Beginn: | nach Absprache, evtl. sofort |
| Betreuer: | Dipl.-Inform. Dirk Schäfer, Raum E 15 |
Literatur:
| [CJN93] | Svante Carlsson, Hakan Jonsson, Bengt J. Nilsson. Finding the shortest watchman tour in a simple polygon. LNCS 763, pp. 58-67,1993. |
| [CN88] | Wei-Pang Chin and Simeon Ntafos. Optimum watchman routes. Information Processing Letters 28(1), pp. 39-44, 1988. |
| [HIKK98a] | Frank Hoffmann, Christian Icking, Rolf Klein and Klaus Kriegel. The polygon exploration problem I: A competitive strategy. Technical Report 241, Praktische Informatik, 1998. |
| [HIKK98b] | Frank Hoffmann, Christian Icking, Rolf Klein and Klaus Kriegel. The polygon exploration problem II: The Angle Hull. Technical Report 245, Praktische Informatik, 1998. |