(Wenn Sie hier keinen Button sehen, dann unterstützt Ihr Browser JAVA 1.4. nicht vollständig. In diesem Fall sollten Sie es entweder abschalten oder später versuchen, diese URL erneut aufzurufen, mit dem Appletviewer von JDK1.4.x für Ihr Betriebssystem.)

Das Applet

Dieses Applet veranschaulicht, wie ein dreidimensionales Gitter nach vorgegebener Strategie exploriert wird. Es stehen mehrere Strategien zur Auswahl. Das Gitter muss vor der Exploration vom Benutzer definiert werden.

Um eine gitterförmige dreidimensionale Umgebung besser veranschaulichen zu können, wurde bei der Darstellung der Umgebung stark abstrahiert. So werden keine Würfel zur Darstellung einzelner Zellen genommen, sondern Kugeln. Ein weitere Abstraktion besteht darin, dass die Zellen nicht direkt benachbart sind, sondern zwischen den Zellen gibt es einen Zwischenraum. Weiter werden hier Hinderniszellen als Löcher (engl. holes) betrachtet. Die Zellen können optional durch ein Gitter (engl. Grid) verbunden werden. Im Folgenden wird mit Gitter die Menge der ausgewählten Zellen mit optionalem Grid bezeichnet.

Eine kurze Einführung zum theoretischen Hintergrund dieser Arbeit finden Sie hier.


Benutzung

Das Applet besitzt zwei Modi, einen Editor Modus und einen Explorer Modus. Im Editor Modus wird das Gitter definiert und verändert. Dazu markiert oder löscht man beliebig viele Zellen mit Hilfe der Maus. In beiden Modi kann man das Gitter zoomen, drehen und verschieben. Drehen und Verschieben wird durch Bewegen der Maus ausgeführt und Zoomen wird mit den Buttons, die sich oberhalb des Gitters befinden, gesteuert. Im Explorer Modus findet die Exploration des im Editor definierten Gitters statt. Zur Zeit stehen 3 Strategien zur Auswahl: Manuell, CellExplore und DFS.

Allgemein

Canvas

Panel

Menubar

Buttons

Sliders

Auswahlliste

Shortcuts


Editor

Maus

Popup

Buttons


Explorer

Maus

Popup

Buttons

Strategien

Bei Cell Explore und DFS kann zusätzlich noch die Option "Optimize Return Path" gewählt werden.
Mit "Clear" kann jederzeit alles wieder in die Ausgangsposition zurückgesetzt werden.
Mehr zu den Strategien Cell Explore und DFS finden Sie hier.

Theoretischer Hintergrund

Unter einer gitterförmigen Umgebung verstehen wir ein Polygon, das aus einzelnen Zellen zusammengesetzt ist. Wenn der Roboter sich in einer Zelle befindet, kann er ertasten, welche der Nachbarzellen zum Polygon gehören und welche Hinderniszellen sind, und kann sich auf eine benachbarte Zellen des Polygons bewegen. Die Aufgabe des Roboters ist, jede Zelle zu besuchen und dabei möglichst wenige Zellen mehrfach aufzusuchen.

Für den zweidimensionalen Fall sind bereits einige Strategien bekannt und sowohl theoretisch als auch exprimentell eingehend untersucht. Eine Experimentierumgebung in Form eines Java-Applets findet sich im Applet Gridrobot.

Die Ziele dieser Arbeit sollten sein:

Es wurden bisher die Strategien Cell Explore und DFS umgesetzt.

Cell Explore in 3D

Es gibt 2 Modi:

Vorwärts-Modus:

Rückwärts-Modus:

Durch Optimierung des Rückwegs, d.h. durch entfernen überflüssiger reservierter Zellen kann die Anzahl der Schritte verringert werden.

DFS (Depth First Search)

Auch hier wird bei der Wahl der Richtungsreihenfolge nach der Linke-Hand-Regel verfahren. Die Reihenfolge ist im Prinzip egal, da DFS jede Zelle genau 2x besucht. D.h. die Reihenfolge der Aufrufe in der Prozedur ExploreCell ist beliebig.
ccw(dir) bedeutet Änderung der Richtung um 90° entgegen dem Uhrzeigersinn, ccw steht für counterclockwise. cw steht entsprechend für clockwise. Up und Down bezeichnen Konstanten für die Richtungen Oben und Unten.

Der Algorithmus arbeitet nach folgendem Prinzip:

procedure DFS(startcell, environment);

InitRobot();          // wähle dir so, dass in reverse(dir) eine Hindernis- oder Randzelle liegt
ExploreCell(dir);
end DFS;

procedure ExploreCell(dir);
if dir==Up oder dir==Down then
InitRobot();
ExploreStep(ccw(dir));
ExploreStep(dir);
ExploreStep(cw(dir));
ExploreStep(Up);
ExploreStep(Down);
end ExploreCell;

procedure ExploreStep(dir);
if existCell(dir) and unexplored(dir) then
move(dir);
ExploreCell(dir);
move(reverse(dir));
end ExploreStep;

Es wird zuerst eine Anfangsrichtung bestimmt und dann begonnen, das Gitter in dieser Richtung zu explorieren. ExploreCell versucht im Uhrzeigersinn (ausgehend von dir) die adjazenten, noch nicht besuchten Zellen über ExploreStep weiter zu explorieren. Ist die aktuelle Richtung oben oder unten, dann wird die Richtung mit InitRobot() neu bestimmt, da sonst die Funktionen ccw(dir) und cw(dir) nicht angewendet werden können. Die Bedingung, dass in reverse(dir) eine Hindernis- oder Randzelle liegt, kann dabei nicht immer eingehalten werden. Existiert eine Zelle in Richtung dir und ist diese noch nicht besucht, dann bewege den Roboter auf diese Zelle und exploriere die Zelle mit ExploreCell. Ist die Zelle vollständig exploriert, d.h. alle adjazenten Zellen sind schon besucht worden, dann gehe einen Schritt zurück. Mit anderen Worten gehe solange nach links bis es keine linke, adjazente und noch nicht besuchte Zelle mehr gibt, dann gehe falls möglich einen Schritt geradeaus. Ist jetzt auch geradeaus nicht möglich, dann gehe nach rechts. Ist rechts auch nicht möglich, dann bleiben noch oben und unten. Von der neu betretenen Zelle fange mit der Exploration wieder bei links an.

Autor: Christine Dienelt