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

88 MOTION PLANNING FOR A MOBILE ROBOT

Proof: Any path generated by algorithm Bug1 can be looked at as consisting
of two parts: (a) straight-line segments of the path while walking in free space
between obstacles and (b) path segments when walking around obstacles. Due
to inequality (3.6), the sum of the straight-line segments will never exceed D.
As to path segments around obstacles, algorithm Bug1 requires that in order to
define a leave point on the ith obstacle, MA has to first make a “full circle”
along its boundary. This produces a path segment equal to one perimeter, p i ,of
the ith obstacle, with its end at the hit point. By the time MA has completed
this circle and is ready to walk again around the ith obstacles from the hit to the
leave point, in order to then depart for point T , the procedure prescribes it to go
along the shortest path. By then, MA knows the direction (going left or going
right) of the shorter path to the leave point. Therefore, its path segment between
the hit and leave points along the ith obstacle boundary will not exceed 0.5 · p i .
Summing up the estimates for straight-line segments of the path and segments
around the obstacles met by MA on its way to point T , obtain (3.7). Q.E.D.

Further analysis of algorithm Bug1 shows that our model’s requirement that
MA knows its own coordinates at all times can be eased. It suffices if MA knows
only its distance to and direction toward the target T . This information would
allow it to position itself at the circle of a given radius centered at T . Assume
that instead of coordinates of the current point Q m of minimum distance between
the obstacle and T , we store in register R 1 the minimum distance itself. Then
in Step 3 of the algorithm, MA can reach point Q m by comparing its current
distance to the target with the content of register R 1 . If more than one point of
the current obstacle lie at the minimum distance from point T , any one of them
can be used as the leave point, without affecting the algorithm’s convergence.
In practice, this reformulated requirement may widen the variety of sensors the
robot can use. For example, if the target sends out, equally in all directions, a low-
frequency radio signal, a radio detector on the robot can (a) determine the direc-
tion on the target as one from which the signal is maximum and (b) determine
the distance to it from the signal amplitude.

Test for Target Reachability. The test for target reachability used in algorithm
Big1 is designed as follows. Every time MA completes its exploration of a new
obstacle i, it defines on it a leave point L i . Then MA leaves the ith obstacle at
L i and starts toward the target T along the straight line (L i ,T ). According to
Lemma 3.3.1, MA will never return again to the ith obstacle. Since point L i is
by definition the closest point of obstacle i to point T , there will be no parts of
the obstacle i between points L i and T . Because, by the model, obstacles do not
touch each other, point L i cannot belong to any other obstacle but i. Therefore,
if, after having arrived at L i in Step 3 of the algorithm, MA discovers that the
straight line (L i ,T ) crosses some obstacle at the leave point L i , this can only
mean that this is the ith obstacle and hence target T is not reachable—either
point S or point T is trapped inside the ith obstacle.
To show that this is true, let O be a simple closed curve; let X be some point
in the scene that does not belong to O;let L be the point on O closest to X;