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

BASIC ALGORITHMS 97

j
because MA is known to have walked along the whole segment (L j−1 ,H ).
j
If the crossing occurs within the interval (H ,T ), then at the crossing point
j
MA would define the corresponding leave point, L , and start moving along
the line (S, T ) toward the target T until it defined the next hit point, H j+1 ,
j
j
or reached the target. Therefore, between points H and L , MA could not
have reached into the right semiplane of the M-line (see Figure 3.9).
j
Since the above argument holds for any Q and the corresponding H , we con-
clude that in an out-position case MA will never cross the interval (Start, Target)
into the right semiplane, which prevents it from producing local cycles. Q.E.D.
So far, no constraints on the shape of the obstacles have been imposed. In
a special case when all the obstacles in the scene are convex, no in-position
configurations can appear, and the upper bound on the length of paths generated
by Bug2 can be improved:

Corollary 3.3.4. If all obstacles in the scene are convex, then in the worst case
the length of the path produced by algorithm Bug2 is

P = D + p i (3.10)
i

and, on the average,

P = D + 0.5 · p i (3.11)
i
where D is distance (Start, Target), and p i refer to perimeters of the obstacles
that intersect the straight line segment (Start, Target).

Consider a statistically representative number of scenes with a random distri-
bution of convex obstacles in each scene, a random distribution of points Start
and Target over the set of scenes, and a fixed local direction as defined above.
The M-line will cross obstacles that it intersects in many different ways. Then,
for some obstacles, MA will be forced to cover the bigger part of their perimeters
(as in the case of obstacle ob 1 , Figure 3.5); for some other obstacles, MA will
cover only a smaller part of their perimeters (as with obstacle ob 2 , Figure 3.5).
On the average, one would expect a path that satisfies (3.11). As for (3.10),
Figure 3.7 presents an example of such a “noncooperating” obstacle. Corol-
lary 3.3.4 thus ensures that for a wide range of scenes the length of paths
generated by algorithm Bug2 will not exceed the universal lower bound (3.1).

Test for Target Reachability. As suggested by Lemma 3.3.4, under Bug2 MA
j
may pass the same point H of a given obstacle more than once, producing a
finite number p of local cycles, p = 0, 1, 2,... . The proof of the lemma indicates