Zielpunktsuche in einer unbekannten Umgebung

Die Aufgabe eines autonomen Roboters mit idealerweise vollständiger Sicht besteht hier darin, ein Ziel in einer unbekannten Umgebung zu finden. Der zurückgelegte Weg soll dabei im Vergleich zum kürzesten Weg zum Ziel nicht zu groß werden. Der Ansatz des Brücken Problems kann zunächst auf eine bestimmte Anzahl von Korridoren verallgemeinert werden. Das Prinzip wird dann auch innerhalb einer polygonalen Umgebung verwendet.

Inhalt des Vortrags:

• Vorstellung des Problems, Modellierung
• m Halbgeraden absuchen, Strategie mit Faktor (Theorem 7.14)
• Suche nach einem Punkt im Polygon
  • Allgemein nicht kompetitiv
  • Untere Schranke, abhängig von den Ecken (Lemma 7.15)
  • Der Baum der kürzesten Wege SPT
  • Doubling auf dem SPT
  • 8n Kompetitivität (Theorem 7.16)

Literatur:

Rolf Klein, Algorithmische Geometrie, Addison Wesley 1997
Kapitel 7.3 S. 341-349 und Anfang des Kapitels (Kompetitivität).

Betreuer:
Rolf Klein