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

84 MOTION PLANNING FOR A MOBILE ROBOT

(D + i p i ) to its both sides. With a little manipulation, we obtain

2 2
p i + D + W − W ≥ D + p i − δ (3.5)
i i
Comparing (3.3) and (3.5), observe that (3.1) is satisfied.

This exhausts all possible cases of path generation by the algorithm X. Q.E.D.

We conclude this section with two remarks. First, by appropriately select-
ing multiple virtual obstacles, Theorem 3.2.1 can be extended to an arbitrary
number of obstacles. Second, for the lower bound (3.1) to hold, the constraints
on the information available to MA can be relaxed significantly. Namely, the
only required constraint is that at any time moment MA does not have complete
information about the scene.
We are now ready to consider specific sensor-based path planning algorithms.
In the following sections we will introduce three algorithms, analyze their per-
formance, and derive the upper bounds on the length of the paths they generate.

3.3 BASIC ALGORITHMS

3.3.1 First Basic Algorithm: Bug1
This procedure is executed at every point of the MA’s (continuous) path [17,
58]. Before describing it formally, consider the behavior of MA when operating
under this procedure (Figure 3.2). According to the definitions above, when on
its way from point S (Start) to point T (Target), MA encounters an ith obstacle, it
defines on it a hit point H i ,i = 1, 2,... . When leaving the ith obstacle in order
to continue toward T ,MAdefines a leave point L i . Initially i = 1, L 0 = S.
The procedure will use three registers—R 1 , R 2 ,and R 3 —to store intermediate
information. All three are reset to zero when a new hit point is defined. The use
of the registers is as follows:

• R 1 is used to store coordinates of the latest point, Q m , of the minimum
distance between the obstacle boundary and point T ; this takes one com-
parison at each path point. (In case of many choices for Q m , any one of
them can be taken.)
• R 2 integrates the length of the ith obstacle boundary starting at H i .
• R 3 integrates the length of the ith obstacle boundary starting at Q m .

We are now ready to describe the algorithm’s procedure. The test for target
reachability mentioned in Step 3 of the procedure will be explained further in
this section.