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

198 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

Recall that an ability to explore the whole obstacle boundary is an impor-
tant function exploited in the Bug family algorithms (Section 3.3). The robot
may rarely use it, but it should be there: Bug algorithms need it for assur-
ing convergence and for the target reachability test. We intend to bring this
same mechanism into the process of motion planning for arm manipulators. The
example in Figure 5.7, where two simple closed curves form the virtual obstacle,
raises a question: How many more simple closed curves can a virtual obstacle
have? Unless the robot knows this, it will not know whether it explored the whole
obstacle or there is still something unexplored. And, if the robot does know that
number, how would it know if it has explored the whole obstacle if that were
its goal? The maximum number of simple closed curves in a virtual boundary is
given by the following lemma.

Lemma 5.2.2. For the RR arm, a virtual boundary of an obstacle can be formed
by no more than two closed curves. (See the proof in the Appendix to this chapter.)

3
This is a good news. One conclusion from Lemma 5.2.2 is that if the arm
endpoint completes a full circle on its way around an obstacle, this does not
necessarily mean that the whole virtual boundary has been traversed. There may
be another, yet unobserved, closed curve which limits the virtual obstacle “from
the other side” of the torus. On the other hand, if the robot explored both closed
curves of a virtual boundary, this definitely means the robot has explored the
whole obstacle. We classify obstacles into two types according to topology of
their virtual boundaries.

Definition 5.2.6. The virtual boundary of an obstacle of Type I is formed by a
single closed curve. The virtual boundary of an obstacle of Type II is formed
by two closed curves. No obstacle can be of both types. Type I and Type II are
complementary and together cover all possible virtual obstacles.

For the path planning algorithm, it would be important to know whether a
closed curve traversed by the arm thus far belongs to a Type I or a Type II
obstacle. If such inference is possible, it would allow us to produce a test that the
algorithm can use to plan further robot motion. Namely, if the curve traversed
thus far belongs to an obstacle of Type I, the robot would know that it has
explored that obstacle completely. And, if the curve traversed thus far belongs to
an obstacle of Type II, the robot would know that somewhere out there there is
still another unexplored closed curve of the same virtual boundary. The following
discussion helps produce such a test.
A C-space image of an obstacle is an area on the surface of the C-space torus
separated from the rest of the torus by the obstacle virtual boundary. Taking into
account Lemma 5.2.2 and allowing for any continuous deformations of obstacle
3 In principle, there are more complex arms with rather unusual kinematics that have more than two
simple closed curves per virtual boundary. They are not used in practice and are not discussed in
this text.