We consider searching problems in robotics that a robot has to find a path to a target by traveling in an unknown star shaped polygon P. The goal is to minimize the ratio of the distance traveled by the robot to the length of the shortest start-to-target path. Let s be a starting point in p. We first present a competitive strategy to find a path from s to the closest kernel point k of P. The length of the path that the robot generates is less than 1+2 square root 2 (<3.829) times the distance from s to k, which improves the best previous bound 5.331 (C. Icking and R. Klein, 1995). Second, given a specified target t in P, we present a competitive strategy to find a path from s to t whose length does not exceed 17 times the length of the shortest s-t path.
New competitive strategies for searching in unknown star-shaped polygons
1997
3 Seiten, 9 Quellen
Conference paper
English
On the Geometry of Spatial Polygons and Screw Polygons
Online Contents | 1997
|Star-Configuration Searching for Satellite Attitude Computation
Online Contents | 1995
|Eigenvalues of the Laplacian on regular polygons and polygons resulting from their disection
Online Contents | 1999
|Active Polygons for Object Tracking
British Library Conference Proceedings | 2002
|