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

202 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

curves of a Type II obstacle have the same range (see Figures 5.8b to 5.8e).
For a given obstacle, therefore, the term “arm joints range” is equivalent to the
term obstacle range. For a Type II obstacle, its range is (n 1 · 2π, n 2 · 2π), with
either n i = 0, |n 3−i |= 1 (Figures 5.8b and 5.8c) or |n i |= 1, |n 3−i |= 1, 2,...
(Figures 5.8d and 5.8e); i = 1, 2. Numbers n i uniquely represent the range of an
obstacle.
After the arm has passed around an obstacle, the range accumulated in counters
C 1 ,C 2 is, therefore, an indicator of the obstacle’s type. If, after completing a
closed curve, the contents of the counters is (0, 0), then the obstacle in question
is of Type I and thus the whole virtual boundary has already been traversed. If,
on the other hand, the range of the closed curve is different from (0, 0), then the
obstacle is of Type II and hence there must be another closed curve somewhere
that corresponds to the same obstacle.
This observation can be used in the reachability test that we will need in the
complete motion planning algorithm. The mechanism of the test is very similar
to that in the Bug2 algorithm (Section 3.3.2). Namely, in the case of a Type
I obstacle, if, after having defined a leave point, the arm returns back to it
without ever meeting the M-line and without having defined the next hit point,
this indicates that the target position cannot be reached. This may happen, for
example, if the obstacle forms a ring around the target position. A similar idea
works for the Type II obstacles: If the arm traverses both closed curves of a
Type II virtual obstacle without ever meeting the M-line and without defining
the next hit point, the target is not reachable. These mechanism will be used in
the algorithm’s reachability test.
We emphasize that in no way does the above discussion imply that traversing
closed curves of obstacle boundaries is a necessary part of the motion planning
algorithm. More often than not, the robot will be passing only parts of obstacles
that it encounters on its way to the target position. The test above is needed
for algorithm completeness: If once in a while the analysis above is needed, the
algorithm will provide the mechanism for it.

M-Line and Path Planning. How do we choose the M-line? If the arm encoun-
ters no obstacles on its way, the arm endpoint will proceed directly from point
S to point T along the M-line. It is desirable, then, to have a simple and shorter
M-line, such that one could easily determine whether a given point does or does
not lie on it. In the case of planning algorithms for mobile robots (Section 3.3),
we chose a straight line (S, T ) for the M-line.
An M-line can be defined for the RR arm in a number of ways. One option is
a straight line (S, T ) in W-space (see Figures 5.3 and 5.6). Another reasonable
choice for M-line would be a “uniform descent” curve in W-space, described
in polar coordinates as R = p · ϕ + q,where R is the distance from the arm
endpoint to the fixed base O of the arm (Figure 5.2), and ϕ is the angular
position of the arm endpoint relative to some zero axis passing through the base
O. This is a straight line in the plane of variables (R, ϕ), 0 ≤ ϕ ≤ 2π. Knowing