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

BASIC ALGORITHMS 89

and let (L, X) be the straight-line segment connecting L and X. All these are
in the plane. Segment (L, X) is said to be directed outward if a finite part of it
in the vicinity of point L is located outside of curve O.Otherwise, if segment
(L, X) penetrates inside the curve O in the vicinity of L,itissaidto be directed
inward.
The following statement holds: If segment (L, X) is directed inward, then
X is inside curve O. This condition is necessary because if X were outside
curve O, then some other point of O that would be closer to X than to L
would appear in the intersection of (L, X) and O. By definition of the point L,
this is impossible. The condition is also sufficient because if segment (L, X) is
directed inward and L is the point on curve O that is the closest to X,then
segment (L, X) cannot cross any other point of O, and therefore X must lie
inside O. This fact is used in the following test that appears as a part in Step 3
of algorithm Bug1:

Test for Target Reachability. If, while using algorithm Bug1, after having
defined a point L on an obstacle, MA discovers that the straight line segment
(L, Target) crosses the obstacle at point L, then the target is not reachable.

One can check the test on the example shown in Figure 3.4. Starting at point T ,
the robot encounters an obstacle and establishes on it a hit point H.Using the
local direction “left,” it then does a full exploration of the (accessible) boundary
of the obstacle. Once it arrives back at point H, its register R 1 will contain the
location of the point on the boundary that is the closest to T . This happens to be

T

L

H
S
Figure 3.4 Algorithm Bug1. An example with an unreachable target (a trap).