The Exact Cost of Exploring Streets with a CAB. A.
López-Ortiz and S. Schuierer. Proceedings of 10th Canadian
Conference on Computational Geometry, 1998. PostScript
file.
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.