Randomized Strategy for Walking in Streets for a
Simple Robot
Azadeh Tabatabaeia,∗, Mohammad Ghodsia,b
aDepartment of Computer Engineering, Sharif University of Technology, Tehran, Iran
bInstitute for Research in Fundamental Sciences (IPM), Tehran, Iran
Abstract
We consider the problem of walking in an unknown street, for a robot that
has a minimal sensing capability. The robot is equipped with a sensor that
only detects the discontinuities in depth information (gaps) and can locate
the target point as enters in its visibility region. First, we propose an online
deterministic search strategy that generates an optimal search path for the
simple robot to reach the target t, starting from s. The competitive ratio
of the strategy is 9. In contrast with previously known research, the path is
designed without memorizing any portion of the scene has seen so far. Then,
we present a randomized search strategy, based on the deterministic strategy.
We prove that the expected distance traveled by the robot is at most a 5.33
times longer than the shortest path to reach the target.
Keywords:
Computational Geometry, Unknown Environment, Street
Polygon, Competitive Ratio, Simple Robot
1. Introduction
Path planning is a basic problem to almost all scopes of computer science;
such as computational geometry, online algorithms, robotics and artificial
intelligence [3]. Especially, path planning in an unknown environment for
which there is no geometric map of the scene is interesting in many real life
cases. Robot sensors is the only tool for gathering information in an unknown
∗Corresponding author
Email address: atabatabaei@ce.sharif.edu (Azadeh Tabatabaei)
URL: http://sharif.ir/~ghodsi/ (Mohammad Ghodsi )
Preprint submitted to
October 29, 2018
arXiv:1512.01784v2  [cs.CG]  8 Dec 2015
street. Amount of the information achieved from the environment depends
on the capability of the robot. Due to the importance of using simple robot,
including low cost, less sensitive to failure, robust against sensing errors
and noise, many types of path planning for simple robot have been studied
[1, 5, 9].
In this paper, we consider the problem of walking a simple robot in an
unknown street. A simple polygon P with two separated vertices s and t
is called a street if the left boundary chain Lchain and the right boundary
chain Rchain constructed on the polygon from s to t are mutually weakly
visible. In other words each point on the left chain can see at least one point
on the right chain and vice versa [6], see Figure 1. A point robot which its
sensor has a minimal capability that can only detect discontinuities in depth
information (gaps) and the target point t, starts searching the street. The
robot can locate the target as soon as it enters in its visibility region. Also,
the robot cannot measure any angles or distances or infer its position, see
Figure 1. The goal is to reach the target t using the information gathered
through its sensor, starting from s such that the traveled path by the robot
is as short as possible.
In order to evaluate the efficiency of a search strategy for the robot, we
use the notation of the competitive analysis. The competitive analysis for a
strategy that leads the robot is the ratio of the expected distance traversed by
the robot over the shortest distance from s to t, in the worst case. In previous
research, Tabatabaei and Ghodsi gave a deterministic algorithm for the sim-
ple robot to reach the target t in the street, starting from s. The robot using
some pebbles and memorizing some portion of the street has seen, explores
the street. The target t is achieved such that the traversed path is at most
11 times longer than the shortest by using one pebble. Also they showed,
allowing use of many pebbles reduces the factor to 9 [10]. Furthermore, they
presented a randomized strategy in [11].
In this paper, first, we present a deterministic strategy using the location
of two special gaps which are updated during the walking. The robot achieves
the target, without memorizing environment and without using pebbles. The
search path is optimal; length of the generated path is at most 9 times longer
than shortest path. Then, we present a randomized strategy that generate a
search path similar to the deterministic one, but the worst case ratio of the
expected distances traveled by the robot to the shortest path is 5.33.
Related Works: Klein proposed the first competitive algorithm for
walking in streets problem for a robot that was equipped with a 360 degrees
2
R
inflection   ray
R
bitangent 
complement
R
L
(b)
(c)
(d)
(e)
R
R
R
L
R
bitangent 
complement
L
R
L
L
bitangent 
complement
R
R
(a)
R
R
L
R
R
L
R
LR
L
R
R
L
R
L
R
L
R
R
LL
R
L
R
R
R
R
R
bitangent 
complement
(f)
Lchain
Rchain
s
t
gr
gl
Figure 1: Street polygons, and the dynamically changes of the gaps as the robot walks
towards a gap in street polygon. The dark circle is the location of the robot, and squares
and other circles denote primitive and non-primitive gaps respectively. (a) Existing gaps
at the start point. (b) A split event. (c) A disappearance event. (d) An appearance event.
(e) Another split event. (f) A merge event.
vision system [6]. Also, Icking et al. presented an optimal search strategy for
the problem with the competitive factor of
√
2 [4]. Many online strategies
for patrolling unknown environment such as street, generalized street, and
star polygon are presented in [3, 7].
The limited sensing model (gap sensor) that our robot is equipped with,
in this research, was first introduced by Tovar et al. [12]. They offered Gap
Navigation Tree (GNT) to maintain and update the gaps seen along a navi-
gating path. A strategies, using GNT for exploring unknown environments,
presented in [8].
Another minimal sensing model was presented by Suri et al. [9]. They
assumed that the simple robot can only sense the combinatorial (non-metric)
properties of the environment.
The robot can locate the vertices of the
polygon in its visibility region, and can report if there is a polygonal edge
between them. Despite of the minimal ability, they showed that the robot
can accomplish many non-trivial tasks. Then, Disser et al. empowered the
robot with a compass to solve the mapping problem in polygons with holes
[2].
3
2. preliminaries
2.1. The Sensing Model and motion primitives
At the start point, the point robot reports a cyclically ordered of discon-
tinuities in the depth information (gaps) in its visibility region. Each gap
has a label of L or R which displays the direction of the part of the scene
that is hidden behind the gap, see Figure 1.
The robot can orient its heading to each gap and moves towards the gap
in an arbitrary number of steps. Also the robot moves towards the target as
they enter in its visibility region.
While the robot moves, combinatorial changes occur in the visibility re-
gion of the robot that they are called critical events. There are four types
of critical events: appearances, disappearances, merges, and splits of gaps.
Appearance and disappearance events occur when the robot crosses inflec-
tion rays. An appeared gap, during the movement, corresponds to a portion
of the environment that was already visible, but now is not visible. such the
gaps are called primitive gaps and the other gaps are non-primitive gaps.
Merge and split events occur when the robot crosses bitangent, as illustrated
in Figure 1.
2.2. Known Properties
At each point of the search path, if the target is not visible, the robot
reports a set of left and right gaps (l-gap and r-gap for abbreviation). Let
gl be the most advanced non-primitive left gap (l-gap) and gr be the most
advanced non-primitive right gap (r-gap) [10], see Figure 1. The two gaps
have a fundamental role in path planning for the simple robot.
Theorem 1. [4, 10] While the target is not visible, it is hidden behind one
of the two gaps, gl or gr.
From Theorem 1, if there exist only one of the two gaps (gr and gl) then
the goal is hidden behind of the gap. Thus, there is no ambiguity and the
robot moves towards the gap, see Figure 2(a). When both of gr and gl exist,
a funnel case arises, see Figure 2(b). At each funnel case, usually, a detour
from the shortest path is unavoidable.
4
2.3. Essential Information
Whatever we maintain during the search strategy is location of gl and gr.
As the robot moves in the street, the critical events that change the structure
of the robot’s visibility region may dynamically change gl and gr. Also, by
the robot movement, a funnel case may end or a new funnel may start. We
refer to the point, in which a funnel ends a critical point of the funnel.
The following events update the location of gl and gr as well as a funnel
situation when the robot moves towards gl or gr.
1. When gr/gl splits into gr/gl and another r-gap/l-gap, then gr/gl will
be replaced by the r-gap/l-gap, (point 1 in Figure 2(b)).
2. When gr/gl splits into gr/gl and another l-gap/r-gap, then l-gap/r-gap
will be set as gl/gr. This point is a critical point in which a funnel
situation ends, (point 2 in Figure 2(b).
3. When gl or gr disappears, the robot may achieve a critical point in
which a funnel situation ends, (point 1 in Figure 2(b)).
Note that the split and disappearance events may occur concurrently, (point 3
in Figure 2(b)). Furthermore, by moving towards gr and gl, these gaps never
merge with other gaps.
3. Algorithm
Now, we present our strategy for searching the street, from s to t. Since
the target is constantly behind one of gr and gl, during the searching, the
location of them is maintained and dynamically updated as explained in the
previous section.
3.1. A deterministic strategy
At each point of the search path, especially at the start point s, there are
two cases:
• If only one of the two gaps (gr and gl) existsor, or they are collinear
then the goal is hidden behind the gap. The robot moves towards the
gap until the target is achieved or a funnel situation arises, see Figure
2(a).
5
• If there is a funnel case, in order to bound the detour, the robot moves
towards gr and gl alternatively. At each stage i ∈{1, 3, 5, ...}, the robot
moves ai step(s) towards gr, and at each stage i ∈{2, 4, 6, ...}, the robot
moves ai steps towards gl such that: a1 = 1, a2 = 3, and ai = 2ai−1 for
i ≥3.
The robot continues moving towards gr or gl alternatively until a critical
point of the funnel is achieved. At the point, one of gr or gl disappears,
or gr and gl are collinear. So, the robot moves along the existing gap
direction until the target is achieved or a new funnel situation arises,
as illustrated in Figure 2(b).
3.1.1. The randomized strategy
Now, we present a randomized search strategy based on the above deter-
ministic strategy. At each point of the search path that only one of gr or
gl exists, or the two gaps are collinear, the robot moves along the existing
direction, similar the deterministic strategy. In the funnel case, first, the
robot chooses a random real uniformly variable from [0, 1) and sets length
of its step by 2ε. Then, it chooses a uniform random variable X from {0, 1}
to select the direction towards gr or gl. If X is 1/0, at each odd stage i the
robot moves ai steps towards gr/gl, and at each even stage i, the robot moves
ai steps towards gl/gr (an in the previous section).
Similar to the deterministic strategy, the robot continues moving towards
gr and gl in the number of steps alternatively until the funnel case ends.
At each funnel, the actual randomization occurs only at first step for
specifying length of steps, and for determining the direction of the movement.
In the next section, we show the expected performance of our randomization
algorithm is better than the performance of our deterministic algorithm.
3.2. Correctness and Analysis
Throughout the searching, the robot path coincides with the shortest
path unless a funnel case arises. Then, in order to prove the competitive
ratio of our strategy, we compare length of the path and shortest path in a
funnel case.
For analyzing the strategy, we inspire from the doubling strategy by
Baeza-Yates et al.
[1]. In the strategy a robot moves back and forth on
a line such that the distance to the start point doubles at each stage until
the target is reached.
6
t
Critical point
s
j
(a)
3
1
Critical point
s
t
j
(b)
1
t
2
(c)
1
2
s
Figure 2: The bold path is the robot search path, and the dotted path is shortest
path. (a) There is only gr. Illustration of the algorithm for two opening angles,
small and large angles respectively in (b) and (c).
Theorem 2. [1] The doubling strategy for searching a point on a line has a
competitive factor of 9, and this is optimal.
Opening angle, the angle between gr and gl, is always smaller than π [4].
The simple robot walks towards within the opening angle. An important
attribute of the angle is characterized in the following lemma.
Lemma 3. By our strategy, the detour from shortest path for small opening
angle, in the funnel case, is shorter than detour for large opening angle.
Proof. In each funnel case, the robot moves some steps towards gr or gl,
then changes its direction and moves some steps towards the other. In the
alternative movement, one of the directions is correct and the other is a
deviation. Clearly for large opening angle the deviation is greater, as shown
in Figure 2(c).
Now, we can prove, the competitive factor of our deterministic strategy.
Theorem 4. Our deterministic strategy guarantees a path at most 9 times
longer than shortest path in the street from s to t.
Proof. The robot always moves towards gr and gl while the gapas update via
splitting by crossing over bitangents, as explained in 2.3. Numbers of the
7
events are finite, so the target is achieved in finite time. From Lemma 3,
there is further deviation from shortest path for large opening angles. The
angle never exceeds π. Then, for computing a competitive factor, we consider
it equals π. Starting from s, the robot moves a1 = 1 step towards gr, then
moves a2 = 1 + 2 steps towards gl, and again moves forth a3 = 2a2 = 2 + 22
steps towards gl, moves back a4 = 2a3 = 22 + 23 steps towards gl, and so on.
In other words the robot moves back and forth on the line that contain gl
and gr such that the distance to the start point s doubles at each stage until
the critical point is reached. By Theorem 2 competitive factor for the search
strategy is 9.
Kao, Reif, and Tate [5] offer a competitive randomized algorithm for
searching on a line. The procedure is similar to the doubling strategy; the
first step is characterized as a random number, and lengths of subsequent
steps is multiplied by r. The competitive factor of their randomized strategy
is 1 + (1 + r)/ ln r. A similar argument to the proof of theorem 4 shows that
when the opening angle is π, our randomized search strategy coincides with
Kao et al. strategy to search a point on a line with r = 2. So, the theorem
below is immediately satisfied.
Theorem 5. The randomized strategy generates a search path to achieve
target t in the street, starting from s, with a competitive ratio of 5.33.
4. Conclusions
In this paper we have developed two similar search strategies for walking
in streets problem for a simple robot. The point robot can only detect the
gaps and the target in the environment.
Also the robot can only moves
towards the gaps. Our deterministic strategy achieves optimal competitive
factors of 9, and is simpler than previous known result. The other strategy is
a randomized strategy based on the deterministic strategy that has a better
performance. Expected length of the generated path by the random strategy
is at most 5.33 times longer than shortest path. It would be absorbing if
there is an optimal randomized search strategy.
References
[1] Baezayates, R. A., Culberson, J. C., Rawlins, G. J. Searching in the
plane. Information and Computation 106(2): 234–252, 1993.
8
[2] Disser, Y., Ghosh, S. K., Mihalk, M., Widmayer, P. Mapping a polygon
with holes using a compass. Theoretical Computer Science, 2013.
[3] Ghosh, Subir Kumar, and Rolf Klein Online algorithms for searching
and exploration in the plane. Computer Science Review 4.4 (2010): 189-
201.
[4] Icking, C., Klein, R., Langetepe, E. An optimal competitive strategy
for walking in streets. In STACS 99, Springer Berlin Heidelberg, (pp.
110–120), 1999.
[5] Kao, Ming-Yang, John H. Reif, and Stephen R. Tate. Searching in an
unknown environment: An optimal randomized algorithm for the cow-
path problem. Information and Computation 131(1): 63–79,1996.
[6] Klein, R. Walking an unknown street with bounded detour. Computa-
tional Geometry, 1(6): 325–351, 1992.
[7] Lpez-Ortiz, Alejandro, and Sven Schuierer. Lower bounds for streets and
generalized streets. International Journal of Computational Geometry
and Applications 11.04 (2001): 401-421.
[8] Lopez-Padilla, R., Murrieta-Cid, R., LaValle, S. M. Optimal Gap Nav-
igation for a Disc Robot.
In Algorithmic Foundations of Robotics,
Springer Berlin Heidelberg, (pp 123–138), 2012.
[9] Suri, S., Vicari, E., Widmayer, P. Simple robots with minimal sensing:
From local visibility to global geometry.
The International Journal of
Robotics Research, 27(9): 1055–1067, 2008.
[10] Tabatabaei, Azadeh, and Mohammad Ghodsi. Walking in Streets with
Minimal Sensing. Journal of Combinatorial Optimization, 30(2): 387-
401, 2015.
[11] Tabatabaei, Azadeh, and Mohammad Ghodsi. Randomized Strategy for
Walking in Streets for a Simple Robot. EuroCG 2015, Ljubljana, Slove-
nia, March 16–18, 2015.
[12] Tovar, B., Murrieta-Cid, R., LaValle, S. M. Distance-optimal navigation
in an unknown environment without sensing distances. Robotics IEEE
Transactions 23(3): 506–518, 2007.
9