Page 120 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

BASIC ALGORITHMS 95

where D is the distance (Start, Target), and p i refers to perimeters of obstacles
that intersect the M-line (straight line segment (Start, Target)). This means Bug2
is convergent.
Proof: Any path can be looked at as consisting of two parts: (a) straight-line
segments of the M-line between the obstacles that intersect it and (b) path seg-
ments that relate to walking around obstacle boundaries. Because of inequality
(3.8), the sum of the straight line segments will never exceed D.Astopath
segments around obstacles, there is an upper bound guaranteed by Lemma 3.3.4
for each obstacle met by MA on its path: No more than n i /2 passings along the
same segment of the obstacle boundary will take place. Because of Lemma 3.3.3
(see its proof), only those obstacles that intersect the M-line should be counted.
Summing up the straight-line segments and segments that correspond to walking
around obstacles, obtain (3.9). Q.E.D.

Theorem 3.3.3 suggests that in some “bad” scenes, under algorithm Bug2, MA
may be forced to go around obstacles any large, albeit finite, number of times.
An important question, therefore, is how typical such “bad” scenes are.
In particular, other things being equal, what characteristics of the scene influ-
ence the length of the path? Theorem 3.3.4 and its corollary below address this
question. They suggest that the mutual position of point S, point T , and obstacles
in the scene can affect the path length rather dramatically. Together, they signif-
icantly improve the upper bound on the length of paths generated by Bug2—in
out-position scenes in general and in scenes with convex obstacles in particular.
Theorem 3.3.4. Under algorithm Bug2, in the case of an out-position scene, MA
will pass any point of an obstacle boundary at most once.

In other words, if the mutual position of the obstacle and of points S and T sat-
isfies the out-position definition, the estimate on the length of paths generated by
Bug2 reaches the universal lower bound (3.1). That is a very good news indeed.
3
Out-position situations are rather common for mobile robots. We know already
that in some situations, algorithm Bug2 is extremely efficient and traverses only
a fraction of obstacle boundaries. Now the theorem tells us that as long as the
robot deals with an out-position situation, even in the most unlucky case it will
not traverse more than 1.5 times the obstacle boundaries involved.

Proof: Figure 3.9 is used to illustrate the proof. Shaded areas in the figure cor-
respond to one or many obstacles. Dashed boundaries indicate that obstacle
boundaries in these areas can be of any shape.
Consider an obstacle met by MA on its way to the Target, and consider an
arbitrary point Q on the obstacle boundary (not shown in the figure). Assume
that Q is not a hit point. Because the obstacle boundary is a simple closed curve,
the only way that MA can reach point Q is to come to it from a previously

3 We will see later that out-position situations are a rarity for arm manipulators.