Geometry Lab: Erkundung einer unbekannten Umgebung mit Gitterstuktur

Geometry Lab
[][]

Erkundung einer unbekannten Umgebung mit Gitterstuktur

Theorie

Unser Ziel ist es, eine möglichst kurze Explorationstour zu finden, d.h. die Anzahl der Schritte des Roboters soll möglichst klein sein. Als Gütemaß einer Strategie betrachten wir den kompetitiven Faktor c; das Verhältnis der Länge des online berechneten Tour zur Länge des optimalen Tour.

Obere Schranke

Die erste Frage ist, ob der Roboter überhaupt in der Lage ist, das Optimum bis auf einen konstanten Faktor zu approximieren, wenn die Umgebung nicht bekannt ist. Diese Frage läßt sich leicht beantworten:

Theorem 1: Die kompetitive Komplexität der Erkundung einer unbekannten Umgebung mit Hindernissen ist 2.

Der Roboter kann diese durch eine einfache Tiefensuche (DFS) auf dem Zellgraphen erreichen. Der Zellgraph ist ein Graph, der für jede Zelle der Umgebung einen Knoten und Kanten zwischen adjazenten Zellen enthät. DFS benötigt 2(C-1) Schritte, wobei C die Anzahl der Zellen ist: für jede Zelle bis auf die Startzelle brauchen wir einen Schritt um die Zelle zum ersten Mal zu betreten und einen Schritt, um die Zelle zum letzten Mal zu verlassen. Die optimale Strategie braucht dagegen (mindestens) C Schritte, um jede Zelle einmal zu besuchen. Beispiel:

Abb. 1: Zu erkundendes Polygon.

Abb. 2: Zellgraph des Polygones.

Abb. 3: DFS Erkundung mit 2(C-1)=30 Schritten.

Abb. 4: Optimale Erkundung.

Untere Schranke

Theorem 2: 2 ist auch untere Schranke die Erkundung gitterförmiger Umgebungen

Zum Beweis, beobachten wir zunächst das Verhalten des Roboters in einem Korridor. :

Fall 1

Der Roboter erkundet jeweils einen Teil des Korridors und kehrt periodisch zu seinem Startpunkt zurück :

Nun schiessen wir den Korridor mit jeweils einer unerkundeten Zelle an beiden Enden :

Der Roboter hat bereits mindestens 2R-2 Schritte zurückgelegt und muß noch 2R+2 laufen, um die Umgebung vollständig zu erkunden. Optimal wären 2R+2 Schritte gewesen.

Fall 2

Im 2. Fall kehrt der Roboter nicht regelmäßig zum Startpunkt zurück, sondern konzentriert sich mehr oder weniger auf ein Ende des Korridors :

Nun trifft der Roboter auf eine Gabelung. Die beiden neuen Korridore verlaufen jeweils parallel zum gerade vom Roboter erkundeten Tunnel. :

Sollte der Roboter jetzt umkehren, und zum Startpunk zurückkehren, kann man ähnlich wie im 1. Fall argumentieren. Konzentriert er sich mehr oder weniger auf einen der beiden Äste, so verbinden wir den Ast mit dem Korridor, in dem der Roboter gestartet ist. Den anderen Ast schiessen wir mit einer unerkundeten Zelle :

Der Roboter hat bereits 2R+2P Schritte benötigt, und braucht weitere 2R+2P Schritte. Optimal sind 2R+2P Schritte.

Literatur

Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe
On the competitive complexity of navigation tasks
Sensor Based Intelligent Robots,
LNCS 2238, Springer, Berlin, 2002, pp. 245-258.
Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe
Exploring an Unknown Cellular Environment
Abstracts 16th European Workshop Comput. Geom., Eilat,
Ben-Gurion University of the Negev, 2000, pp. 140-143.
Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe
Exploring an Unknown Cellular Environment
Unpublished Manuscript, FernUniversität Hagen, 2000.

[ Die Simulationsumgebung ] [ Die Oberfläche ] [ Der Polygoneditor ] [ Theoretische Hintergründe ]

[ Applet starten ]

Startseite Sitemap Über geometrylab.de