On-line target searching in bounded and unbounded domains
Prabhakar L. Ragde, Alejandro López-Ortíz · 1996
In this work we study the problem of a robot searching for a target on bounded and unbounded domains, specifically in one and two dimensions. We present some relevant results in the field and within this framework, the contributions of this work. We show that one-sided searches on the real line have an average competitive ratio of 9 and we apply this result for the case of known destination searches on $\cal{G}$-street polygons. For this class of polygons we also show that the best known upper bound of $\sqrt{82}$ is indeed optimal for the case of unknown destination searches. For orthogonal street polygons we prove that knowing the location of the destination does not reduce the competitive ratio. We present the first robust algorithm for searches inside street polygons under navigational errors, as well as for other important classes of impaired robots such as robots lacking triangulation and depth measurement mechanisms. In particular, we propose a ($\pi+1$)-competitive strategy which is robust under navigational error, and equally efficient for oblivious robots. We also present an 1.92-competitive strategy which does not require depth perception from the robot. We also give the best-known strategy for searching inside street polygons, at a competitive ratio of 1.76. This significantly improves over the best previously known ratio of 2.8. We give the first non-trivial lower bound for searching and walking into the kernel of a polygon. We provide upper and lower bounds for searching for a target inside street polygons. These results are the first constant competitive ratio strategies inside a class of polygons which is independent of the location of the start and target points. We also prove negative results regarding the optimality of several well-known family of strategies for searching inside simple polygons. In particular we show that Kleinherg's strategy is 2.6-competitive, and that continuous bisector, which is in many respects a good strategy, is at least 1.68-competitive. Lastly we show that any strategy which does not respond to the absence of new extreme points has a competitive ratio strictly larger than $\sqrt{2}$.