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

VISION AND MOTION PLANNING 113

T T
A

Q

C
r u

S
Figure 3.15 Scene 1: Path generated by VisBug-21. The radius of vision r v is larger
than that in Figure 3.14.

holds for any i. The proof is by induction. Consider the initial stage, i = 0; it
corresponds to C 0 = S. Clearly, |ST 0 |≤ [ST 0 ]. This can be written as {SC 0 }+
|C 0 T 0 |≤ [ST 0 ], which corresponds to the inequality (3.15) when i = 0. To pro-
ceed by induction, assume that inequality (3.15) holds for step (i − 1) of the
path, i> 1:

{SC i−1 }+|C i−1 T i−1 |≤ [ST i−1 ] (3.16)

Each step of the robot’s path takes place in one of two ways: either C i−1 = T i−1
or C i−1 = T i−1 . The latter case takes place when the robot moves along the
locally convex part of an obstacle boundary; the former case comprises all the
remaining situations. Consider the first case, C i−1 = T i−1 . Here the robot will
take a step of length |C i−1 C i | along a straight line toward T i−1 ; Eq. (3.16) can
thus be rewritten as

{SC i−1 }+|C i−1 C i |+ |C i T i−1 |≤ [ST i−1 ] (3.17)

In (3.17), the first two terms form {SC i },and so

{SC i }+|C i T i−1 |≤ [ST i−1 ] (3.18)