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

THE CASE OF THE PPP (CARTESIAN) ARM 295

6.2.4 Connectivity of C
A space or manifold is connected relative to two points in it if there is a path that
connects both points and that lies fully in the space (manifold). For a given path
l, the corresponding trajectory l(t) defines this path as a function of a scalar
variable t; for example, t may indicate time. Denote the 2D Cartesian space
formed by joint values l 1 , l 2 as C p , C p = [0,l 1max ] × [0,l 2max ].
We intend to show here that for the 3D Cartesian arm the connectivity in C
can be deduced from the connectivity in C p . Such a relationship will mean that
the problem of path planning for the 3D Cartesian arm can be reduced to that
for a point automaton in the plane, and hence the planar strategies of Chapter 3
can be utilized here, likely with some modifications.
Define the conventional projection P c (E) of a set of points E ={(l 1 ,l 2 ,l 3 )}⊆
∗
C onto space C p as P c (E) ={(l 1 ,l 2 ) |∃ l , (l 1 ,l 2 ,l ) ∈ E}. Thus, P c (S), P c (T ),
∗
3 3
P c (M-line), and P c ({O}) are, respectively, the projections of points S and T ,the
M-line, and C-obstacles onto C p . See, for example, projections P c of three obsta-
cles, O 1 , O 2 , O 3 (Figure 6.12). It is easy to see that P c (O 1 ∩ O 2 ) = P c (O 1 ) ∩
P c (O 2 ).
Define the minimal projection P m (E) of a set of points E ={(l 1 ,l 2 ,l 3 )}⊆ C
onto space C p as P m (E) ={(l 1 ,l 2 ) |∀ l 3 , (l 1 ,l 2 ,l 3 ) ∈ E}. Thus, if a C-obstacle
O stretches over the whole range of l 3 ∈ [0,l 3max ], and E contains all the points
in O,then P m (E) is the intersection between the (l 1 ,l 2 )-space and the maximum
cylinder that can be inscribed into O and whose axis is parallel to l 3 . Note that if a
set E is a cylinder whose axis is parallel to the l 3 axis, then P c (E) = P m (E). Type
I and Type II obstacles present such cylinders. In general, P m (S) = P m (T ) =∅.

Existence of Collision-Free Paths. We will now consider the relationship
between a path in C and its projection in C p . The following statement comes
directly from the definition of P c and P m :

Lemma 6.2.1. For any C-obstacle O in C and any set E p in C p ,if E p ∩ P c (O) =
−1
∅,then P (E p ) ∩ O =∅.
m
−1 −1
If the hypothesis is not true, then P (E p ) ∩ O =∅.We have P c (P (E p ) ∩
m
m
−1
O) = P c (P (E p )) ∩ P c (O) = E p ∩ P c (O) =∅. Thus a contradiction.
m
The next statement provides a sufficient condition for the existence of a path
in C-space:
Lemma 6.2.2. Given a set of obstacles {O} in C and the corresponding projec-
tions P c ({O}), if there exists a path between P c (S) and P c (T ) in C p , then there
must exist a path between S and T in C.

Let l p (t) ={l 1 (t), l 2 (t)} be a trajectory of P c (C-point) between P c (S) and
−1
P c (T ) in C p . From Lemma 6.2.1, P (l p (t)) ∩{O}=∅ in C. Hence, for example,
m
−1
the path l(t) ={(l p (t), (1 − t)l 3S + t · l 3T )}∈ P (l p (t)) connects S and T in C.
c