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

THE CASE OF THE PPP (CARTESIAN) ARM 297
c
c

such that (l p (t ∗ ), l 3∗ ) ∈ E while (l p (t ∗ ), l ) ∈ E and (l p (t ∗ ), l ) ∈ E .How-
3∗ 3∗
ever, this cannot happen because of the monotonicity property of obstacles. Hence
c
E must be connected, and since points S and T lie outside of obstacles, then
c
S, T ∈ E . Q.E.D.
Lifting 2D Algorithms into 3D Space. Theorem 6.2.1 establishes the rela-
tionship between collision-free paths in C and collision-free paths in C p . We now
want to develop a similar relationship between motion planning algorithms for
C and those for C p . We address, in particular, the following question: Given an
algorithm A p for C p , can one construct an algorithm A for C, such that any tra-
jectory (path) l(t) produced by A in C in the presence of obstacles {O} maps by
P m into the trajectory l p (t) produced by A p in C p in the presence of obstacles
P m ({O})?
We first define the class of algorithms from which algorithms A p are chosen.
A planar algorithm A p is said to belong to class A p if and only if its operation
is based on local information, such as from tactile sensors; the paths it produces
are confined to the M-line, obstacle boundaries, and W-space boundaries; and it
guarantees convergence. In other words, class A p comprises only sensor-based
motion planning algorithms that satisfy our usual model. In addition, we assume
that all decisions about the direction to proceed along the M-line or along the
obstacle boundary are made at the intersection points between M-line and obstacle
boundaries.
Theorem 6.2.1 says that if there exists a path in C p (between projections
of points S and T ), then there exists at least one path in C. Our goal is to
dynamically construct the path in C while A p , the given algorithm, generates its
path in C p . To this end, we will analyze five types of elemental motions that
appear in C, called Motion I, Motion II, Motion III, Motion IV, and Motion V,
each corresponding to the P c (C-point) motion either along the P c (M-line) or
along the obstacle boundaries P c ({O}). Based on this analysis, we will augment
the decision-making mechanism of A p to produce the algorithm A for C.
Out of the three types of obstacle monotonicity property identified above, only
Type III monotonicity is used in this section. One will see later that other mono-
tonicity types can also be used, resulting in more efficient algorithms. Below,
Type I and II obstacles are treated as C-space side walls; the C-space ceiling is

treated as a Type III + obstacle; and the C-space floor is treated as a Type III −
obstacle. Note that when the arm comes in contact simultaneously with what it
perceives as two Type III obstacles, only those of the opposite “signs” have to
be distinguished—that is, a Type III + and a Type III − . Obstacles of the same
sign will be perceived as one. Below, encountering “another Type III obstacle”
refers to an obstacle of the opposite sign. Then the projection P m of the union
of the obstacles is not zero, P m (·) =∅.
Among the six local directions defined in Section 6.2.1—forward, backward,
left, right, upward,and downward —the first four can be used in a 2D motion
planning algorithm. Our purpose is to design a general scheme such that, given
any planar algorithm A p , a 3D algorithm A can be developed that lifts the