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

110 MOTION PLANNING FOR A MOBILE ROBOT

Test for Target Reachability. If, after having defined the last hit point as its
intermediate target, the robot returns to it before it defines the next hit point,
then either the robot or the target point is trapped and hence the target is not
reachable. (For more detail, see the corresponding text for algorithm Bug2.)

The following notation is used in the rest of this section:

• C i and T i are the robot’s position and intermediate target at step i.
• |AB| is the straight-line segment whose endpoints are A and B; it may also
designate the length of this segment.
• (AB) is the obstacle boundary segment whose endpoints are A and B,or
the length of this segment.
• [AB] is the path segment between points A and B that would be generated
by algorithm Bug2, or the length of this path segment.
• {AB} is the path segment between points A and B that would be generated
by algorithm VisBug-21 or VisBug-22, or the length of this path segment.

It will be evident from the context whether a given notation is referring to a
segment or its length. When more than one segment appears between points A
and B, the context will resolve the ambiguity.

3.6.2 Algorithm VisBug-21
The algorithm consists of the Main body, which does the motion planning proper,
and a procedure called Compute T i -21, which produces the next intermediate
target T i and includes the test for target reachability. As we will see, typically the
flow of action in the main body is confined to its step S1. Step S2 is executed only
in the special case when the robot is moving along a (locally) convex obstacle
boundary and so it cannot use its vision to define the next intermediate target T i .
For reasons that will become clear later, the algorithm distinguishes between the
case when point T i lies in the main semiplane and the case when T i lies in the
secondary semiplane. Initially, C = T i = S.

Main Body. The procedure is executed at each point of the continuous path. It
includes the following steps:

• S1: Move toward point T i while executing Compute T i -21 and performing
the following test:
If C = T the procedure stops.
Else if Target is unreachable the procedure stops.
Else if C = T i go to step S2.
• S2: Move along the obstacle boundary while executing Compute T i -21 and
performing the following test:
If C = T the procedure stops.