BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR92-1316
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Algorithms for On-Line Navigation
AUTHOR:: Kleinberg, Jon M. 
DATE:: November 1992
PAGES:: 14
ABSTRACT:: 
We consider a number of problems faced by a robot trying to navigate inside 
a simple polygon. Such problems are ``on-line'' in the sense that the robot 
does not have access to the map of the polygon; it must make decisions as it 
proceeds, based only on what it has seen so far. Specifically, we examine 
algorithms for the related problems of exploration and search. We present a 
5/4-competitive randomized algorithm for exploring a rectilinear polygon; the 
only privious work here is the deterministic 2-competitive algorithm claimed 
in Deng, Kameda and Papadimitrou. For the problem of searching for a 
distinguished point in a polygon, we give a $\sqrt{3}$-competitive algorithm 
for traversing a street, which improves on a result of Klein by more 
than a factor of 3. Finally, the techniques we use in exploration and the 
construction of search patterns are combined to give an algorithm for 
searching an arbitrary and unknown rectilinear polygon; here, no constant 
competitive ratio can be achieved, but our algorithm is within a constant 
factor of optimal in the worst case.
END:: CORNELLCS//TR92-1316
BODY::
Algorithms for On-Line Navigation*
Jon M. Kleinberg
IR 92-1316
November 1992
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*This work was sponsored in part by the Sloan Fellowship of Eva Tardos.
Algoritlims for O?-Li?e N?vigatio? *
Jo11 M. Nleinberg
Department of Computer Science
Cornell University, Ithaca, NY 14853, U.S.A.
Abstract
We consider a number of problems faced by a robot trying to navigate inside a simple
polygon. Such problems are `?on-line" in the sense that the robot does not have access to the
map of the polygon; it must make decisions as it proceeds, based only on what it has seen so
far. Specifically, we examine algorithms for the related problems of exploration and search. We
present a 5/4-competitive randomized algorithm for exploring a rectilinear polygon; the only
previous work here is the deterministic 2-competitive algorithm claimed in Deng, I?ameda,
and Papadimitriou. For the problem of searching for a distinguished point in a polygon, we
give a ???-competitive algorithm for traversing a street, which improves on a result of Klein
by more than a factor of 3. Finally, the techniques we use in exploration and the construction
of search patterns are combined to give an algoritbm for searching an arbitrary and unknown
rectilinear polygon; here, no constant competitive ratio can be achieved, but our algorithm is
within a constant factor of optimal in the worst case.
*This work was supported in part by the Sloan Fellowship of Eva Tardos.
1. Introduction
A recurring theme in robotics and other branches of computer science is the need to design an
autonomous algonthm that can interact with its environment. Very often, a major goal in such
problems is to write an algoflthm with as tittle "hard-wired" knowledge as possible; it should be
able to deal with a wide range of environments as it encounters them. We cannot say that the topic
of navigation in an unknown geometric scene (??on-line navigation") has grown out of this theme,
in that some of the questions it considers maz&solving, for example ---H reach back a hundred
years or more [Orej. But problems in on-line navigation provide us with a clear illustration of the
issues faced in the design of such autonomous algorithms.
Navigation problems had been addressed by Bliim and Kozen in the context of automata theory
[BK], and by Lumeisky, Stepanov, and others in robotics [LS]. The incorporation of robot navi-
gation into the framework of on-line algorithms (cf. [ST, MMSi), however, was first proposed by
Papadimitriou and Yannakakis in [PY]. Since then, a number of papers have anatyzed algorittims
for navigation in an unknown environment in terms of their coi?petztive `?atio: the worst-case ratio
of the distance traveled by the algorithm to the distance that an optimal algonthm with a map
of the scene would have traveled. Navigation here is viewed as a geometric optimization problem
the input (the set of obstacles in the environment) is revealed only gradually, as the robot sees
(or touches) it, and the cost incurred by the robot is the distance it travels. An algorittim whose
competitive ratio is bounded by c can be termed c-conipetitive for the given problem. Thus in the
prnblem originally considered in [PY], that of finding a short path between given points A and f?
amidst an unknown set of obstacles, the competitive ratio of an algorithm is the worst-case ratio
of the length of the A-B path it generates to the length of the shortest obstacle-avoiding A-B
path. Naturally, the best competitive ratio achievable depends 01) the class of obstacles considered;
variants of this problem have been considered in [BRS, BBFY].
Here, we investigate two other kinds of navigation problems: exploration and search in a simple
polygon. The model in these problems is as follows. A robot with vision is placed in a simple
polygon P. F?rom its current position s it can see any point x inside or on the boundary of P such
that the line segment from 8 to w is completely contained in P. We assuiiie here that it has untimited
memory; as it moves, it can build a `map" of F, consisting of all the points on the boundary of P
that it has seen. The full map of P is simply the circulau list of the coordinates of its vertices.
Deng, Kameda, and Papadimftriou introduced the problem of explonug a simple polygon in
[DKP]. A robot must traverse a closed path inside P, beginning and ending at a given point s, such
that it sees all points on the boundary of P; this is an on-hue w?rsion of the "Shortest Watchman
R?oute" problem of Chin and Ntafos [CNj. They claim a 2-competitive deterministic algorithm
for exploring a simple rectilinear polygon (distances measured ill the L1 metric). We give a 5/4-
competitive randomized algorittim for this problem, and show that no deterministic algorittim can
achieve a ratio better than 5/4.
It is less clear how to define the problem of searching a simple polygon P. The idea is for a robot
with vision to begin at some point 8 in P and travel to a point I in P. The location oft is unknown,
but the robot will recognize it when it first sees it. There are two flavors of this problem, one of
them more "on-line" than the other, depending on whether the map of F is known or not. In the
style of search problem pioneered by Baeza-Yates, Culberson, and R?awlins [RCR?], a robot is faced
with a known geometric environment and must find a distinguished goat point that is "hidden" in
the environment; its competitive ratio is the worst-case ratio of the distance it travels to the length
of the shortest path from start to goal. Thus, the problem becomes to construct a searvh patte?n in
the environment that sees all points at each given distance as quickly as possible (in what follows,
we make no distinction between the search pattern and the corresponding algonthm to traverse
it). The techniques of [BCR?1 were developed for fairly simple environments such as a set of m rays
diverging from a common point; they have proven, however, to have application in a wide of variety
of on-line navigation problems. (See also \yKRT] in which a randomized algorithm for the problem
of searching n? concurrent rays is presented.)
In this paper, we consider the question of search patterns in an arbitrary simple rectilinear
polygon. We identify the notion of an essential cutintroduced in [CN] as the feature of a simple
polygon that makes search difficult; certain points lying beyond an essential cut cannot be seen
unless the cut is crossed. Indeed, a simple construction gives a class of rectilinear polygons P1,F2,..
such that Pm has m essential cuts and no algorithm has competftive ratio better than Q(m?) for the
proUem of searching for a distinguished point in Pm. We then show that for any simple rectilinear
polygon P with ?fl essential cuts, an 0(m)-coinpelitive search pattern can be constructed for the
problem of searching for a goal inside P.
Very little work has been done on the problem of search wh??n both the environment and the
location of the goal are unknown, and it seems difficult to give situations in which a constant
competitive ratio is achievable. One example is the algorithm of Klein [Kl] for traversing a special
kind of polygon known as a st?et We present an aigo?'thm for this pmblem which improves on
the competftive ratio given in [Kl] by more than a factor of 3. F?inally, we show how to combine the
notions used in exploration and the construction of search patterns to give an algoritlim for a robot
searching for a point in an unknown rectilinear polygon. That is, the robot must again construct
a search pattern, but here it must truly do so in an on-line fashion it does not have access to
the map of P. If F has n? essential cuts, the conipetitive ratio of the algorithm is again O(n?); this
shows that knowledge of P does not help, in aii asymptotic sensc, for the problem of searching for
a point inside it.
I'inally, a word about the distance metrics used h? this paper. The distance between two points
as measured in the L1 and L2 (Enclidean) n?etrics differs at niost by a factor of ?; thus, an
algorithm with a competitive ratio of c in L1 has a competitive ratio at most c? in L2. With the
exception of the algouthm for traversing streets, which is analyze?i directly in the Euclidean metric,
we present our results in the conceptually neater framework of tlie L1 metnc. In view of the tight
correspondence between L1 and L2, our search algorithiris are 0(m)-competitive in both.
The paper is organized as follows. The algorithrn for traversilig a street is presented in Section
2. Section 3 develops a number of useful facts about rectilinear polygons and uses them to prove
the existence of an 0(m)-competitive search pattern in any simple rectilinear polygon. Section 4
presents our results on exploration, and Section 5 combines these earlier ideas to present the 0(m)-
competitive algorithm for searching an unknown rectilinear polygon. l?inally, Section 6 concludes
2
with open problems and possible extensions of this work.
2. Traversing an Unknown Street
Let F be a simple polygon and 8 and t two distinguished points on the boundary. The removal of 8
and t would disconnect the boundary into two polygonal chains, L and R. We say that P is a ?t?et
[1K, Kl1 if each point on the boundary of P can see some point on the opposite boundary chain. The
goal is for a robot with vision to travel from 8 to i; neither the map of P nor the coordinates of t are
known. The cost incurred by the robot is the length of the path it generates, and its competitive
ratio is taken with respect to the length of the shortest s-t path in P; distances are measured in
the Euclidean metric.
a)			b)
__x			___			_
y
8
A
Th
Indecision
left cavemouth
Figure 1: Streets and their views
rol)ot
Ar
right
cavemouth
Figure 1(a) can be completed to form a street in whid? t could be just around the corner from
either X or Y [Kl]. The robot will incur the best worst-case performance if it moves directly to
segment XY, then to t (it will see J when it reaches XY). This can be at most a factor of Vm2
longer than the shortest path. Curiously, this is the only known lower bound on the competitive
ratio achievable for the problem. In [Kl], an algonthm with a competitive ratio of at most 1 + 2??
(N 5.72) is presented. Below, we give an algoflthm with competitive ratio at most ? ( 1.73).
The example of Figure 1(a) is central to the proof technique we develop in this section, and it
highlights a principle that will appear repeatedly in what follows on-line algorithms hate making
decisions. Specifically, it is useful in inany navigation problems to adopt a strategy that preserves
the robot's options for as long as possible. In the figure, suppose the robot at point 8 is moving
towards segment XY, but it has not yet decided whether it ultimately wants to visit point X or
Y. Let us define a polygonal path to be monotone if the x- and y-coordinates of the points on the
3
path change from their initial to final values monotonically. Then the key observation is that in
the L1 metric, any monotone path between two points is a shortest path, so the robot can defer
its decision (X or Y) until it reaches segment XY and still have the option of traveling optimally
to either point. The related fact for the Enclidean metric is that any monotone path between two
points in the plane has length at most a factor of 72 times the straight-line distance between them.
Thus, in this example, the robot can move to segment XY before making a decision and travel only
72 times too far (Euclidean distance) in the worst case.
Let F be a street, and assume that the robot is currently located at a point x inside P. The
robot maintains an extended view of P; this consists of all points on the boundary of P that it
has seen so far. The robot's extended view will typically look like the example of Figure 1(b). We
define a cave G1 to be a connected chain of the boundary of P such that the robot has seen the
endpoints of the chain but no other points of it. At some point PI on the robot's path, these two
endpoints were on the same line of sight from PI; call the one closer to PI the ?`mouth" of C. In the
neighborhood of a caveniouth v, F lies either to the left or right of the ray p'v; we accordingly refer
to v as being either a left or right cavemouth.
Assume that t has not yet been seen, and the robot has maintained the invariant that the points
in its extended view immediately to its left and right belong to L and R respectively. In view of
these assumptions, we assemble some facts about extended views before presenting the algorithm
itself. The first is a standard fact about shortest paths inside a simpie polygon.
Lemma 1 Ift is contained in a cave C, Then The shoNest w-t path touches the niouth of C
Lemma 2 Let p be a point on bounda?y' chain L (I?;, and let ? be the boundary chain sp of F
contained in L (11). If the robot moves fi?w' s to p, it will have seen every point on
Proof. Every point on boundary chain ? must see be able to see some point on R; but all such
lines of sight to R cross the robot's path from 5 to p. Thus the robot has seen every point on ?. 1
Len?n?a 3 Ifv is a left (right) cavemouTh, it belongs to bonnda?? chain L (11).
Proof. Assume v is a left cavemouth, v C J?, and v was seen from point p1. The chain determined by
a clockwise scan of the boundary from v to 8 (taken from point p') is entirely contained in R. Thus,
if the robot were to walk directly from p1 to v, it would have seen all of this chain, by Lenima 2.
But since v is a cavemouth, it would not have seen any point on the boundary of P just around the
corner from v, which belongs to this chain, a contradiction. I
Corollary 1 In the extended view, all left cavemoullis lie to the left of all right cavemouths.
If the extended view contains any left cavemouths, we define c1 to be the rightinost one. The
point Cr is defined analogously for right cavemouths. If both c1 and CT are defined, the chain
between the far endpoints of their respective caves must be completely visible in the extended view;
otherwise, it would contain an additional left or right cavemouth. Combining this with Lemma 1
and the fact that t has not been seen, we have
4
Lemma 4 The point t lies in the cave of Cithef Cj 0? CT. Conse?aently, the shortest path from x to
t touches either Ci or CT
Let d(.,.) denote the length of the shortest path between two points in P. The shortest path from
5 to t, denoted by F, is a chain of line segments joined at reflex vertices of P. Assume inductively
that the robot is currently sitting on a vertex x ? F; our algorithin shows how it can get to another
vertex x' c F while traveling at most vR3d(x, x'). Based on the robot's extended view, there are
four cases to consider. (See Figure 2.)
4
case 2
M
y
4
case 3
5
r
Case 4
Figure 2: The algonthin at work
Case 1. If t is visible the robot moves directly to t. The distance traveled is d(x, t).
Case 2. If CT (ct) is not defined (there are 110 right (left) cavemouths), then by Lemma 4, F
passes directly through c1. Thus, the robot moves directly to c1, following 1' the whole way.
Otherwise, both c1 and CT are visible. The robot chooses a direction of motion such that c1 lies
to its left and CT lies to its right. We view this as a coordinate system in which the robot is the
origin and it is moving in the direction of the positive 1)-axis; thus, Ct has negative r-coordinate and
Cr has positive w-coordinate. The robot moves in this direction, updatiiig its extended view and the
points Ci, CT, until one of of the above two cases applies, or one of the following two:
Case 3. The point Ct (or respectively c?) "jumps" to the opposite side of the 1)-axis. At the
moment when this happens, both Cj and CT will lie on the same line of sight. If the robot moves in
this direction until it hits the nearer one, it will once again be on a point x' E F, having followed a
path from x to x' that is monotone with respect to the chosen coordinates. Thus, it has traveled
no more than 72 times the distance from w to x' along F.
Case 4. If none of Cases 1, 2, or 3 applies, then there comes a point at which the robot's line of
sight to c1 (Cr) is parallel to the x-axis. At the moment when this happens, the robot is "confused";
5
it can no longer follow a path guaranteed to be monotone to either c1 or Q. However, since F is a
street, if the robot touches the segment CtCr, it will see the entirety of at least one of their respective
caves, and thus will be able to return to F by moving to the other cavemouth.
Thus, the problem in Case 4 becomes the following. Assume that the robot is currently at y.
It must choose a "landing point" z on the segment CICT so as to minimize the relative distance it
travels in returning to V. If we set ? d(x,y), s d(y,z), t d(z,ct), t1 d(Z,CT), and let d1
and dT denote the shortest-path distances from w to c1 and CT respectively, then the robot wants to
choose z so as to minimize
+ s + t r + s + t'
max(			d1			dT
Based on what it can see from the point y, it has enough information to make this calculation;
when it finally arrives at c1 or Cr, it will once again be sitting on V.
It is difficult to give the precise worst-case value of this ratio over all r, s, t ? ?+, but we
can put a fairly tight upper bound on it as follows. Suppose that the robot follows the weaker
strategy of always moving along the normal to segment c!c?. Then we have d1 > mTh?2+t2 and
dr > MTh-)2+tl2, so an easy calculation shows that both of the ratios in the expression above
are bounded by ffi3.
Finally, we should note that it is possible for the robot's motion in the positive ,y direction to
be stopped by the boundary of F. By Lemma 2, however, it will have seen the entirety of one of
the caves associated with c1 or CT b? the time ?his happens, so it can return to V; the preceding
analysis is not affected. Thus we have
Theoren? 1 For any strect P, thC ahove algorithw pmduccs a path fron? 8 to t that ?s at niost ?
tirnes as long as the shortest s-t path in F
3. Search Patterns jn a Rectlllnear Polygon
We now turn to the question of search patterns in rectilinear polygoris. As in described in the
introduction, our robot is given the map of a simple rectilincar polygon P and a point 5 in F; it
must find a distinguished point tin P. The goal is to construct a search pattern T in P so that by
traversing f it will follow an s-t path which is as short as possible relative to d(s, t), regardless of
the location of t In this and the remaining sections, distances will be measured in the L1 metric.
There are a number of defiuftions based on those in tCN, DI?P' that will be useful here. Let P
be a simple rectilinear polygon and e an edge of P. The edge e is contained in a line"; we say that
an ertended edge is a line segment e? c ? in P which shares one endpoint with e, and whose other
endpoint is also on the boundary of P. Each edge e induces at most two extended edges. Also, note
that an extended edge is either horizontal or vertical, depending on the onentation of its associated
edge e. Define L, and lIe to be the two boundary chains of P formed by removing the endpoints
of e. Varying slightly from the terminology of [c'Nl, we say that a horizontal extended edge e is an
essential cut if Le C Lf for all horizontal extended edges f, or Re c R? for all horizontal f. We
make the analogous definition for vertical extended edges.
6
Assume that a starting point 5 inside P is given. Then we will say that an extended edge e
induced by e is a hornzon if there is no path from 5 to e that does not cross e. See Figure 3. We can
define a partial order on horizons as follows: if h and h' are horizons, then h ? h' (h dominates h')
if any path from s to It' must cross It. Because P is a simple polygon, we have the following useful
lemma.
Lemma 5 Let It and It' be Itorn?ons with the same ornentation such that for some point v in P,
every path from 5 to v must cross both It and It'. Then It and It' are comparable with respect to ?
(It ? It' or It' ? It).
a)
Th
M?!????e?sentiai cut
ffi-??ess?tiaI cut
Th'
_ - ---A
Th
L
Polygon Pm
Figure 3: Some simple rectilinear polygons
Based on the above lemma, we can represent the partial order ? restricted to the horizontal
segments by a directed tree Th in which the root is the point s and the other nodes are horizontal
horizons. For vertical horizons, there is the analogous representation as a tree T)
Assume that the polygon P has m essential cuts. We will say that s lies "beyond" an essential
cut if it is on the side of the cut that is dominated by all other horizons of tlte same orientation.
Clearly 5 can be beyond at most one horizontal and one vertical essential cut; the rest of the essential
cuts appear as leaves of Tic and Tv. Conversely, a leaf of Th corresponds to a honzontal essential
cut, or a horizon i-i that doniinates sonie vertical horizon It'. In the latter case, no other leaf of Th
can dominate It', by Lemma 5, so It can be uniquely charged to It'. The same analysis holds for ,
giving us
Lemma 6 The total number of leaves of Th and Tt, is between ni --H 2 and 2m.
If e is an edge of P and e is a horizon, a point on the interior of e can only be seen once the
robot touches e. As a result, we have the straightforward example of Figure 3(b), in which polygon
Pm contains `in long "arms," each ending in an essential segment. For any given search pattern, we
can place the goal beyond the essential cut it crosses last. A sinillar argument holds for randomized
search algorithms, so we have
7
Proposition 1 No algornthrn (dete?ministic 0f randomized) fo? searching Pm can he better than
Q(m) -cornpetitive.
We note that the definition of a street can be applied here to give an equivalent measure of the
complexity of searching P. Say that a street decomposition of P is a representation of P as Uffi1Qi,
where each Q? is a rectilinear street all of whose vertices lie on the boundary of P. Let k(P) denote
the minimal value of k, taken over all possible street decompositions of P. We can show that if
P has m essential cuts, then k(P) is Q(m), and clearly the polygons Pm have decompositions of
size 0(m). Thus, our upper and lower bounds on searching can be phrased equivalently in terms
of k(P).
The following three lenimas provide a basis for constructing a search pattern that tries to cross
each horizon in P as quickly as possible. The first a key property of the L1 met?c and a
special case of the second are given in [DXPj.
Lemma 7 Let v he a point in P and ot a horizontal or rertical line segment in P. Assame that
a shortest path from v to ? ends at the point `a E Ct'. Then for ang other a' C ?, d(v,a')
d(v,u) + d(a,u').
Lemma 8 Let eti, . . . , ?,, he a set of horn?onta' and ve4ical segments in P, and v a point in P The
(L1) shortest path beginning at v and touching the o?? i?t order is generated hg the greedg algorill?m,
which, from segment ct?, alwags chooses the shortest path to 0'j+1
Proof Let 5 denote the greedy algorithm, and A any other algorithin. Each algorithm defines
a "hitting point" 5(i), A(i) on segment ct',, where it first touches this segment. Between these
points, it clearly should follow an L1 shortest path. Set 5(0) A(o) "`, and 5 d(5('i), S(i+ 1)),
Q d(A(i),A(i+1), dj d(5('i),A(i)). Then by Lemina 7 and the definition of 5, s?+d?+1 ? dj+Q,
so ?? ? a? + (d? --H dj+1). The total distance traveled by 5 is Zi ??, whidi is less than or equal to
Z?(a? + dj --H dj+1) d? + Z? Q I
Lemn?a 9 Let v he a point in F such that 5 cannot see u. Then there is some horizon h in F that
separates 5 f'?m v, such U?at for any path from 5 to h, the point " can he seen f'?m some point on
this path. (I.e. no matter how the rohot gets to h, it wit! have seen v.)
Proof. By analogy with the construction of the previotts sectioii, consider the "view" of P from
point v. Define a cave, as above, to be a connected chain of the boundary of F such that v can see
the endpoints but no other points of the chain. Since 5 cannot see v, 5 must lie in some cave C.
Let v be the cavemouth of C; then there is a horizon with endpoint `a such that by the time the
robot reaches this horizon, it will have crossed the ray ?Ka and seen v. I
We now inductively construct a tree 14 consisting of polygonal chains in P as follows. The root
is the point 5. When 74 crosses a horizon h C Th with out-edges (h, h1),.. . , (h, hk), we extend 74
via shortest paths to the horizons h1hk. An analogous construction yields a tree TJ. These
trees have the same root; we view them as a single tree T of polygonal chains.
8
Lemma 10 T contazn? at mo?t 2rn Thave?, and a ?horte?t path from 8 to each horn%?n zn
Proof. The first part of the claim follows by the fact that the leaves of ? correspond to leaves of Th
and Tv. Consider the path in Th' (TJ) to a horizontal (vertical) honzon h. It crosses the horizons
separating 8 from h in a greedy manner; since any path must cross these horizons, it is a shortest
path by Lemma 8. 1
The search algonthm now traverses T in a style similar to the algorithuis of ?BCR?1. Initially,
the robot can see all points in P that lie within some fixed distance of 8; we assume without loss of
generality that this distance is 1. The algorithin operates in phases. In phase j, the robot follows
all polygonal chains ofT in a depth-first manner out to a distance of 2?. If at any point it sees the
goal t, it moves directly to it.
Theorem 2 The above algorz'thm Z'8 0(m)-competitive fo? the problem of searching P.
Proof. Assume that the robot first sees tin phase j > 1 (the case j 1 is similar), and let h be a
horizon as in the statement of Lemma 9. Let 6 denote the distance from t to the point at which the
shortest s-h path in T crosses h. Then since t was not seen in phase j --H 1, d(s, h) > 2j--H1, and so
d(s, t) > 2i--Hi + 6, by Lemma 8. The robot travels a distance at most 2ni(2?) in phase `i, so it travels
at most Zffi1 2m(2?) ? 25+2m to reach h, then 6 to reach t. Thus, the total distance traveled is at
most 6 + 2j+2? ? (8m)d(s, t). I
4. Exploring a Rectilinear Polygon
In this section, we consider the problem of a robot which must explore a simple rectilinear polygon
P, starting and ending at some point 8 in F. That is, it must traverse a closed path beginning and
ending at 8 such that every point on the boundary of F is visible from some point on the path.
As noted in [CN, DNP] (see also the discussion in the preceding section), a closed path through 8
has this property if and only if it touches all essential cuts in P. For simplicity of presentation, we
assume that 8 does not lie beyond any essential cut. In [CN, DKPl, i? is observed that since any
exploration route can be traversed (off-line) without self-crossings, the shortest exploration route
will touch the essential cuts in clockwise order. Moreover (see also Lemnia 8), it will touch the cuts
in this order using the greedy algorithin.
Consider the case in which the point 8 lies on the boundary of P, between the endpoints of
essential cuts e and e'. The on-line algorithm given in [DKP] will traverse the greedy path that
touches the essential cuts in clockwise order, beginning with e. Consequently, this algorithm finds
the optimal exploration route on-line; it is i-competitive when 8 lies on the boundary of P.
When 8 does not lie on the boundary, the choice of which essential cut to start with becomes
crucial, and the robot does not have enough information to make this choice.
Proposition 2 No deterministic algorithm for exploring a simple rectilinear polygon can be better
than 5/4-competitive.
9
a)
Th
7D
Add small "caves" at
three of the four points
A, B, C, D
N
Figure 4: Lower bound constructions
Pwof. Consider Figure 4(a). All the long edges of the polygon P have length 2, the short edges
have some length ? much less than 2, and 8 is at the center, A robot exploring P must cross either
the upper or lower horizon first; assume the former case. At this point, it will see two tiny ?caves"
at points A and B, both of which nuist be visited. Assume that it visits A before visiting 1? or
crossing the lower horizon (other cases are similar).
We now add an extra cave at C but not at D. Even if the robot now had the map of F, it
would have to travel a distance of 8 to visit the caves at B and C' and retiirn to 8. It has traveled
a distance of 2 to reach A; thus its total distance is 10. On the other hand, the greedy exploration
route which visits C first travels a distance of 8. 1
When 8 is an interior point of Pit is suggested in ?DKP1 to ?take any one of the four directions
along the coordinates from 8 as the initial direction of motion until the boundary is hit," and then
follow an algo?'thm similar to the one for 8 on the boundary. However, this algorithm does not
have any constant competitive ratio; consider Figure 4(b), in which the optimal exploration route
has length 2 and the boundary is as far away as we want.
In the remainder of this section. we present a deterministic 2-competitive algonthin, and adapt
this to give a 5/4-competitive randomized algon'thm. Consider first the following construction.
If the robot standing at 8 were to imagine a tiiin `needle" of boundary extending from the real
boundary of P to 8, it would then be on the boundary of this new polygon and could explore
optimally. If we restrict ourselves to horizontal or vertical segments, then there are four possible
needles that can be inserted in P. See Figure 5.
Let L(.) denote the length of a path in P, E denote the optimal exploration route in P, and Pi
denote polygon P with the jth needle inserted, i t, 2, 3,4. Finally, we denote by Tithe (optimal)
exploration route generated by the robot starting from 8 in Pi (8 is on the boundary of each Pi).
Of course, we are not really interested in the performance of Ti il-i P?; we must show that Ti is also
not far from optimal in the onginal polygon P. Set di L(74) --H
10
a)
needle
Inserting needles in the polygon
E
The exploration route I?, avoiding a needle
Figure 5: Polygon with needles
Lemma 11 Zsffiidi ffi
P?oof. Since E visits the essential cuts of P in clockwise order, it meets each needle in at most one
point. E can be traversed so as to avoid the jth needle (it takes a detour through s); let us denote
this longer route by Ej. Since E? is an exploration route for Fj and T? is optimal in this polygon,
we have L(Tj) ? L(Ej).
Let d51- L(E5-)--HL(E). Consider the four points at which E hits tlie needles (some of these points
may be?); connect these by shortest paths to form a closed path J'. Then we have L(T) ? L(E)
and L(T) Z5Y1 d?. Since dj ffi d'j for each `i
4			4
zd5?zd5(?L(E). I
i--H--Hi
Thus, if the robot chooses any needle, the exploration route T it generates will have length
at n?ost 2L(E). Simple examples show that standing at 8, th?re is no way to choose a needle
guaranteeing a peftormance better than this. However, the expected value of the quantity d5- is
bounded by L(B)/4, so if the robot chooses one of the four needles uniformly at random, the
expected length of the exploration route it generates is at most $)/4E(E). Thus we have
Theoren? 3 The 9iven detemninistic and ?`ando?nized eplo?ation al?or?thms have cornpetitive ?atios
of 2 and 5/4 ?espectivelu.
5. Searching an Unknown Rectilinear Polygon
Finally, we combine ideas from the preceding two sections to give an O(?n)-competitive algorithin
for searching a simple rectilinear polygon with fl1 essential cuts, even when the map of the polygon
is not known in advance. This generalizes the result on search patterns from Section 3; note that
the ?(m) tower bound on competitive ratio clearly holds here as well. Specifically, the problem is
11
for a robot, starting at a point s in a simple rectilinear polygon P for which `it does not have the
map, to find a point t while traveling as little as possible.
There are two lemmas that will be useful in what follows; the first is an interesting fact in its
own right. As before, let d(u, v) denote the length of the shortest u-v path in P.
Lemma 12 Let P be a simple polygon (not necessarily rectitinear), and consider a robot traversing
some path in P. If points u and v are both visible from this path, then the `robot can determine
d(u, v) without seeing the rest of P.
Proof. In fact, it can compute a shortest path between v and v. Since we are dealing with the L1
metric, the shortest v-v path in P will not generally be unique. However, some shortest v-v path
is polygonal (consists of a finite nun??er of line segments). We define the robot's extended view of
P by analogy with Section 2. By definition, the line segment joining the two endpoints of a cave in
this view is completely contained in P; let us call it a "pseudo-edge." Let P' denote the truncated
polygon whose boundary consists of the edges and pseudo-edges of the extended view of P. Thus,
the robot has seen all of the boundary of PI.
We claim that there is a shortest v-v path in P that does not leave P'. The result will follow
since the robot can obviously compute a shortest `a-v path in P1. Let T be a polygonal shortest
v-v path in P, which may enter a cave of the extended view, crossing pseudo-edge e at the point x.
Since v lies in P', the path nuist re-enter P'; let 115 say that it next does so by crossing pseudo-edge
e1 at point y. Since P is a simple polygon, e e1. Thus we can form a new v-v path which goes
directly from x to y when T enters this cave; this operation does not increase the length. Proceeding
in this way, we eliminate the (finitely many) places at which 7' enters a cave, producing a v-v path
T1in P' with L(T') ? L(T). 1
Lemma 13 Let P be a simple rectilinear potggon wilk a disti?guished point 8 in its interior, jix
some subset of the horizons with respect to 5, and let P1 be the l?uncaied polygon formed by removing
the parts of P beyond these horizons. Then the nun?ber of essential c?'ts of P' is at most the number
of essential cuts of P.
Proof. In effect, we are pruning the trees Th and `TT That is, any essential cut in P' dominates
some essential cut c of P with the same onentalion, and by Len?tna 5, no other essential cut of P'
with this orientation can dominate c. 1
As before, imagination is our robot's most powerftil tool. The idea is to successively form
polygons P6, which is the polygon P truncated at horizons more than ? away from 5. The robot
imagines that it is in P?, and it explores this polygon. If it fails to find t, it doubles ? and tries
again. All the points of P within some distance of s are visible from s; let us assume that this
distance is 1. Hence, when k 1, the robot explores P6 by standing still. Otherwise, it follows
a modified version of the exploration algorithrn of [DKP]. It successively crosses horizons whose
endpoints it encounters in clockwise order, treating horizons at a distance of more than 6 as walls.
(By Lemma 12, it can correctly gauge distances in P, and Lemma 7 implies that the distance to a
12
horizon can be determined, once it is completely visible, by the distance to its endpoints.) It is not
difficult to show that combining this technique with the algorithin of the preceding section gives a
2-competitive algorithm for exploring P6. llence,
Theorem 4 If P is an unknown rectilinear polygon with m essential cuts, the above algorithm is
0(m)-competitive for the problem of searching for a point t in P
Proof, I3y Lemma 13, the number of essential cuts in each pb is at most m. One way to explore
P? would be to travel separately to each essential cut and back to 5. Since each essential cut is
at most ? away from 5, this exploration route has length at most 2m?. The robot is following a
2-competitive Jgon'thm for exploring P?, so it travels no more than 4m?.
Since ? is doubled at each iteration, an argument very similar to that in the proof of Theorem 2
shows that the robot travels no more than 0(m) times d(s,t) to reach t. 1
We note that the polygons Pm can be modified to provide a lower bound of Q(m) for the problem
of finding a shortest path between 5 and t when the coordinates of 5 and t are both known but the
map of P is not. Our algon'thm is therefore asymptotically optimal for this problem as well.
6. Conclusion and Open Problems
We have a considered a number of questions related to exploration and search in a simple polygon.
For general search problems in rectilinear polygons, the worst-case competitive ratio is bounded
in terms of the number of essential cuts in the polygon; this is realized by simple lower-bound
examples. In this sense the definition of a `?street" is worth noting, in that it is gives a fairly
general class of polygons in which a constant competitive ratio for search is achievable. It would be
interesting to find other classes of polygons which can be searched efficiently.
There are a number of other open questions that could be worth investigating. First of all, there
is still a gap between the lower bound of 5/4 and the upper bound of 2 on the best competitive
ratio achievable for exploring a rectilinear polygon deterministically. Also, any improvement on the
randomized exploration algorithm given here would beat the deterniinistic lower bound. Finally,
exploration and search become quite difficult when the robot is n?)t in a simpky connected region; it
is interesting to consider which restricted cases of this problem allow for algorithuis with a constant
competitive ratio, independent of the number of "holes."
Acknowledgements
The author wishes to thank Eva Tardos for numerous helpful discussions and ideas on the topic of
this paper. Thanks also to the robotics and vision groups at Cornelt for their feedback.
13
References
[BBFY] E. Bar-Eli, P. Berman, A. Fiat, P. Yan, "On-Line Navigation in a Room," Proc. 3rd
ACM-SIAM Symposium on Discrete Alyomthms, 1992, pp. 237--H249.
[BCR] R. Baeza-Yates, J. Culberson, G. Rawlins, "Searching in the Plane," Information and Corn-
putation, to appear.
[BPS] A. Blum, P. Raghavan, B. Schieber, "Navigating in Unfamiliar Geometflc Terrain," Proc.
23rd ACM Symposium on Theory of Computiny, 1991, pp. 494-504.
[BK] M. Bluin, D. Kozen, "On the Power of the Compass (or, Why Mazes are Easier to Search than
Graphs)," Proc. 19th IEEE Symposium on Foundations of Computer Science, 1978, pp. 132--H142.
[CN] W. Chin, 5. Ntafos, `?Shortest Watchman Routes in Simple Polygons," Discrete and Compu-
tational Geometry, 6(1991), pp. 9--H31.
[DKP] X. Deng, T. Kameda, C. Papadimitnon, "How to Learn an Unknown Environment," Proc.
32nd IFEE Symposium on Foundations of Computer Science, 1991, pp. 298--H303.
[1K] C. Icking, R. Klein, "The Two Guards Prnblem," Proc. Wh ACAJ Symposium on Computational
Geometry, 1991.
[Kl] R. Klein, "Walking an Unknown Street with Bounded Detour," Proc. 32nd IFEE Symposium
on Foundations of Computer Science, 1991, pp. 304--H313.
[KRT] M. Kao, J. Reif, 5. Tate, "Searching in an Unknown Environment: An Optimal Randomized
Al orfthm for the Cow-Path Problem," Proc. 4th ACM-SIANI Symposium on Discrete Algorithms,
193, to appear.
[LS] V. Lumelsky, A. Stepanov, "Path-Planning Strategies for a Point Mobile Automaton Moving
Amidst Unknown Obstacles of Arbitrary Shape," Alyorithmica, 2(1987) pp. 403--H430.
[MMS] M. Manasse, L. McGeoch, D. Sleator, "Competitive Algonthins for On-Line Problems,"
Proc. Twentieth ACkI Symposium on Theory of Computiny, 1988, pp.322--H333.
[Ore] 0. Ore Theory of Graphs, Providence: AMS, 1962.
[PY] C. Papadimitriou, M. Yannakakis, "Shortest Paths Without a Map," Theoretical Computer
Science, 84(1991), pp. 127--H150.
[ST] D. Sleator, R. Taijan, "Amortized Efficiency of List Update and Paging Rules," Comm. ACM,
23(1985), pp. 202--H208.
14
