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

186 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

(robot) around simple closed curves. The key property will then be deduced: For
a two-link arm, no matter how complex the arm motion around an actual physical
obstacle in W-space, the corresponding virtual boundary in C-space presents a
simple curve—that is, a curve with no self-intersections and double points. This
will be shown to be true for each of the arms in Figure 5.1.
With this property in hand, by transforming the motion planning problem from
W-space to C-space, we will effectively make our problem similar to the one
that was tackled in Chapter 3 for mobile robots. In fact, on a certain level of
generalization, both problems look identical. The actual algorithms will differ
due to a number of new issues that need to be worked out. Still, understanding
the Bug family algorithms from Chapter 3 will help one grasp the algorithms for
robot arms that we are about to develop.
We can now sketch the idea behind a motion planning algorithm for a planar
robot arm manipulator. It is easier to describe the operation in C-space; the
actual operation in W-space proceeds accordingly. As one will notice, the sketch
sounds much like the algorithm Bug2; deviations and complexities will be added
later.
At the beginning, the C-space arm image point moves along a simple M-line,
which is a desired path from point S to point T , an equivalent of the straight-line
M-line for the mobile robot (Section 3.3). During this motion, when (in W-space)
some point of the arm body meets an obstacle, in C-space this corresponds
to the image of M-line intersecting the obstacle’s virtual boundary. The point
of intersection is said to define a hit point, H j ,where j is the running index
enumerating such points.
We will show below that the virtual boundary is a simple curve, a curve with
no self-intersections or double points. This being so, at the hit point the arm has a
simple choice: to walk along the virtual boundary in one or the opposite direction
along the curve. Since no information is available beforehand as to which of the
two directions is better, one direction, called the local direction, will be chosen
once and for all.
While following the obstacle virtual boundary, the arm may meet the M-line
again. If it does, and if this occurs at a distance (measured appropriately along
the M-line) from point T shorter than the distance from the latest hit point H j
to T , the arm will define a leave point, L j . Hit and leave points will play an
important role in the path planning procedure. We will see below that these points
come in pairs, (H j , L j ), j = 1, 2,. .. . For convenience, denote L o = S,Start,
with no corresponding H o . The motion planning algorithm proper, the proof of
its convergence, and the test for target reachability will emerge from our analysis
of the described scheme and of C-space properties.
Similar to the mobile robot case (Chapter 3), under our scheme the arm will
need no beforehand information about the obstacles in order to move properly.
The C-space presentation is used primarily for the analysis, the algorithm devel-
opment, and the proof of convergence. No explicit mapping of any kind from
W-space to C-space and no explicit calculation of C-space will ever take place
before or during the actual arm motion.