The Exact Cost of Exploring Streets with CAB

摘要

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 . A street is a simple polygon where s and t are located on the polygon boundary and the part of the polygon boundary from s to t is weakly visible to the part from t to s and vice versa. We are interested in the ratio of the length of the path traveled by the robot to the length of the shortest path from s to t which is called the competitive ratio of the strategy. In this work 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 ~ 1.6837 in the worst case.