Zu den Grundaufgaben autonomer mobiler Roboter gehören heute unter anderem das Rasen mähen und Staub saugen, das Suchen nach Gegenständen und das vollständige Erkunden von unbekannten Umgebungen. Für diese Aufgaben entwickeln wir die methodischen Grundlagen für effiziente Strategien.

Das hier vorgestellte Applet dient zur Simulation verschiedener Strategien zur Erkundung unbekannter Umgebung mit Gitterstruktur.

Unten sehen Sie zwei Erkundungsbeispiele. Links das Ergebnis einer Online-Exploration, rechts eine der optimalen Möglichkeiten.

Online berechnet

Online Tour

Optimale Tour

Optimale Tour

[ Die Simulationsumgebung ] [ Theoretische Hintergründe ]

Simulationsumgebung

Mit Hilfe des Applets können verschiedene Strategien zur Erkundung beliebiger, benutzerdefinierter Polygone erprobt werden. Ein Polygon ist dabei aus einzelnen Zellen zusammengesetzt und enthält eine ausgezeichnete Zelle - die Startzelle - an die der Roboter seine Erkundung beginnt und zu der der Roboter zurückkehren muß, wenn das gesamte Polygon erkundet ist.

example Abb. 1: Beispielpolygon mit Hindernissen

Der Roboter kennt seine Umgebung zunächst nicht. Er kann nur erkennen, welche der unmittelbar an seinen Standort angrenzenden Zellen Hindernisse ("Löcher") sind und welche er betreten darf. In dem Polygon aus Abb. 1 erkennt der Roboter (rotes Quadrat) am Startpunkt zwei Hinderniswände und zwei freie Zellen (Hellgrau), siehe Abb. 2. Der Roboter darf sich jedoch eine Karte seiner Umgebung anfertigen; er darf sich merken, welche der Zellen, die er schon "gesehen" hat, Hindernisse sind und welche freie Zellen. Weiter darf er Zusatzinformationen zu den Zellen speichern um seinen Weg zu planen, z.B. Zellen für den Rückweg reservieren, siehe Abb. 3.

startcell Abb. 2: "Sicht" des Roboters von der Startzelle

some steps Abb. 3: Der Roboter (Rot) hat ein paar Zellen erkundet (Grün) und einige vorgemerkt (Dunkelgrau)

In dem Applet sind verschiedene Strategien zur Erkundung des Polygons implementiert. Außerdem kann der Roboter manuell bewegt werden, wobei zwischen verschiedenen Ansichten (ganzes Polygon, nur erkundetes Polygon) gewählt werden kann. Die Animation in Abb. 4 zeigt die Erkundung des Polygons aus Abb. 1 durch die Strategie CellExplore.

  Abb. 4: Exploration eines Polygons mit CellExplore

Weiterhin stellt das verschiedene Gegenstrategien bereit, mit denen untere Schranken das Erkundungsproblem gezeigt werden.

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:

Zu erkundendes Polygon  Abb. 1: Zu erkundendes Polygon.

Zellgraph des Polygones  Abb. 2: Zellgraph des Polygones.

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

Optimale Erkundung  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:

[1]: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.
[2]: 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.
[3]:Christian Icking, Thomas Kamphans, Rolf Klein, Elmar Langetepe
Exploring an Unknown Cellular Environment
Unpublished Manuscript, FernUniversitšt Hagen, 2000.