Sorry, this WWW browser does not seem to understand Java applets. 

An interactive Java applet by Christian Icking, Rolf Klein, Peter Köllner, Elmar Langetepe, supported by MWF/NRW and DFG grant Kl 655/8-2.
© 1997 Praktische Informatik VI, FernUniversität Hagen, © 2001 Institute of Computer Science, Dept. I, University of Bonn.

This applet demonstrates how to explore an initially unknown room with rectilinear walls on a path as short as possible.

Comments may be adressed to: javagroup@fernuni-hagen.de.

How to use the applet:

The applet brings up two windows:

The applet has three menus:

The  algorithm-modi work as follows:

The user-mode works as follows:

The presentation-mode works as follows:

Note that the mouse first has to be inside the 3-d window if you want to get control over the applet. If you have closed the applet please klick inside the "Exploring Rectilinear Rooms" rectangle to invoke the applet again.

The strategy:

Our model is as follows: The simple rectilinear room is modelled by a simple rectilinear polygon and the robot is described by a point in the two dimensional sphere. By definition a watchman route inside a simple polygon is a closed route that "sees" every point inside the polygon, i.e. the conjunction of all visibility polygons along the path should cover the whole polygon. So for a given startpoint our task is to find a watchman route inside a rectilinear polygon while "walking" through the polygon.

The strategy demonstrated here is a simple modification of the greedy online algorithm of Deng, Papadimitriou and Kameda published in their paper "How to learn an unknown environment: The rectilinear case". This strategy computes the shortest L_1-watchman route online.

At the starting point we choose a visible point on the border of the polygon and try to prolongue the already seen part of the border in a fixed direction (counterclockwise repectively clockwise). The strategy has to cross extensions (prolongations) of edges at reflex vertices in order to see more parts of the polygon. If the border line is not yet complete we just look where the border line becomes unvisible first and walk on a shortest path to the extension of an edge that causes the lack of sight. So we proceed until the whole border line is seen. Then we return to the start point on a shortest path.

The simple modification: Sometimes two already seen parts of the border are connected to a longer already seen first part if we just have explored the border line between the two parts. So the relevant first endpoint of the border jumps a bit and we have to walk on a shortest path to the next relevant extension behind the endpoint. This shortest path can be constructed online again. We just forget what we have seen so far and follow the border online to the next extension behind the endpoint. We only have to ensure that we stop the process if the whole border is seen.