Geometry Lab: Exploringcubical environments

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 befindet sich unter http://web.informatik.uni-bonn.de/I/GeomLab/Gridrobot/.

Die Ziele dieser Arbeit sollten sein:

Eine Experimentierumgebung für die Erkundung gitterförmiger Umgebungen in 3D zu erstellen, dazu zählt ein Editor für dreidimensionale Umgebungen und die Simulation von Erkundungsstrategien. Als Vorlage diente dabei das Applet für den zweidimensionalen Fall.
Das Verhalten von vorhandenen Erkundungsstrategien im 3D zu untersuchen: wie weit lassen sich bekannte Strategien einfach auf den 3D Fall erweitern?

Es wurden bisher die Strategien Cell Explore und DFS umgesetzt.

Cell Explore in 3D

Es gibt 2 Modi:

Vorwärts-Modus:

Wie im 2-dimensionalen Fall wird das Gitter nach der Linke-Hand-Regel exploriert, d.h. bei jeder Zelle, die der Roboter betritt versucht er seinen Weg über eine adjazente, noch nicht besuchte und nicht reservierte Zelle fortzuseten, dabei bevorzugt er einen Schritt nach links vor einem Schritt nach geradeaus vor einem Schritt nach rechts vor einem Schritt nach oben vor einem Schritt nach unten.
Schritt nach links bedeutet eine Drehung des Roboters um 90° gegen den Uhrzeigersinn. Analog Schritt nach rechts, oben oder unten.
Alle noch nicht besuchten und nicht reservierten Zellen rechts des Pfades werden für den Rückweg reserviert (auf einem Stack). Bei Zellen, die oberhalb oder unterhalb des Pfades adjazente, noch nicht besuchte und nicht reservierte Zellen besitzen, werden Marker gesetzt und die aktuelle Zelle wird reserviert (evt. ist es nötig, weitere Zellen zu reservieren). Werden diese Zellen (für die die Marker gesetzt wurden) jetzt im Vorwärts-Modus besucht oder reserviert, dann werden die Marker gelöscht und die zugehörigen reservierten Zellen (sofern sie nicht sowieso reserviert worden wären) vom Stack entfernt.
Ist kein Schritt mehr im Vorwärts-Modus möglich wird der Rückwärts-Modus betreten.

Rückwärts-Modus:

Der Roboter geht über die auf dem Stack reservierten Zellen zurück.
Bei jeder Zelle wird geprüft, ob wieder in den Vorwärts-Modus gewechselt werden kann, d.h. ob die Zelle eine adjazente, noch nicht besuchte und nicht reservierte Zelle besitzt.

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.

Theoretical Background

With gridlike environment we mean a polygon, that consists of single cells. When the robot is located in a cell, he can recognize which of the adjacent cells belong to the polygon and which are obstacle cells, and then he can move to an adjacent cell of the polygon. The task of the robot is to visit every cell and in doing so to visit only a few cells several times.

For the 2-dimensional case there are already several strategies known which are theoretical and also experimental examined in detail. You will found an experimental environment in form of an applet under http://web.informatik.uni-bonn.de/I/GeomLab/Gridrobot/.

The aims of this work should be:

To develop an experimental environment for the exploration of gridlike environments in 3D, including an editor for 3-dimensional environments and the simulation of exploration strategies. The applet for the 2-dimensional case was used as a template.
To examine the behavior of existing exploration strategies in 3D: How far is it possible to transfer known strategies to the 3-dimensional case?

At the moment the strategies Cell Explore and DFS are implemented.

Cell Explore in 3D

There are two modes:

Forward mode:

Like in the 2-dimensional case the grid is explored after the Left-Hand-Rule, i.e. at every cell, the robot enters he tries to continue his path over an adjacent unvisited and unreserved cell, whereas he prefers a step to left over a step forward over a step to the right over a step up over a step down.
A step to the left means a turn of the robot of 90° counterclockwise. Analog turns for step to the right, up or down.
All unvisited and unreserved cells right to the path will be reserved (on a stack). At cells, which have adjacent unvisited and unreserved cells above or below the path, markers are set and the actuell cell is reserved (maybe more cells have to be reserved). Are this cells (for which the markers are set) now visited or reserved in forward mode, then the markers will be deleted and the belonging reserved cells will be removed from the stack (if they are not needed any longer).
No more forward step is possible then the robot changes to backward mode.

Backward mode:

The robot goes back over the reserved cells on the stack.
At every cell there is a tryout if it's possible to go back to the forward mode, i.e. to check if this cell has an adjacent unvisited and unreserved cell.

Optimizing the return path means deleting redundant reserved cells and so lessen the number of steps.

DFS (Depth First Search)

Here the order of the directions is managed by the Left-Hand-Rule, too. In principle the order don't mind, because DFS visits every cell exactly 2 times. That means the order of the calls in the routine ExploreCell is arbitrary.
ccw(dir) causes a change of the direction of 90° counterclockwise, cw a change of 90° clockwise. Up and Down denote constants for the corresponding directions.

The following code shows the principle of the algorithm:

procedure DFS(startcell, environment);

InitRobot(); // choose dir so that the cell in reverse(dir) is an obstacle or edge cell

ExploreCell(dir);

end DFS;

procedure ExploreCell(dir);

if dir==Up or 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;

First the starting direction is determined and then the algorithm starts to explorate the grid in this direction. ExploreCell tries to explorate counterclockwise (beginning with dir) the adjacent unvisited cells with ExploreStep. Is the actual direction up or down then a new direction is determinend by InitRobot, because otherwise the functions ccw(dir) and cw(dir) couldn't be applied. Thereby the condition that the cell in reverse(dir) is an obstacle or edge cell can't always be kept. Exists a cell in the direction dir which isn't yet visited, then move the robot on this cell and explorate the cell with ExploreCell. Is the cell completely explorated, i.e. all adjacent cells are already visited then step back. In other words take a step to the left until there is no more adjacent unvisited cell to the to left, in this case take a step forward. No step forward is possible, too, then take a step to the right. A step to the right isn't possible, too, then there are left the directions up and down. Start the further exploration on the new entered cell again with the left side.

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

	InitRobot(); // choose dir so that the cell in reverse(dir) is an obstacle or edge cell
	ExploreCell(dir);