Search Target In Polygon

To reopen the STIP windows push:

(If you see no button here, your browser does not completely support JAVA 1.1.
In this case either enable it or try this URL again with the appletviewer from the JDK1.1.x for your Operating System.)

What is STIP ?

STIP is the abbreviation of "Search Target In a Polygon" and is the simulation of a robot who uses his visual system to find an unknown target in an unknown room with a polygonal ground plan and insurmountable walls. STIP allows a broad variety of human interaction, ranging from pure calculation of several values up to competing with the robot in a 3D-environment.

STIP was entirely written in JAVA 1.1 by Nicole Heckenkemper as a "Diplomarbeit" for the "Lehrgebiet Praktische Informatik VI" at the "FernUniversität Hagen" and it's main purposes are the visualisation and teaching of the course "Algorithmische Geometrie" and the realization of an experimental environment for this problem.

STIP has numerous parameters which can be optimized to fit the users needs.


Usage


Contents

Since STIP has three major windows with different intentions, here will follow a short description of them. The three windows are: You can click here on any of the listed features to jump there directly:

Robot Window

Mouse usage

Description of the Menubar of the Robot window

File-Menu

Back to the Contents.

Show-Menu

Back to the Contents.

User Mode-Menu

Back to the Contents.

Options-Menu

Back to the Contents.

Help-Menu

Back to the Contents.

Statusline

Back to the Contents.

Errors, as well as other status messages are displayed in the statusline below the menubar.

Resultline

Back to the Contents.

The following fields are displayed in the resultline below the statusline:

Canvas

Back to the Contents.

In the canvas, below the resultline can be displayed:

Description of the Buttons

Back to the Contents. Hint
The TS, SPT and the shortest path can only be displayed when they have been computed already and are valid.
They can easily be invalidated by moving any point.

Human Window and 3D Window

Try for yourself to find the target!

Mouse usage

Back to the Contents.

Navigation in the 3D Window

Back to the Contents.

Alternatively you can navigate with the following keys (3D Window):

   UP arrow key => go ahead
 DOWN arrow key => go backwards
 LEFT arrow key => turn left
RIGHT arrow key => turn right
The 3D Window shows the user a virtual sight through the polygon from the place where the robot currently is, in the direction the robot currently moves.
In the beginning the view is from the startpoint "up" in the 2D-canvas.

When the user selects with the mouse a new point where the robot shall go to, and the selected direction lies in a very different direction than the one before, the sight in the 3D Window will slowly turn around and when the new angle is reached, the robot will start on its way.

The "sky" in the robot window is blue and the "ground" is olive. The polygonsegments are grey "walls". Walls which are closer to the robot will appear brighter.

The search can not be paused (no need for that) in this window, only aborted.


Description of the Menubar of the Human Window:

Options-Menu

Back to the Contents.

Help-Menu

Back to the Contents.

Statusline and Resultline in the Human Window:

Back to the Contents.

The statusline and the resultline are the same as in the Robot Window

Please read the explanations there.


Canvas in the Human Window:

Back to the Contents.

The canvas in the Human Window is mostly the same as in the Robot Window, but has some exceptions:

For a more common explanation of the parts of the canvas of the Human Window click here.

Description of the Buttons

Back to the Contents.
Back to the Contents.

Theoretical Background for STIP


Problemdescription

A robot starts at the point "s" in an unknown room with a ground plan in the shape of a simple polygon"P". The room has no exit and the walls are insurmountable. There are no obstacles in the room. The room does not change it's shape.

The robots task consists of reaching the targetpoint "t" in the shortest possible way , without leaving the polygon and without knowing where the target is placed.

The robot can move freely within the polygonal shaped room.

Since the walls are insurmountable, the problem can be reduced in the simulation to two dimensions.

The robot uses a visual system, which allows him to use the visibility polygon "vis(p)" for the further calculation of his path, in every place "p" within the polygon.

Using this visual system, the robot is able to construct a partial map, in which all parts of the polygon "P", which are or were ever seen, are included.

The target "t" is marked and will be recognized by the robot as soon as it is contained in the visibility polygon.

As soon as the robot "sees" the target, he walks towards it, on the direct way.



Pathlength Factor

Due to the lack of information about the polygon, it is inevitable for the robot to take detours. The quality of the implemented search algorithm can be measured via the pathlength factor.

The pathlength factor is the factor with which the length of the shortest path from the startpoint to the targetpoint has to be multiplied, to reach the length of the way the robot took through the polygon, in order to reach the target.

For the solution of this task are especially strategies of interest, which are able to solve the problem within an predictable limit. Such strategies are usually called "competitive". The limit is usually called the competitive factor.

The following graph shows, that it is impossible to have a problem-solving strategy for the above mentioned problem for which the limit is a constant. The limit depends at least linear on the amount "n" of corners in the polygon.

Diagram of a polygon
Diagram 1

The diagram above shows a polygon with "n" corners, which consists of "n/4" passages. The startpoint "s" lies precisely in the center of the polygon. The target "t" lies at the end of one of the passages and is initially not visible from the startpoint. The robot has to walk through all the passages and has to look behind every corner. In the worst case the robot will find the target behind the last corner.

Assuming the passages have a length of "1" and their width, as well as the size of the ankled ends are neglectable small, we will reach an overall length for the way of the robot, of:

(n/4 - 1) * 2 + 1 = n/2 - 1

The shortest possible path for the polygon above has a length of "1".



The base algorithm

The Shortest Path Tree "SPT" contains the shortest paths to all corners from "s".

The robot knows during his search not the complete tree "SPT", but the shortest paths to all corners he has already seen.

The paths to the known corners are stored in a cyclic list "L" and are cyclic visited with an increasing pathlength.
The pathlength is doubled every time the robot has visited the last corner he can reach with his current pathlength for the current cycle.

New discovered corners are immediately included into the list "L" and if the pathlength is long enough to reach this corner, the robot will go for it in the same round.

The robot will continue, until he finds the target.

This description of the basic algorithm is only very ridgid and can be thoroughly studied in either the script of the course "Algorithmische Geometrie" of the "Fernuniversität Hagen", or in the book "Algorithmische Geometrie", Addison-Wesley, Bonn, 1997 by Prof. Dr. Rolf Klein.



In STIP implemented improvements to the base algorithm

The following improvements are integrated into STIP:


Autor: © 1997 Praktische Informatik VI, FernUniversität Hagen, © 2001 Institute of Computer Science, Dept. I, University of Bonn, Nicole Wengatz (