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

APPENDIX 259

(“dead ends”). This endpoint corresponds to some arm position P ∗ = (a ∗ ,b ∗ ).
Along the curve, take a close, but distinct from P ∗ , arm position, P 1 = (a 1 ,b 1 ).
Apparently, once the arm moves from P 1 to P ∗ , the only way for it to continue
its motion is to return to P 1 .
Because this curve corresponds to the same virtual boundary, in both positions
P ∗ and P 1 the arm is in contact with the obstacle. For P ∗ to be a dead end—that
is, to be qualitatively different from P 1 —there must be some other obstacle that
affects the arm in the position P ∗ but does not affect it in position P 1 . The idea of
the proof is to show that for all possible occurrences of such additional obstacles
at position P ∗ , there is a direction for passing around the obstacle different from
the direction toward P 1 . This means that the arm, after moving from P 1 to P ∗ ,
can then use this alternative direction. Hence, no dead ends are possible, and a
virtual boundary must consist solely of simple closed curves.
Since the numbers a i and b i ,i =∗, 1, come in pairs, there are four possible
combinations: (1) a ∗ = a 1 , b ∗ = b 1 ;(2) a ∗ = a 1 , b ∗ = b 1 ;(3) a ∗ = a 1 , b ∗ = b 1 ;
and (4) a ∗ = a 1 , b ∗ = b 1 . The first combination is of no interest because positions
P ∗ and P 1 on the virtual boundary curve are assumed to be distinct. The second
combination presents two arm solutions for a single point in W-space. For P ∗ and
P 1 to be close to each other in C-space, this point must be located in the vicinity
of the W-space boundary. If it is on the W-space boundary, then a ∗ = a 1 ,which
brings us to the first combination. If the point is not on the W-space boundary,
then consider a point P 2 on the curve such that it lies between, and is distinct
from, points P ∗ and P 1 . Because of the curve continuity, such a point exists.
It must be that b 2 = b ∗ because otherwise P 2 would make the third distinct
arm solution for the same point of W-space, and this is not possible. Using P 2
instead of P 1 , we replace the second combination by either the third or the fourth
combination. Therefore, out of the four possible combinations above, the ones to
study are the third and the fourth. Now we consider the types of situations with
the arm motion that lead to those combinations: Case 1 (for the third combina-
tion) and Cases 2 and 3 (for the fourth combination). (In Figures 5.39a, 5.39b,
and 5.39c, known entities are shown in solid lines, and guessed entities are shown
in dashed lines).

Case 1 (Figure 5.39a); a ∗ = a 1 , b ∗ = b 1 . For this case to occur, link l 1 must
be constrained from one side by some obstacle, call it A. It cannot be constrained
from both sides as it would be immobilized permanently. The only possibility
for the position P ∗ = (a ∗ ,b ∗ ) to be a dead end is if some other obstacle, B,
constrains link l 2 as shown in Figure 5.39a. Clearly, it is possible to continue
passing around the virtual obstacle while moving from P ∗ to some other position
in its vicinity, P 2 = (a 2 ,b 2 ), instead of P 1 .Since P 2 does not lie between P 1
and P ∗ on the virtual boundary and since the virtual boundary is a simple curve,
position P ∗ cannot be a dead end. The only other possibility to consider is having
the obstacle A on the other side of the link l 1 ; this creates a symmetric situation.
Case 2 (Figure 5.39b); a ∗ = a 1 , b ∗ = b 1 . In this case, the segments l 2 in both
positions P 1 and P ∗ do not intersect. This may occur only if in both positions the