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 tour |
Optimal tour |

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

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.

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

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.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(Theorem 1:The competitive complexity of exploring an unknown cellular environment with obstacles equals 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:

Fig. 1: Polygon that is to explore.

Fig. 2: Cellgraph.

Fig. 3: DFS with 30 steps.

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 2

*R*-2 steps and has to use another 2

*R*+2 steps to explore the whole environment. The optimal number of steps is 2

*R*+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 2

*R*+2

*P*steps and needs another 2

*R*+2

*P*steps. The optimal number of steps is 2

*R*+2

*P*.

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 LangetepeExploring an Unknown Cellular EnvironmentUnpublished Manuscript, FernUniversität Hagen, 2000. |