Abstract
We consider the problem of a robot traversing an unknown polygon with the aid of standard visibility. The robot has to find a path from a starting point s to a target point g. We provide upper and lower bounds on the ratio of the distance traveled by the robot in comparison to the length of a shortest path. Since this ratio is unbounded for general polygons, we restrict ourselves to the well investigated class of polygons called streets. A street is a polygon where s and t are located on the polygon boundary and the part of the polygon boundary from s to g is weakly visible to the part from g to s and vice versa.
We consider two problems in this context. First we assume that the location of the target g is known to the robot. We prove a lower bound of sqrt(2) on the competitive ratio of any deterministic algorithm that solves this problem. This bound matches the competitive ratio for searches in a rectilinear polygon with an unknown target which implies that, for rectilinear streets, knowledge of the location of the destination provides no advantage for the robot. In addition, we also obtain a lower bound of 9 for the competitive ratio of searching in generalized streets with known target which closely matches the upper bound if the target is unknown.
Secondly, we consider a new strategy for searching in an arbitrarily oriented street where the location of g is unknown. We show that our strategy achieves a competitive ratio of sqrt(1+(1+π/4)
2) =~ 2.05 which significantly improves the best previously known ratio of 2 sqrt(1 +1/sqrt(2)) =~ 2.61.
Bibtex Entry
