Exploration von geometrischen Umgebungen mit Hindernissen

gegebenes Szenario einen minimalen Weg zu finden, jeden Punkt
dieses Szenarios mindestens einmal gesehen hat.

In dieser Arbeit werden Online-Explorationsalgorithmen untersucht.
Im Gegensatz zum klassischen Algorithmus kennt dieser das Szenario
zun"achst nicht, sondern nur die Teile, die er bereits gesehen hat.
Ziel ist es, unter diesen Umst"anden einen Weg zu finden, dessen L"ange
m"oglichst wenig von der des optimalen Weges abweicht. Den Quotienten
zwischen dem Weg des Online-Algorithmus und des optimalen Weges nennt man
Kompetitivit"atsrate.

Wir betrachten zwei Modellierungen der Umgebung.
Zun"achst wird sie durch eine Menge von Polygonen dargestellt, deren
Umrandungen die Sicht des Roboters begrenzen. Wir zeigen, da"s die
Kompetitivit"atsrate abha"ngig von der Anzahl der Hindernisse ist und
entwickeln einen Algorithmus f"ur den Sonderfall quadratischer Hindernisse.
Als zweites Modell wird das Szenario von einem Gittergraphen "uberdeckt,
den der Roboter komplett "uberstreichen mu"s. Wir verallgemeinern einen
Algorithmus von Betke et al. zur st"uckweisen Exploration eines Szenarios
mit rechteckigen Hindernissen auf den Fall beliebiger Hindernisse.