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: firstname.lastname@example.org.
How to use the applet:
The applet brings up two windows:
- in the main window the "room" is (perhabs partially) shown from above
- in the sub window there is a subjective view of a part of the polygon (this part is also colored in the main window)
- the extension of the subjectively seen part depends on the width of the sub window
The applet has three menus:
- two polygon-examples are available in the examples menu
- three algorithm-modi, one user- and one presentation-mode are available in the modus menu
- the applet may be closed in the file menu
The algorithm-modi work as follows:
- to start an algorith-mode klick inside the 3-D window
- the algorithm chooses the start point on the border in the south direction
- Algorithm computes the startegy in event steps and in 3-D sight (each step is invoked by a single mouse klick in the 3-D window)
- CompleteAlgorithm shows the complete path generated by the strategy
- DemoAlgorithm demonstrates the whole strategy using 3-D sight
The user-mode works as follows:
- to get control, fix the left mouse button inside the 3-D window
- the speed of the robot is increased/decreased if you turn the mouse up/down now
- the robot moves left/right if you turn the mouse to the left/right now
- while walking the partial map and the subjective view are shown
The presentation-mode works as follows:
- the robot's start position is fixed and the robot looks around
- the robot follows the border of the room, a naive strategy for exploration
- the robot uses the more intelligent strategy, the corresponding route is shorter
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.
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.