Tizian.cs.uni-bonn.de

Optimal Competitive Online Ray Search with an
Tom Kamphans and Elmar Langetepe University of Bonn, Institute of Computer Science I omerstraße 164, 53117 Bonn, Germany Abstract. We consider the problem of finding a door along a wall with
a blind robot that neither knows the distance to the door nor the direc-
tion towards of the door. This problem can be solved with the well-
known doubling strategy yielding an optimal competitive factor of 9
with the assumption that the robot does not make any errors during
its movements. We study the case that the robot's movement is erro-
neous. In this case the doubling strategy is no longer optimal. We present
optimal competitive strategies that take the error assumption into ac-
count.
Keywords: Online algorithms, motion planning, ray search, errors.
Motion planning in unknown environments is theoretically well-understood andalso practically solved in many settings. During the last decade many differentobjectives where discussed under several robot models. For a general overviewon online motion planning problems see e. g. Theoretical correctness results and performance guarantees often suffer from idealistic assumptions so that in the worst case a correct implementation is im-possible. On the other hand, practioners analyze correctness and performancemainly statistically or empirically. Therefore it is useful to investigate, how the-oretic online algorithms with idealistic assumptions behave if those assumptionscannot be fulfilled. Can we incorporate assumptions of errors in sensors andmotion into the analysis? The task of finding a point on a line by a blind agent without knowing the location of the goal was considered by Gal and independently reconsideredby Baeza-Yates et al. Both introduced the so-called doubling strategy, whichis a basic paradigma for searching algorithms, e. g., approximating the optimalsearch path, see Searching on the line was generalized to searching on mconcurrent rays, see .
In this paper we investigate how an error in the movement influences the correctness and the corresponding competitive factor of a strategy. The errorrange, denoted by a parameter δ, may be known or unknown to the strategy.
S.E. Nikoletseas (Ed.): WEA 2005, LNCS 3503, pp. 2005.

Springer-Verlag Berlin Heidelberg 2005 T. Kamphans and E. Langetepe Due to space limitations, we give only brief sketches of the proofs and refer theinterested reader to where we also consider a second error model.
The Standard Problem and the Error Model
The task is to find a point, t, on a line. Both the distance from the start position s to t, as well as the position of t (left hand or right hand to s) is unknown. Astrategy can be described by a sequence F = (fi)i∈IN. fi denotes the distance therobot walks in the i-th iteration. If i is even (odd), the robot moves fi steps fromthe start to the right (left) and fi steps back. It is assumed that the movementis correct, so after moving fi steps away from the start point and fi towards s,the robot has reached s. This does not hold if there are errors in the movement.
In this case, every movement may be erroneous, which causes the robot to movemore or less far than expected. We require that the robots error per unit iswithin a certain error bound, δ. Let f denote the length of a movement requiredby the strategy then we require that the robot moves at least (1 − δ)f and atmost (1 + δ)f for δ ∈ [0, 1[.
Finding a Point on a Line
First, we assume that the robot is not aware of making any errors. Thus, theoptimal 9-competitive doubling strategy fi = 2i seems to be the best choicefor the robot. Let + (−) be the covered distance to the right (left) in the i-th step. Now, the drift from s, ∆ k, is ∆k = (− − +).
Theorem 1. The robot will find the door with the doubling strategy fi = 2i,
if the error δ is not greater than 1 . The generated path is never longer than
8 1+δ + 1 times the shortest path to the door. Proof sketch. We assume that the goal is found on the right side. For the com-petitivity it is the worst, if the door is hit in step 2j +2, but located just a littlebit further away than the rightmost point reached in step 2j.
We get the worst case ratio 1 = 2 (1 + δ) 1 = 2 (1 − δ) 2 = 4 (1 − δ) i )+ε This maximizes for ∓ = (1 ± δ)2i, and 2 = 4 (1 + δ) 8 (1 + δ) we get πonl < 1 + 8 1+δ . We have to require δ ≤ 1 , otherwise the distance (1−3δ) 22j +4δ from s may not exceedthe point 4δ .
One might wonder if there is a strategy which takes the error δ into account and yields a smaller factor. Intuitively this seems to be impossible, but we areable to show that there is such a strategy.
Optimal Competitive Online Ray Search with an Error-Prone Robot Theorem 2. In the presence of an error up to δ there is a strategy that meets
every goal and achieves a competitive factor of 1 + 8 1+δ Proof sketch. We design a strategy, F = (fi)i∈IN. From (*) we conclude that it
n+1 fi is sufficient to minimize G (n,δ)(F ) := , which is achieved by the strategy fi = 2 1+δ . This strategy is reasonable since it monotonically increases the distance to s, and we reach every goal.
This factor is optimal. We can show that for every δ there is a strategy, F ∗, that achieves the optimal factor Cδ exactly in every step, and describe F ∗ by arecurrence. Finally, the condition fi > 0 leads to a lower bound for Cδ. Thus: Theorem 3. In the presence of an error up to δ ∈ [0, 1[, there is no competitive
strategy that yields a factor smaller than 1 + 8 1+δ Error-Prone Searching on m Rays
The robot is located at the common endpoint of m infinite rays, knowing neitherthe location—the ray containing t— nor the distance to t. Gal showed thatw.l.o.g. one can use a periodic and monotone strategy, i. e., fi and fi+m visitthe same ray, and fi < fi+m holds. In the error-prone setting, the start point ofevery iteration cannot drift away, since the start point is the only point whereall rays meet.
Theorem 4. Searching for a target located on one of m rays with an error-prone
robot using a monotone and periodic strategy is competitive with an optimal
factor of 3 + 2 1+δ for δ < e−1 . (m−1)m−1 − 1 Proof sketch. It turns out that we consider the functionals G k(F ) := in this case, which are identical to the functionals considered in the error-freem-ray search. Thus, fi = (m/m − 1)i minimizes Gk(F ), see Ensuringmonotony leads to the condition δ < e−1 .
We have analyzed the standard doubling strategy in the presence of errors inmovements. The robot still reaches the goal for δ ≤ 1 with a competitive ratio of 8 1+δ + 1. If δ is known to the strategy f is optimal with a competitive factor of 1 + 8 1+δ . In the case of m rays f i = (m/m − 1)i yields 3 + 2 1+δ for δ ≤ e−1 ≈ 0.46.
(m−1)m−1 − 1 T. Kamphans and E. Langetepe 1. S. Alpern and S. Gal. The Theory of Search Games and Rendezvous. Kluwer Academic Publications, 2003.
2. R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Inform. Comput., 106:234–252, 1993.
3. P. Berman. On-line searching and navigation. In A. Fiat and G. Woeginger, editors, Competitive Analysis of Algorithms. Springer-Verlag, 1998.
4. E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost. Submitted to Theor. Comput. Sci.
5. R. Fleischer, T. Kamphans, R. Klein, E. Langetepe, and G. Trippen. Competitive online approximation of the optimal search ratio. In Proc. 12th Annu. EuropeanSympos. Algorithms, volume 3221 of Lecture Notes Comput. Sci., pages 335–346,Heidelberg, 2004. Springer-Verlag.
6. S. Gal. Search Games, volume 149 of Mathematics in Science and Engeneering.
Academic Press, New York, 1980.
7. M. Hammar, B. J. Nilsson, and S. Schuierer. Parallel searching on m rays. Comput. Geom. Theory Appl., 18:125–139, 2001.
8. C. Hipke, C. Icking, R. Klein, and E. Langetepe. How to find a point on a line within a fixed distance. Discrete Appl. Math., 93:67–73, 1999.
9. C. Icking, T. Kamphans, R. Klein, and E. Langetepe. On the competitive complex- ity of navigation tasks. In H. Bunke, H. I. Christensen, G. D. Hager, and R. Klein,editors, Sensor Based Intelligent Robots, volume 2238 of Lecture Notes Comput.
Sci., pages 245–258, Berlin, 2002. Springer.
10. T. Kamphans. Models and Algorithms for Online Exploration and Search. PhD thesis, University of Bonn, to appear.
11. T. Kamphans and E. Langetepe.
Optimal competitive online ray search with an error-prone robot.
Technical Report 003, University of Bonn, 2005.
12. M.-Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inform. Comput.,133(1):63–79, 1996.
13. E. Langetepe. Design and Analysis of Strategies for Autonomous Systems in Mo- PhD thesis, Department of Computer Science, FernUniversit¨ Hagen, 2000.
opez-Ortiz and S. Schuierer. The ultimate strategy to search on m rays? Theor. Comput. Sci., 261(2):267–295, 2001.
15. J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R.
Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633–701.
Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
16. C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. Theoret. Comput. Sci., 84(1):127–150, 1991.
17. N. S. V. Rao, S. Kareti, W. Shi, and S. S. Iyengar. Robot navigation in un- known terrains: introductory survey of non-heuristic algorithms. Technical ReportORNL/TM-12410, Oak Ridge National Laboratory, 1993.

Source: http://tizian.cs.uni-bonn.de/publications/kl-ocolr-05.pdf