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

286 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

below). By treating links’ interaction with obstacles individually and by making
use of the information on what specific part—front or rear—of a given link is
currently in contact with obstacles, the path planning algorithm takes advantage
of the obstacle monotonicity property. Because this information is not available
in C-space, the following holds:

Information Loss due to Space Transition. Information is lost in the space tran-
sition W → C. Since some of this information—namely, the location of contact
points between the robot arm and obstacles—is essential for the sensor-based
planning algorithm, from time to time the algorithm may need to utilize some
information specific to W-space only.

We will now consider some elemental planar interactions of arm links with
obstacles, and we will show that if a path from start to target does exist, then a
combination of elemental motions can produce such a path. Define the following:

• Type I obstacle corresponds to a W-or C-obstacle that results from the
interaction of link l 1 with a physical obstacle.
• Type II obstacle corresponds to a W-or C-obstacle that results from the
interaction of link l 2 with a physical obstacle.
• Type III obstacle corresponds to a W-or C-obstacle that results from the
interaction of link l 3 with a physical obstacle.
We will use subscripts “+”and “−” to further distinguish between obstacles that
interact with the front and rear part of a link, respectively. For example, a Type
III + obstacle refers to a C-obstacle produced by interaction of the front part of
link l 3 with some physical obstacle.
In the next section we will analyze separately the interaction of each link
with obstacles. Each time, three cases are considered: when an obstacle interacts
with the front part, the rear part, or simultaneously with both parts of the link
in question. We will also consider the interaction of a combination of links with
obstacles, setting the foundation for the algorithm design.

Interaction of Link l 1 with Obstacles—Type I Obstacles. Since, according
to our model, sliding along an obstacle does not constitute an interference with
the link l 1 motion, we need to consider only those cases where the link meets
an obstacle head-on. When only the front end of link l 1 is in contact with an

obstacle—say, at the joint value l —a Type I + obstacle is produced, which
1
extends from C-space floor to ceiling and side to side (see Figure 6.6) which
effectively reduces the C-space cubicle by the volume (l 1max − l ) · l 2max · l 3max .

1
A similar effect appears when only the rear end of link l 1 interacts with an

obstacle—say, at a joint value l . Then the C-space is effectively decreased by
1
the volume l · l 2max · l 3max . Finally, a simultaneous contact of both front and

1

rear ends with obstacles at a value l corresponds to a degenerate case where no
1
motion of link l 1 is possible; that is, the C-obstacle occupies the whole C-space.
Formally the property of Type I obstacle monotonicity is expressed as follows: