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

194 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

A geodesic curve connecting points S and T on the surface of the C-space
torus corresponds to a straight line in the plane of variables (θ 1 ,θ 2 ). This geodesic
curve can therefore be used as the “shortest” M-line between positions S and T .
Because of the torus topology, in general, four such “shortest” M-lines can appear.
Shown in Figure 5.5 are these four M-lines, their middle points, and positive and
negative directions and zero points for both variables (θ 1 ,θ 2 ). With appropriate
positioning of points S and T on the torus, all four M-lines can be made indeed
equal. Otherwise, each M-line presents the “shortest” curve for a given set of
directions of change of variables (θ 1 ,θ 2 ).
Since in general every position of the arm endpoint corresponds to two posi-
tions of the arm, defining uniquely the image of a virtual line in C-space will
require some additional information about the corresponding arm positions.

Definition 5.2.4. A virtual boundary is a curve in C-space that represents the
image of the corresponding virtual line.

Clearly, the virtual boundary corresponds to one out of two sets of arm posi-
tions tied to the virtual line. Where is the other set? The other set is physically
unrealizable: In each such position the arm links would cross through the corre-
sponding obstacle.
The virtual boundary separates an area of C-space occupied by the virtual
obstacle from the rest of C-space. A finite number of actual obstacles in W-space
produce a finite number of virtual obstacles in C-space. Each intersection of the
M-line with the virtual line in W-space has its counterpart intersection of the
M-line image with the virtual boundary. Unlike virtual lines, virtual boundaries
cannot form self-intersections or double points. This means that at any point
during the motion along the virtual boundary in C-space, there is one and only one
possible direction for continuing the motion. Therefore, the following statement
holds.

Lemma 5.2.1. A virtual boundary can consist of only simple curves.

To define the virtual boundary corresponding to the virtual line of obstacle A
in Figure 5.3, points a 1 to a 14 have to be added, coordinates of the endpoint of
link l 1 ; the respective positions (a i ,b i ) of link l 2 are shown in the figure. Note
that the coinciding points on the virtual line correspond to different positions of
link l 2 .Thatis, in C-space all points of the virtual boundary are distinct. The
same is true for obstacle B.

Theorem 5.2.1. A virtual boundary can consist of only simple closed curves. (See
the proof in the Appendix to this chapter.)

This statement will be pivotal in the design of the motion planning algorithm
for an RR arm. Formally, the statement means that no matter what direction is
chosen for following the virtual boundary, eventually the whole curve will be