Finding a doo along a wall wi h an e o a lic ed obo
Tom Kamphans aand Elma Lange epe a
aUni e si y o Bonn
Ins i u e o Compu e Science I
R¨ome s aße 164
53117 Bonn
Ge many
h p://web.in o ma ik.uni-bonn.de/I/agklein.h ml
Abs ac
We conside he p oblem o inding a doo in a wall wi h a blind obo , ha does no know he dis ance o he
doo o whe he he doo is loca ed le hand o igh hand o i s s a poin . This p oblem can be sol ed wi h
he well-known doubling s a egy yielding an op imal compe i i e ac o o 9 wi h he assump ion, ha he obo
does no make any e o s du ing i s mo emen s. We s udy he case, ha he obo s mo emen is e o neous. We
gi e uppe bounds o he mo emen e o , such ha eaching he doo is gua an eed. Mo e p ecisely he e o
ange δhas o be smalle han 1
3. Addi ionally, he co esponding compe i i e ac o is gi en by 1 + 8 1+δ
1−3δ.
Keywo ds: Online algo i hm, Online mo ion planning, sea ching, compe i i e a io, e o s.
1. In oduc ion
Online mo ion planning in unknown en i on-
men s is heo e ically well-unde s ood and p ac-
ically sol ed in many se ings. Du ing he las
decade many di e en objec i es whe e discussed
unde se e al obo models. Fo a gene al o e iew
o heo e ical online mo ion planning p oblems and
i s analysis see he su eys [3,9,10,7].
Theo e ical co ec ness esul s and pe o mance
gua an ees o en su e om idealis ic assump-
ions, he e o e in he wo s case a co ec im-
plemen a ion is impossible. On he o he hand
p ac ione s analyze co ec ness esul s and pe o -
mance gua an ees mainly s a is ically. The e o e
i is use ul o in es iga e, how online algo i hms
wi h idealis ic assump ions beha e, i hose as-
sump ions canno be ul illed. Mo e p ecisely, can
we inco po a e assump ions o e o s in senso s
and mo ion di ec ly in o he heo e ical analysis?
We al eady success ully conside ed he beha iou
o he well-known pledge algo i hm, see Abelson
Email add esses: [email protected] (Tom
Kamphans), lange [email protected] (Elma
Lange epe).
and diSessa [1] and Hemme ling [6], in he p es-
ence o e o s [8].
The ask o inding a poin on a line wi hou
knowing he di ec ion o he dis ance o he s a
poin was conside ed by Baeza-Ya es e . al. [2] and
independen ly by Gal [5] and lead o he so called
doubling s a egy, which gi es a basic pa adigma
o o he sea ching algo i hms, i.e., sea ching o
a poin on m ays o app oxima ing he op imal
sea ch pa h, see [4].
Unde he compe i i e amewo k doubling wi h
a ac o o wo is he op imal s a egy o sea ch-
ing a poin on he line. The compe i i e analysis
compa es he cos o he s a egy wi h he cos o a
solu ion which is compu ed unde ull in o ma ion,
see [2].
In his pape we in es iga e how he doubling
s a egy beha es in he p esence o e o s and how
he e o in luences he co ec ness and he co e-
sponding compe i i e ac o o he s a egy.
We assume ha an e o ange o a single s ep
is known in ad ance bu he agen ge s no u he
in o ma ion abou he cummula ed e o . The e-
o e o he agen i makes no sense no o use he
doubling heu is ic.
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
2. The los cow p oblem
The ask is o ind a doo in a wall, espec i ely
a poin , , on a line. The obo does no know
whe he is loca ed le hand o igh hand o i s
s a posi ion, s, no does i know he dis ance om
s o . Baeza-Ya es e . al. [2] desc ibe he s a egy
o sol e his p oblem using a unc ion . (i) is
he dis ance he obo walks in he i h s ep. I iis
odd, he obo mo es (i) s eps om he s a o
he igh and (i) s eps back; i iis e en, he obo
mo es o he le . I is assumed, ha he mo emen
is co ec , so a e mo ing (i) s eps om he s a
poin o he igh and mo ing (i) s eps o he le ,
he obo has eached i s s a poin . Baeza-Ya es
e . al. showed, ha a s a egy wi h (i) = 2iis 9-
compe i i e and his is op imal.
An online s a egy ha p oduces a pa h o
leng h |πonl|is called C-compe i i e i o all scenes
|πonl| ≤ C· |πop |+A
holds, whe e |πop |deno es he pa h leng h o he
op imal s a egy which makes use o ull in o ma-
ion.
3. Modelling he e o
The obo mo es s aigh line segmen s o a ce -
ain leng h om he s a poin al e na ely o he
le and o he igh . E e y mo emen can be a -
lic ed wi h an e o , ha causes he obo o mo e
mo e o less a han expec ed. Howe e , we equi e
he obo s e o in e e y s ep is wi hin a ce ain e -
o bound, δ. Mo e p ecisely i he s a egy mo es
he obo a dis ance ℓwe equi e ha he co e ed
dis ance is in he ange [ℓ·(1 −δ), ℓ ·(1 + δ)] wi h
δ∈[0,1[.
4. Reaching he doo
How la ge can he e o bound δbecome unde
he es ic ion, ha he obo should be able o
each he doo ? W. l. o. g. we conside he case, ha
he doo is loca ed on he same side as he i s s ep
o he agen . We assume ha he doo is loca ed
a d= 22j−ε, so an e o - ee obo hi s he doo
du ing he i e a ion wi h s ep wid h (j) = 22j.
s′
s
∆2j+2k−1d
22j+2k
4−δ
2−δ
2 + δ
1 + δ
1−δ
Fig. 1. In he wo s case, he s a poin o e e y i e a ion
d i s away om he doo . The e ical pa h segmen s
a e o highligh he single i e a ions, he obo mo es on
ho izon al segmen s only.
In he wo s case, e e y s ep o he igh o he
e o a lic ed obo is oo sho and e e y s ep o
he le is oo long, so s a poin o he i e a ions
d i s o he le , see Fig. 1. Le ∆kdeno e he d i
a e ki e a ions.
∆k=
k
X
i=0 2i·(1 + δ)
| {z }
S eps, ha a e oo long
−2i·(1 −δ)
| {z }
S eps, ha a e oo sho 
= 2δ·
k
X
i=0
2i= 2δ(2k+1 −1).
Le he e o a lic ed obo miss he doo du -
ing he i e a ion wi h s ep wid h (j) = 22jdue
o he d i o he le . Now we a e in e es ed in
he numbe o addi ional s eps, and whe he he
obo is able o each he doo a all. Ob iously he
eachabili y and he numbe o addi ional s eps de-
pends on he e o δ. I he obo hi s he doo , i
will hi in he i e a ion wi h a s ep wi h o 22j+2k,
k∈N>0, because he doo is loca ed igh hand o
he s a poin . To ensu e, ha he obo hi s he
doo , he leng h o he las s aigh pa h mus be
a leas as la ge as he dis ance o doo plus he
o e all d i o he le . The las s aigh pa h may
be e o a lic ed again, bu i s leng h is a leas
he lowe bound o he e o ange in he i e a ion
22j+2k. This yields
Ma ch 25-26, 2004 Se ille (Spain)
∆2j+2k−1+d≤22j+2k·(1 −δ)
⇔2δ·22j+2k−2δ+ 22j−ε≤22j+2k−22j+2kδ
⇒22j2δ22k+ 1 −22k+δ22k−2δ
<22j3δ22k+ 1 −22k≤ε
⇔δ≤1
3
22k−1
22k+ε
3·22j+2k
⇒δ≤1
3
22k−1
22k
The las e m con e ges o k→ ∞ o 1
3. Thus
Co olla y 1 I he e o δis no g ea e han 1
3
he obo will hi he doo .
Wi h he gi en analysis i is also possible o p esen
ela ions be ween he e o ange and he numbe
o addi ional i e a ions. Fo example:
Co olla y 2 I he e o δis no g ea e han 1
4
he obo will hi he doo wi h only one i e a ion
s ep mo e han he e o - ee obo .
5. Analyzing he pe o mance
W. l. o. g. o he compe i i e se ing i would be
he wo s , i he doo is hi du ing he i e a ion
wi h s ep wid h 22j+2, bu loca ed jus a li e bi
u he away han he igh mos poin ha was
eached du ing he i e a ion wi h s ep wid h 22j,
i. e.
d= 22j(1 −δ)−∆2j−1+ε= 22j(1 −3δ) + 2δ+ε.
This yields a ac o o
|πonl|
d=1
d 2
2j+1
X
i=1
2i+ ∆2j+1 +d!
=1
d2·(22j+2 −1) + 2δ(22j+2 −1) + d
=22j8(1 + δ)−1+δ+ε
22j
22j1−3δ+2δ+ε
22j+ 1
<81 + δ
1−3δ+ 1
To show ha his is he wo s case, we show
ha he obo s e o s in he le and in he igh
di ec ion a e di e en . Fu he mo e he e o in
each s ep may be a di e en one. Le δ+
ibe leng h
o he mo emen o he igh in he i- h s ep and
δ−
ibe he leng h o he mo emen o he le . Now
2j−1
X
i=1
(δ−
i−δ+
i)
deno es he de ia ion om he s a poin be o e
he 2j- h s ep and
2j−1
X
i=1
(δ−
i+δ+
i)
is he pa h leng h up o his poin .
As abo e he doo is hi du ing he s ep 2j+ 2,
he e o e i s dis ance is
d=δ+
2j−∆2j−1+ε
=δ+
2j−
2j−1
X
i=1
(δ−
i−δ+
i) + ε
Fo he co esponding pa h leng h we ha e
|πonl|=
2j+1
X
i=1
(δ−
i+δ+
i) +
2j+1
X
i=1
(δ−
i−δ+
i) + d
due o he ac ha we will inally s op a dis ance
d, we add he de ia ion o d.
Wi h his we ge
|πonl|
d= 1 + P2j+1
i=1 (2δ−
i)
δ+
2j−P2j−1
i=1 (δ−
i−δ+
i) + ε
We can conclude ha he a io achie es i s maxi-
mum i we exceed e e y δ−
i o he g ea es ex end,
which is 2i(1 + δ). Now we only ha e o ix δ+
iin
o de o maximize he a io. Ob iously he nom-
ina o ge s i s smalles alue i e e y δ+
iis e y
small, he e o e we use δ+
i= 2i(1 −δ).
Theo em 3 I he e o δis no g ea e han 1
3 he
obo will hi he doo wi h he doubling s a egy.
The gene a ed pa h is no longe han 81+δ
1−3δ+ 1
imes he sho es pa h o he doo .
6. Summa y
We ha e analyzed a simple doubling s a egy o
ind a doo in a wall espec i ely a poin on a line
in he p esence o e o s in mo emen s. We showed
ha he obo is s ill able o each he doo i he
e o is less han 1
3. Mo eo e , i he e o is less
han 1
4 he obo will need a mos wo i e a ion
s eps mo e han he e o - ee obo . I he e o in
20 h Eu opean Wo kshop on Compu a ional Geome y
he mo emen is bound by δ < 1
3, he compe i i e
a io is
81 + δ
1−3δ+ 1.
Bo h e o bounds a e a he big, so i can be
expec ed, ha eal obo s will mee his e o
bounds.
The p oblem o m ays is a li le bi di e en
because he obo may de ec he s a ing poin i
i changes om one co ido o ano he . He e, one
may be in e es ed in he p obabili y o en e ing
co ec ly he nex co ido .
Re e ences
[1] H. Abelson and A. A. diSessa. Tu le Geome y. MIT
P ess, Camb idge, 1980.
[2] R. Baeza-Ya es, J. Culbe son, and G. Rawlins.
Sea ching in he plane. In o m. Compu ., 106:234–252,
1993.
[3] P. Be man. On-line sea ching and na iga ion. In
A. Fia and G. Woeginge , edi o s, Compe i i e
Analysis o Algo i hms. Sp inge -Ve lag, 1998.
[4] R. Fleische , T. Kamphans, R. Klein, E. Lange epe,
and G. T ippen. Compe i i e online app oxima ion o
he op imal sea ch a io. 2004. o appea .
[5] S. Gal. Con inous sea ch games. In Sea ch heo y:
some ecen de elopmen s., olume 112 o Lec u e
No es in pu e and applied ma hema ics, pages 33–53.
Dekke , New Yo k, NY, 1989.
[6] A. Hemme ling. Laby in h P oblems: Laby in h-
Sea ching Abili ies o Au oma a. B. G. Teubne ,
Leipzig, 1989.
[7] C. Icking, T. Kamphans, R. Klein, and E. Lange epe.
On he compe i i e complexi y o na iga ion asks.
In H. B. Hend ik I. Ch is ensen, G ego y D. Hage
and R. Klein, edi o s, Senso Based In elligen Robo s,
olume 2238 o LNCS, pages 245–258, Be lin, 2002.
Sp inge .
[8] T. Kamphans and E. Lange epe. The pledge algo i hm
econside ed unde e o s in senso s and mo ion.
In P oc. o he 1 h Wo kshop on App oxima ion
and Online Algo i hms, Lec u e No es Compu . Sci.,
Be lin, 2003. Sp inge . o appea .
[9] J. S. B. Mi chell. Geome ic sho es pa hs and
ne wo k op imiza ion. In J.-R. Sack and J. U u ia,
edi o s, Handbook o Compu a ional Geome y, pages
633–701. Else ie Science Publishe s B.V. No h-
Holland, Ams e dam, 2000.
[10] N. S. V. Rao, S. Ka e i, W. Shi, and S. S. Iyenga .
Robo na iga ion in unknown e ains: in oduc o y
su ey o non-heu is ic algo i hms. Technical Repo
ORNL/TM-12410, Oak Ridge Na ional Labo a o y,
1993.