Browsing by Author "Schuierer, Sven"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    The exact cost of exploring streets with a CAB
    (1998) Lopez-Ortiz, Alejandro; Schuierer, Sven
    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 points 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.
  • Thumbnail Image
    Item
    The ultimate strategy to search on m rays?
    (1998) Lopez-Ortiz, Alejandro; Schuierer, Sven
    We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1 + 2m[superscript m] / ( m - 1 )[superscript m-1]. We show that if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1 + 2m[superscript m]/(m -1)[superscript m-1] - 0(1/log[superscript 2] D) which is also optimal-but in a stricter sense. We construct a search strategy that achieves this ratio. Our strategy works equally as well for the unbounded case, and produces a strategy where the point is found at a competitive distance of 1 + 2m[superscript m] f(m -1)[superscript m-1] - 0(1/log[superscript 2] D), for unknown, unbounded D, that is, it is not necessary for our strategy to know an upper bound on the distance D in advance.