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

PLANAR REVOLUTE–REVOLUTE (RR) ARM 195

explored, and the arm will return to the position where it started. The theorem
does not tell us how many simple closed curves may constitute a given virtual
boundary. Can a virtual boundary consist of two, three, or an infinite number of
simple closed curves? We will need to address this question, because it is very
important from the algorithmic standpoint.
Following a simple virtual boundary is as advantageous as it was for the Bug
family algorithms in Section 3.3 to follow the simple closed curves of obstacles,
and for the same reason: When the arm meets an obstacle, one of only two possi-
ble directions for passing around it will have to be chosen. Since no information
about the obstacles is available, neither of the two directions is preferable to
another.

Definition 5.2.5. A local direction is a predefined direction for passing around a
virtual obstacle in C-space; it can be either right or left.

Here “right” and “left” are defined in the same natural way as we did with the
Bug algorithms. Looking at the scene from above, going left means going along
the curve clockwise, that is having the obstacle to one’s right, and going right
means going along the curve counterclockwise—that is, having the obstacle to
one’s left.
The motion planning algorithm (which is still to be formulated) will proceed
as follows. The arm’s endpoint starts moving along the M-line from its starting
position S toward the target position T . (In C-space the arm and both positions
S and T are points.) When during this motion the arm encounters a virtual
boundary—which means the arm contacts an obstacle—it defines on it a hit
point H. The arm then starts passing around the obstacle using the chosen local
direction. Since in doing so it follows a simple closed curve, it will eventually
either reach point T , or return to the hit point H, or meet the M-line again. In
the latter case, if the distance, as measured along the M-line, between the point
where the arm meets the M-line and T is shorter than that between the hit point
H and T , the arm defines this point as a leave point L. In Figure 5.3 the arm
position (a 2 ,b 2 ) is the hit point H 1 , and position (a 12 ,b 12 ) is the leave point
L 1 . (As mentioned above, depending on the chosen local direction and the way
of passing around the obstacle, some other point might be defined as the leave
point; this option will be discussed further later.)
We now turn to the question of the maximum number of simple closed curves
that may form a virtual obstacle. Unlike some special two-dimensional nonori-
entable surfaces, such as the Moebius strip and Kline bottle, the surface of the
common torus is topologically an orientable surface [57]. By continuously mov-
ing on one side of an orientable surface, a point robot will never find itself on the
other side of the surface (which can happen on nonorientable surfaces). This fact
follows from the Jordan Curve Theorem [57, 105], according to which any closed
curve homeomorphic to a circle drawn around and in the vicinity of a given point
on an orientable surface divides the surface into two separate domains, for which
the curve is their common boundary [57].