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

296 MOTION PLANNING FOR THREE-DIMENSIONAL ARM MANIPULATORS

To find the necessary condition, we will use the notion of a minimal projection.
The following statement asserts that a zero overlap between two sets in C implies
a zero overlap between their minimal projections in C p :
Lemma 6.2.3. For any set E and any C-obstacle O in C,if O ∩ E =∅,then
P m (E) ∩ P m (O) =∅.

−1
−1
−1
−1
By definition, P (E 1 ∩ E 2 ) = P (E 1 ) ∩ P (E 2 ) and P (P m (O)) ⊂ O.
m m m m
−1 −1
Thus, if P m (E) ∩ P m (O) =∅,then ∅ = P (P m (E) ∩ P m (O)) = P (P m (E) ∩
m
m
−1
P (P m (O))) ⊂ O ∩ E.
m
To use this lemma in the algorithm design, we need to describe minimal
projections for different obstacle types. For any Type I or Type II obstacle O,
P c (O) = P m (O). For a Type III obstacle we consider three cases, using, as an
example, a Type III + obstacle; denote it O + .
• O + intersects the floor F of C. Because of the monotonicity property,
P m (O + ) = O + ∩ F. In other words, the minimal projection of O + is exactly
the intersection area of O + with the floor F.
• O + intersects with a Type III − obstacle, O − . Then, B(P m (O + ∪ O − )) =
P c (B(O + ) ∩ B(O − )),where B(O) refers to the boundary of O.That is,
the boundary curve of the combined minimal projection of O + and O − is
the conventional projection of the intersection curve between the boundary
surfaces of O + and O − .
• Neither of the above cases apply. Then P m (O + ) =∅.
A similar argument can be carried out for a Type III − obstacle.
We now turn to establishing a necessary and sufficient condition that ties the
existence of paths in the plane C p with that in C. This condition will provide a
base for generalizing, in the next section, a planar path planning algorithm to the
3D space. Assume that points S and T lie outside of obstacles.

Theorem 6.2.1. Given points S, T and a set of obstacles {O} in C, a path exists
between S and T in C if and only if there exists a path in C p between points P c (S)
and P c (T ) among the obstacles P m ({O}).

First, we prove the necessity. Let l(t), t ∈ [0, 1], be a trajectory in C.From
Lemma 6.2.3, P m (l(t)) ∩ P m ({O}) =∅. Hence, the path P m (l(t)) connects P c (S)
and P c (T ) in C p .
To show the sufficiency, let l p (t), t ∈ [0, 1], be a trajectory in C p and let l p (·)
−1
be the corresponding path. Then P (l p (·)) presents a manifold in C.Define
m
−1
−1
c
E = P (l p (·)) ∩{O} and let E be the complement of E in P (l p (·)).We need
m
m
c
to show that E consists of one connected component. Assume that this is not true.
For any t ∗ ∈ [0, 1], since l p (t ∗ ) ∩ P m ({O}) =∅, there exists l 3∗ such that point
c
c
(l p (t ∗ ), l 3∗ ) ∈ E . The only possibility for E to consist of two or more discon-

nected components is when there exists t ∗ and a set (l 3∗ ,l ,l ), l >l 3∗ >l ,

3∗ 3∗ 3∗ 3∗