New competitive strategies for searching in unknown star-shaped polygons
Jaeha Lee, Chan-Su Shin, Jae‐Hoon Kim, Sung Yong Shin, Kyung‐Yong Chwa · 1997
We consider searching problems in robotics that a robot has to find a path to a target by traveling in an unknown starshaped 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 + 2W (< 3.829) times the distance from s to k, which improves the best previous bound 5. 331 [3].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.