More than fifty years ago, Bellman asked for the best escape path within a known forest but for an unknown starting position. This deterministic finite path is the shortest path that leads out of a given environment from any starting point. There are some worst case positions where the full path length is required. Up to now such a fixed ultimate optimal escape path for a known shape for any starting position is only known for some special convex shapes (i.e., circles, strips of a given width, fat convex bodies, some isosceles triangles). Therefore, we introduce a different, simple and intuitive escape path, the so-called certificate path. This escape path depends on the starting position s and takes the distances from s to the outer boundary of the environment into account. Due to the additional information, the certificate path always (for any position s) leaves the environment earlier than the ultimate escape path, in the above convex examples. Next we assume that fewer information is available. Neither the precise shape of the envir- onment, nor the location of the starting point is known. For a class of environments (convex shapes and shapes with kernel positions), we design an online strategy that always leaves the environment. We show that the path length for leaving the environment is always shorter than 3.318764 the length of the corresponding certificate path. We also give a lower bound of 3.313126, which shows that for the above class of environments the factor 3.318764 is (almost) tight.
We will see that our solution is a specific logarithmic spiral. In general, logarithmic spirals are natural candidates for optimal competitive search strategies, but in almost all cases the optimality remains a conjecture; see @cite_8 @cite_12 @cite_14 @cite_9 @cite_16 . In @cite_1 the optimality of spiral search was shown for searching a point in the plane with a radar. Many other conjectures are still open. For example Finch and Zhu @cite_9 considered the problem of searching for a line in the plane. .
@cite_14 @cite_8 @cite_9 @cite_1 @cite_16 @cite_12
1587220204 2019729116 1770419565 2038342425
When searching for a planar line, if given no further information, one should adopt a logarithmic spiral strategy (although unproven). In this paper we initiate a new area of study dealing with the best way to search a possibly unbounded region for an object. The model for our search algorithms is that we must pay costs proportional to the distance of the next probe position relative to our current position. This model is meant to give a realistic cost measure for a robot moving in the plane. We also examine the effect of decreasing the amount of a priori information given to search problems. Problems of this type are very simple analogues of non-trivial problems on searching an unbounded region, processing digitized images, and robot navigation. We show that for some simple search problems, knowing the general direction of the goal is much more informative than knowing the distance to the goal. Logarithmic spirals are conjectured to be optimal escape paths from a half plane ocean. Assuming this, we find the rate of increase for both min-max and min-mean interpretations of optimal''. For the one-dimensional analog, which we call logarithmic coils, our min-mean solution differs from a widely-cited published account. Searching for a point in the plane is a well-known search game problem introduced in the early eighties. The best known search strategy is given by a spiral and achieves a competitive ratio of 17.289 ... It was shown by Gal [14] that this strategy is the best strategy among all monotone and periodic strategies. Since then it was unknown whether the given strategy is optimal in general. This paper settles this old open fundamental search problem and shows that spiral search is indeed optimal. The given problem can be considered as the continuous version of the well-known m-ray search problem and also appears in several non-geometric applications and modifications. Therefore the optimality of spiral search is an important question considered by many researchers in the last decades. We answer the logarithmic spiral conjecture for the given problem. The lower bound construction might be helpful for similar settings, it also simplifies existing proofs on classical m-ray search.