The Exact Cost of Exploring Streets with a CAB Strategy
[.ps]
[.pdf]
Abstract
A fundamental problem in robotics is to compute a path for a robot from its current location to a given target. In this paper we consider the problem of a robot equipped with an on-board vision system searching for a target t in an unknown environment. We assume that the robot is located at a point s in a polygon that belongs to the well investigated class of polygons called streets. In this paper we present the first exact analysis of the continuous angular bisector CAB strategy, which has been considered several times before, and show that it has a competitive ratio of approx 1.6837 in the worst case.
Bibtex Entry
