New competitive strategies for searching in unknown star-shaped polygons

Abstract

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.