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

INTRODUCTION 185

W-Space. The arm operates in its workspace (W-space), which is defined in the
plane. The W-space boundaries depend on the arm configuration and dimensions
of its links. The arm’s position in W-space is defined by positions of its joints
and links.
W-space may contain obstacles. Each obstacle is a simple closed curve of
finite size. There may be only a finite number of obstacles present in W-space.
Formally, this means that the boundary of any obstacle is homeomorphic to a
circle and that any circle of a limited radius or a straight line passing through
W-space will intersect with a finite set of obstacles. Being rigid bodies, obstacles
cannot intersect one another. Two or more obstacles may touch each other, in
which case for the arm they effectively present one obstacle. At any position of
the arm with respect to a set of obstacles, at least some arm motion is assumed
to be feasible.

The Task. Our objective for the arm is to move it from the starting position S
to the target position T , or to (correctly) conclude in finite time that no path from
S to T exists. Only continuous motion of the links is allowed. Both positions
S and T lie within the W-space. A position of the arm is said to be feasible if,
when the arm’s endpoint is in this position, the arm’s links and joints intersect no
obstacles. Position S is known to be feasible. Because of obstacles in the scene,
position T may or may not be feasible. Even if position T is feasible, it may or
may not be reachable from position S.
C-Space. The configuration space (C-space) is a representation space in which
the arm is shrunk to a point. In our case, C-space is the space of arm joint vari-
ables, which happen to be the arm’s independent control variables. Every path
and every virtual obstacle has its corresponding image in C-space. A combination
of the virtual line with the corresponding arm solutions defines the virtual bound-
ary of the obstacle. The virtual boundary is a curve that forms the boundary of
the obstacle image in C-space. The transformation from C-space to W-space is
unique. As we will discuss later, depending on the arm configuration, the trans-
formation from W-space to C-space may or may not be unique. We will soon
see that for all the arms shown in Figure 5.1 the corresponding C-space presents
a two-dimensional manifold.
One should not confuse the dimensionality of the manifold in question with the
dimensionality of space in which the manifold appears. For example, later in this
text we will deal with the surfaces of a common torus or a sphere. While each of
these is a two-dimensional manifold, they appear in the three-dimensional space.
In general, C-space is a k-dimensional manifold in a Euclidean space whose
dimension is higher than k. Accordingly, the metric in a manifold in question
may or may not be Euclidean. We will see later, for instance, that unlike what
occurs in a Euclidean space, up to four distinct shortest routes between two points
may appear on the surface of the torus.

Sketching the Approach. To develop a path planning procedure, the problem
of motion planning for a planar arm will be first reduced to that of moving a point