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

260 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

A
b
b *
* b 2 ′′
b
b 1 * b 1 b 2 ′ b 1
b 2 b 2 ′′ B
b 2 ′
B
l 2 A
B
a 2 ′
a a a
a 2 * * a 1 * a 2 ′′
a 1 a 2 ′′ a 2 ′ a 1
l 1
A C
C
(a) (b) (c)
Figure 5.39 An illustration for the proof of Theorem 5.2.1.

arm endpoint (and not any other point of the arm body) is in contact with some
obstacle, A. The dead end position may occur only if one or two other obstacles,
B and C, appear as shown in Figure 5.39a. Clearly, it is always possible to move

from P ∗ to a position distinct from P 1 (here, P or P , respectively). Thus, P ∗
2 2
cannot be a dead end position.
Case 3 (Figure 5.39c); a ∗ = a 1 , b ∗ = b 1 . In this case, the segments l 2 in both
positions P 1 and P ∗ intersect each other. This may occur only if l 2 is “rolling”
around some obstacle, A. Here, P ∗ may be a dead end only if one or two other
obstacles, B and C, appear as shown in Figure 5.39c. Observe that positions P
2
and P , respectively, are good alternatives to P 1 . Therefore, P ∗ is not a dead-end

2
position. This exhausts all possible cases and completes the proof. Q.E.D.
Proof of Lemma 5.2.2 (Section 5.2.1). Torus is a closed orientable manifold.
The maximum number of closed curves needed to divide a given closed orientable
manifold into two separate domains is determined by its connectivity numbers.
The first connectivity number is known to define the maximum number of closed
cuts that can be made on the surface without dividing it into separate domains.
On the torus, the first connectivity number is equal to two [105]. The only
arrangement for two closed cuts (two closed curves), a and b, that can be made
on the torus without dividing it into separate domains is shown in Figure 5.40.
According to Theorem 5.2.1, a virtual boundary consists of simple closed curves
and thus cannot have self-intersections. Any other arrangement of two closed
curves on the torus such that they do not touch or intersect each other produces
at least two separate domains. Similarly, more than two simple closed curves
produce more than two separate domains. Therefore, if some area on the torus is
separated from the rest of it by simple closed curves then the boundary of this
area consists of no more that two such curves. Q.E.D.