 |
[] []
|
|
Sirius
Simulation of robots
in
unknown streets
Introduction
Sirius - Simulation of robots in unknown
streets
- is an application to simulate a robot that is searching for a target
inside a special type of polygons called streets. This page provides an overview
about robots and the kind of strategies implemented.
The Main Page will give you more information on how to use the application.
The Street Page will give you more information on the definition of streets.
What do the robots do
The task the robots have to accomplish is finding a target in an unknown environment. The
robots have a kind of 360 Degree visual sensor, so that they
can "see" their environment. The robots don't have a map of their environment, nor do they
know the coordinates of their target.
Some mathematical background
The environment is simulated by a polygon on the plane, and the robot is simulated is a point.
The target point is a marked point inside the polygon. The length of the tour the robots takes
from start point to target point is compared to the shortest tour a user with a map of the
environment can take. The strategy the robot uses is said to be "c-competitiv" if there is a
constant c, so that for every environment the tour the robot takes is less than c times as
long as the shortest possible tour. It can be shown, that for any robot you can always construct
an environment so that the robot can not be c-competitiv. Therefore we have to make special
restrictions to the kind of environment we present to the robots. This leads to the definition of
"streets". These will be discussed in detail on the Streets Page. It can be shown that
within streets c-competitive strategies can be found. The robots we present are all competitive
to different factors c. One can also show that the best factor that can be achived within street
is the square root of 2, which is about 1.41. One of the robots is proved to be competitive to
that factor and thus uses an optimal strategy.
What strategies do the robots use
We simulate five different strategies within our application. Within this help text we can only give
a brief idea of the way these strategies work. More detailed descriptions can be found in the original
papers that we will name within the description.
All of the used strategies have one thing in common. They choose their way using a simple high level,
as long as there is only one way to go. But whenever they get to a situation in which the target can be
behind two different corners, they will switch to a low level strategy. Each robot uses it's unique
low level strategy.
(1) Klein algorithm
This is the first algorithm to be proofed to be c-competive. It was designed by Prof. Dr. Rolf Klein
at the FernUniversitaet Hagen.
The original paper calculates the competitivity factor c to about 5.72. This has a
been recalculated by Lopez-Ortez and Schuierer to a factor of 1+PI, which is about 4.14.
Experimental use of the strategy has never exceeded a factor of about 1.8. Try to find a street with a
worse competitive factor for the Klein strategy using our application.
Klein's strategy tries to equalize the absolute detour the robot has to take for both corners the target
could be situated behind.
(2) Kleinberg algorithm
Jon M. Kleinberg has invented a strategy that he has proofed to have a competitive factor c of about 2.61.
An environment can be constructed with this application that has a detour of nearly this factor.
This strategy tries to walk in a direction so that with every move the robot will get closer to both corners.
(3) Ellipse algorithm
This strategy has been invented by the authors of this application. It has not yet been proofed to have a
competitive factor, but we suppose it will also hold the optimal factor of sqare root of 2.
The idea is to choose a way such that the tour stayes inside the boundary given by two ellipses formed around the robot and the two
corners. The distance from one focal point of the ellipse - the robot location - to a point on the edge of the ellipse
then continuing to the other focal point - the corner - is the same for all points on the edge of the ellipse.
The robot starts to walk to the point where the line between the two corners intersects the ellipse of the corner
nearest to the robot. It keeps track of how much of the detour it has used up, and recalculates the ellipses
accordingly. Using this strategy, we try to guarantee that the robot can never use more than the optimal detour and
thus will be optimally competitiv.
The Ellipse robot has additional options that can be set using the robot/options menu entry. A dialog will be displayed showing
a textbox and a slider. Either textbox or slider can be used to adjust the value between 0.0 and 1.0. The specified value
determines the point on the horizon the robot will walk to.
A value of 0.0 will let the robot walk to the intesection of the ellipse of the nearer cavemouth with the horizon, whereas a value of 1.0
lets the robot walk to the intersection of the ellipse of the cavemouth farther away. A value between 0 and 1 will move to a point between those
two extrema.
(4) Worst Case Aware algorithm
Elmar Langetepe has invented an algorithm that can be proofed to hold a competitive factor of square root of 2. This
algorithm solves the problem by walking along a curved path that will always hold the minimum necessary detour at any given
angle between the corners as seen from the robots position. Langetepe has shown that the minimum necessary detour for any triangle
that is defined by the robots position and the two corners is the square root of (1 + sin(phi)) where phi is the angle at the robots location.
The robot will choose a path that keeps this detour on both sides. Thus the robot can actually have a detour smaller than sqrt(2) if the
street has only triangles with more than PI/2 opening angle at the robot position.
(5) Constant relative detour algorithm
For experimental purposes we have also included a robot using the constant relativ detour algorithm. This algorithms tries to equalize the relative
detour on both sides. The robot has been invented by Prof. Dr. Rolf Klein, but has not yet been proofed to hold any competitive factor.
