The basic tasks for autonomous mobile robots include lawn mowing, vaccuum cleaning, searching for objects and exploring unknown environments. For this tasks, we investigate methodical backgrounds for efficient strategies

The applet shown here allows the simulation of different strategies for exploring unknown environments.

The figures below show two examples for exploring an environment: the left shows an online exploration tour, the left shows one of the optimal solutions.

Online berechnet

Online tour

Optimale Tour

Optimal tour

[ Die Simulationsumgebung ] [ Theoretische Hintergründe ]

Simulationsumgebung

The applet allows the examination of several different strategies for exploring arbitrary, user defined polygons. A polygon consists of single cells and contains a selected cell-the start cell-at which the robot starts its exporation tour and to which the robot returns as soon as the whole polygon is explored.

example Fig. 1: A cellular environment (example)

The robot does not know anything about its surrounding in advance. It is equipped with tactile sensors that allow the robot to recognize, which of its adjacent cells are obstacles ("holes") and to which he is allowed to move to. Standing at the startcell in the polygon from fig. 1, the robot (red square) detects two obstacle walls and two free cells (light gray), see fig. 2. But he can draw a map of its environment; the robot is allowed to remember, which cells adjacent to his walked path are obstacles, which are free cells and other information needed to plan his tour, e.g. it can reserve some cells for its return path, see fig. 3.

startcell Fig. 2: "View" of the robot from start cell

some steps Fig. 3: The robot (red) has explored some cells (green) and some cells marked (dark gray)

There are several strategies to explore cellular environments implemented. The user can also move the robot manually and select between different views (whole polygon, explored polygon only). The animation in fig. 4 shows the exploration of the polygon from fig. 1 using the strategy CellExplore.

  Fig. 4: Exploring a polygon using CellExplore

Further, the applet provides some counter strategies, that are used to proof lower bound for the exploration problem.

Theory

Our goal is to find a tour, that is as short as possible, i.e. the number of steps the robots has to make should be as small as possible. As a measure for the quality of the strategy we consider the competitive factor c, i.e. the quotient between the length of our online tour and the length of the optimal tour.

Upper bound

The first question is if the robot is still able to approximate the optimum solution up to a constant factor if it does not know the environment. Surprisingly, there is a quick and rather simple answer.
Theorem 1: The competitive complexity of exploring an unknown cellular environment with obstacles equals 2.
The robot achieves this ratio with a simple depth-first search in the cellgraph of the environment. The cellgraph is a graph, that contains one node per cell and edges between adjacent cells. DFS needs 2(C-1) steps, where C is the number of cells: except for the startcell, it uses one step to enter a cell for the first time and one step the cell for the last time. On the other hand, an optimal strategy needs at least C steps to visit the whole environment. For Example:

Zu erkundendes Polygon  Fig. 1: Polygon that is to explore.

Zellgraph des Polygones  Fig. 2: Cellgraph.

DFS Erkundung  Fig. 3: DFS with 30 steps.

Optimale Erkundung  Fig. 4: optimal tour.

Lower Bound

Theorem 2: The lower bound for the exploration problem is 2

Let's the robot start in a long corridor:

Case 1

The robot explores parts left and right to the startcell and returns periodically to the start:

Now, we close the corridor with one unexplored cell on every side of the corridor:

The robot used already 2R-2 steps and has to use another 2R+2 steps to explore the whole environment. The optimal number of steps is 2R+2.

Case 2

The robot does not return to the startcell periodically, but concentrates more or less on one end of the corridor:

Now, we add a fork to the corridor. The two alternatives turn back and run parallel to the first corridor:

If the robots returns to the startcell, we argue as in case 1. If the robot concentrates more or less on one of the new branches, we connect this branch to the corridor that contains the startcell. We close the other branch with one unexplored cell:

The robot has used 2R+2P steps and needs another 2R+2P steps. The optimal number of steps is 2R+2P.

Bibliography:

[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.