## 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 diﬀerentobjectives where discussed under several robot models. For a general overviewon online motion planning problems see e. g.
Theoretical correctness results and performance guarantees often suﬀer 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 fulﬁlled. Can we incorporate assumptions of errors in sensors andmotion into the analysis?
The task of ﬁnding 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

*m*concurrent rays, see .

In this paper we investigate how an error in the movement inﬂuences 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 ﬁnd 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 *= 2

*i *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 *= 2

*i,*

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 2

*j *+2, but located just a littlebit further away than the rightmost point reached in step 2

*j*.

We get the worst case ratio
1 = 2 (1 +

*δ*)
1 = 2 (1

*− δ*)
2 = 4 (1

*− δ*)

*i *)+

*ε*
This maximizes for

*∓ *= (1

*± δ*)2

*i*, and
2 = 4 (1 +

*δ*)
8 (1 +

*δ*)
we get

* π*onl

* < *1 + 8 1+

*δ *. We have to
require

*δ ≤ *1 , otherwise the distance
(1

*−*3

*δ*) 22

*j *+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 suﬃcient 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 *inﬁnite 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-free

*m*-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

RIASSUNTO DELLE CARATTERISTICHE DEL PRODOTTO 1. DENOMINAZIONE DEL MEDICINALE "nome del medicinale" 150 mg compresse / capsule rigide "nome del medicinale" 300 mg compresse 2. COMPOSIZIONE QUALITATIVA E QUANTITATIVA Una compressa / capsula contiene: principio attivo: litio carbonato 150 / 300 mg Per l'elenco completo degli eccipienti, vedere 6.1. 3. FORMA FARMACEUTICA Compresse / Capsule rigide

The ownership of U.S. industrial forestlands has dramatically changed since the 1980s. Whereas forest product companies had been the dominant owner of such lands and sent that timber to their mills, now the lands are owned by investment management organizations and trusts that manage the land to maximize returns. Some of these organizations, however, are delivering returns and helping to conserve the land.