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

THE MODEL 79

obstacles. Note that the model does not require that the scene or the overall
set of obstacles be finite.
Robot. MA is a point. This means that an opening of any size between two dis-
tinct obstacles can be passed by MA. MA’s motion skills include three actions:
It knows how to move toward point T on a straight line, how to move along
the obstacle boundary, and how to start moving and how to stop. The only
input information that MA is provided with is (1) coordinates of points S and
T as well as MA’s current locations and (2) the fact of contacting an obstacle.
The latter means that MA has a tactile sensor. With this information, MA can
thus calculate, for example, its direction toward point T and its distance from
it. MA’s memory for storing data or intermediate results is limited to a few
computer words.
Definition 3.1.1. A local direction is a once-and-for-all decided direction for
passing around an obstacle. For the two-dimensional problem, it can be either
left or right.
That is, if the robot encounters an obstacle and intends to pass it around, it
will walk around the obstacle clockwise if the chosen local direction is “left,”
and walk around it counterclockwise if the local direction is “right.” Because of
the inherent uncertainty involved, every time MA meets an obstacle, there is no
information or criteria it can use to decide whether it should turn left or right to
go around the obstacle. For the sake of consistency and without losing generality,
unless stated otherwise, let us assume that the local direction is always left,as
in Figure 3.5.

Definition 3.1.2. MA is said to define a hit point on the obstacle, denoted H,
when, while moving along a straight line toward point T , it contacts the obstacle
at the point H. It defines a leave point, L, on the obstacle when it leaves the
obstacle at point L in order to continue its walk toward point T . (See Figure 3.5.)

In case MA moves along a straight line toward point T and the line touches
some obstacle tangentially, there is no need to invoke the procedure for walking
around the obstacle—MA will simply continue its straight-line walk toward point
T . This means that no H or L points will be defined in this case. Consequently,
no point of an obstacle can be defined as both an H and an L point. In order
to define an H or an L point, the corresponding straight line has to produce a
“real” crossing of the obstacle; that is, in the vicinity of the crossing, a finite
segment of the line will lie inside the obstacle and a finite segment of the line
will lie outside the obstacle.
Below we will need the following notation:

D is Euclidean distance between points S and T .
d(A, B) is Euclidean distance between points A and B in the scene;
d(S, T ) = D.