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

284 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

From the standpoint of motion planning, the importance of these facts is in
that the local information from the arm’s contacts with obstacles allow one to
infer some global characteristics of the corresponding C-obstacle that help avoid
directions of motion leading to dead ends and thus avoid an exhaustive search.
Whereas the resulting path planning algorithm is used in the workspace, with-
out computations of C-space, it can be conveniently sketched in terms of C-space,
as follows. If the C-point meets no obstacles on its way, it will move along the
M-line, and with no complications the robot will happily arrive at the target
position T .Ifthe C-point does encounter an obstacle, it will start moving along
the intersection curve between the obstacle and one of the planes, M-plane or
V-plane. The on-line computation of points along the intersection curve is easy:
It uses the plane’s equation and local information from the arm sensors.
If during this motion the C-point meets the M-line again at a point that satisfies
some additional condition, it will resume its motion along the M-line. Otherwise,
the C-point may arrive at an intersection between two obstacles, a position that
corresponds to two links or both front and rear parts of the same link contacting
obstacles. Here the C-point can choose either to move along the intersection
curve between the plane and one of the obstacles, or move along the intersection
curve between the two obstacles. The latter intersection curve may lead the C-
point to a wall, a position that corresponds to one or more joint limits. In this
case, depending on the information accumulated so far, the C-point will conclude
(correctly) either that the target is not reachable or that the direction it had chosen
to follow the intersection curve would lead to a dead end, in which case it will
take a corrective action.
At any moment of the arm motion, the path of the C-point will be constrained
to one of three types of curves, thus reducing the problem of three-dimensional
motion planning to the much simpler linear planning:
• The M-line
• An intersection curve between a specially chosen plane and the surface of
a C-obstacle
• An intersection curve between the surfaces of two C-obstacles
To ensure convergence, we will have to show that a finite combination of such
path segments is sufficient for reaching the target position or concluding that the
target cannot be reached. The resulting path presents a three-dimensional curve
in C-space. No attempt will be made to reconstruct the whole or part of the space
before or during the motion.
Since the path planning procedure is claimed to converge in finite time, this
means that never, not even in the worst case, will the generated path amount to
an exhaustive search.
An integral part of the algorithm is the basic procedure from the Bug family
that we considered in Section 3.3 for two-dimensional motion planning for a
point automaton. We will use, in particular, the Bug2 procedure, but any other
convergent procedure can be used as well.