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

122 MOTION PLANNING FOR A MOBILE ROBOT

If points {P } on the M-line are identified such that |S T | < |QT|, S ∈{P },

then find the point S ∈{P } that produces the shortest distance |S T |;define

T i = S ;gotoStep 2.

Else the procedure stops.
Performance and Convergence of VisBug-22. The algorithm’s performance
is demonstrated in Figures 3.14 and 3.21; the values of radius of vision r v used are
the same as in examples for VisBug-21 (Figures 3.14 and 3.15). Compare these
with the performance of algorithm Bug2 in the same scene (Figure 3.13). As one
can see from Figure 3.14, algorithms VisBug-21 and VisBug-22 can sometimes
generate identical paths. This is not so in general. Also, neither algorithm can be
said to be superior to the other in all scenes. For example, in one scene algorithm
VisBug-21 performs better (Figure 3.15) than algorithm VisBug-22 (Figure 3.21),
but luck switches to VisBug-22 in another scene shown in Figure 3.23.
Convergence of algorithm VisBug-22 follows simply from the fact that all the

starting points, S , of the successive quasi-Bug2 path segments lie on the M-line,
and they are organized in such a way as to produce a finite sequence of distances
shrinking to T :

|S T | > |S T | > |S T | > ·· · (3.26)
2
3
1

where points S are numbered in the order of their appearance.

T

r u

S
Figure 3.21 Scene 1. The path generated by algorithm VisBug-22. The radius of vision
r v here is larger than that in Figure 3.14, and is equal to that in Figure 3.15.