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

206 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

M-line, and, after having examined the contents of the counters C 1 and C 2 ,
concludes that it is dealing with a Type II obstacle. Now the arm needs to explore
the second closed curve of the virtual boundary. This second closed curve must
lie somewhere in a direction “opposite” to that in which the first closed curve had
been spotted. Such “opposite” directions are provided by the complementary M k -
lines (Figure 5.5). The notion of M k -line complementarity over a certain angle θ i
provides a way of selecting M k -lines. No more than two complementary M-lines
will have to be tried to complete the task. The outcome of processing the first
closed curve of the virtual boundary is one of these three cases:

1. The accumulated range is (0, n 2 ); |n 2 |≥ 1–an integer. This case is shown
in Figure 5.8b: The arm starts at S, moves along the line (S, T ) (which hap-
pens to correspond to the change of θ 1 in the positive direction), encounters
an obstacle, goes around one of its closed curves, and concludes that the
further motion along M 1 -line in this direction is impossible. On the other
hand, using the opposite (in this example, the negative) direction of change
of θ 1 guarantees reaching the second closed curve of the virtual obstacle.
How would the arm choose the right M-line for this stage? According to
(5.2), such direction can be realized with either an M 3 -line or an M 4 -line
(Figure 5.5). Because no additional information is available, for example,
the shortest of these will be chosen. (There is, of course, no guarantee that
the chosen M-line is better than the other possible choice.)
2. The accumulated range is (n 1 ,0); |n 1 |≥ 1. This case could appear, for
example, in Figure 5.8c. This situation is symmetric to the previous one
except that it relates to angle θ 2 . The opposite direction of change for θ 2
can be realized with either M 2 -line or M 4 -line (Figure 5.5). The shortest
of these will be chosen.
3. The accumulated range is (n 1 ,n 2 ); |n i |≥ 1 (Figures 5.8d and 5.8e). Again,
further motion along M 1 -line is impossible. Any one of the segments M 2 ,
M 3 ,or M 4 can be used as a new M-line. The shortest of these will be
chosen.

Where would the arm start for the exploration of the second closed curve?
Since no information about the obstacle’s second closed curve has been accu-
mulated so far, one point to start with the new M-line is S. If neither of the two
M-lines brings the arm to the target—that is, if point T has not been reached after
exploration of the obstacles both closed curves—the target is not reachable. Using
in the worst case two M-lines instead of one represents the topological distinc-
tion of motion planning on the torus as compared to the plane. With the addition
of complementary M-lines, the convergence theorems developed in Section 3.3
for the Bug family algorithms can be used to ensure that our algorithm for the
revolute–revolute arm terminates.

Local Cycles. As we learned in Section 3.3, a planar sensor-based motion plan-
ning procedure for a mobile robot can create local cycles in the path. Local cycles