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

114 MOTION PLANNING FOR A MOBILE ROBOT

At point C i the robot will define the next intermediate target, T i .Now addto
(3.18) the obvious inequality |T i−1 T i |≤ [T i−1 T i ]:

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

By the Triangle Inequality, we have

|C i T i |≤|C i T i−1 |+ |T i−1 T i | (3.20)

Therefore, it follows from (3.19) and (3.20) that

{SC i }+|C i T i |≤ [ST i ] (3.21)

which proves (3.15).
Consider now the second case, C i−1 = T i−1 . Here the robot takes a step of
length (C i−1 C i ) along the obstacle boundary (the Bug2 path, [C i−1 C i ]). Equation
(3.16) becomes

{SC i−1 }+ [C i−1 C i ] ≤ [SC i−1 ] + [C i−1 C i ] (3.22)

where the left-hand side amounts to {SC i } and the right-hand side to [SC i ]. At
point C i , the robot will define the next intermediate target, T i .Since |C i T i |≤
[C i T i ], inequality (3.22) can be written as

{SC i }+|C i T i |≤ [SC i ] + [C i T i ] = [ST i ] (3.23)

which, again, produces (3.15). Since, by the algorithm’s design, at some finite i,
C i = T ,then

{ST }≤ [ST ] (3.24)

which completes the proof. Q.E.D.

One can also see from Figure 3.15 that when r v goes to infinity, algorithm
VisBug-21 will generate locally optimal paths, in the following sense. Take two
obstacles or two parts of the same obstacle, k and k + 1, that are visited by the
robot, in this order. During the robot’s passing around obstacle k, once a point
on obstacle k + 1 is identified as the next intermediate target, the gap between
k and k + 1 will be traversed along the straight line, which presents the locally
shortest path.
When defining its intermediate targets, algorithm VisBug-21 could sometimes
use points on the M-line that are not necessarily contiguous to the prior intermedi-
ate targets. This would result in a more efficient use of robot’s vision: By “cutting
corners,” the robot would be able to skip some obstacles that intersect the M-line
and that it would otherwise have to traverse. However, from the standpoint of
algorithm convergence, this is not an innocent operation: It is important to make