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

112 MOTION PLANNING FOR A MOBILE ROBOT

T

r u

S
Figure 3.14 Scene 1: Path generated by algorithms VisBug-21 or VisBug-22. The radius
of vision is r v .

Analysis of VisBug-21. Examples shown in Figures 3.14 and 3.15 demonstrate
the effect of radius of vision r v on performance of algorithm VisBug-21. (Com-
pare this with the Bug2 performance in the same environment, Figure 3.13). In
the analysis that follows, we first look at the algorithm performance and then
address the issue of convergence. Since the path generated by VisBug-21 can
diverge significantly from the path that would be produced under the same con-
ditions by algorithm Bug2, it is to be shown that the path-length performance of
VisBug-21 is never worse than that of Bug2. One would expect this to be true,
and it is ensured by the following lemma.

Lemma 3.6.1. For a given scene and a given set of Start and Target points,
the path produced by algorithm VisBug-21 is never longer than that produced by
algorithm Bug2.

Proof: Assume the scene and start S and target T points are fixed. Consider the
robot’s position, C i , and its corresponding intermediate target, T i ,atstep i of the
path, i = 0, 1,... . We wish to show that the lemma holds not only for the whole
path from S to T , but also for an arbitrary step i of the path. This amounts to
showing that the inequality
{SC i }+|C i T i |≤ [ST i ] (3.15)