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

136 MOTION PLANNING FOR A MOBILE ROBOT

• Point P becomes a hit point when MA, while moving along the ST line,
encounters an obstacle at P .
• Point P can become a leave point if and only if (1) it is possible for MA
to move from P toward T and (2) there is a straight line that is tangential
to the obstacle boundary at P and passes through T . When a leave point is
encountered for the first time, it is called open;itmay be closed by MA
later (see the procedure).
• A local direction is the direction of following an obstacle boundary; it can be
either left or right. In AlgX the current local direction is inverted whenever
MA passes through an open leave point; it does not change when passing
through a closed leave point.
• A local cycle is formed when MA visits some points of its path more
than once.

The idea behind the algorithm AlgX is as follows. MA starts by moving
straight toward point T . Every time it encounters an obstacle, it inverts its
local direction, the idea being that this will keep it reasonably close to the
straight line (S, T ). If a local cycle is formed, MA blames it on the latest turn
it made at a hit point. Then MA retraces back to the latest visited leave point,
closes it, and whence takes the opposite turn at the next hit point. If that turn
leads again to a local cycle, then the turn that led to the current leave point
is to be blamed. And so on. The procedure operates as follows:
Initialization. Set the current local direction to “right”; set j = 0,
L j = S.
Step 1. Move along a straight line from the current leave point toward point
T until one of the following occurs:
a. Target T is reached; the procedure terminates.
b. An obstacle is encountered; go to Step 2.
Step 2. Define a hit point H j . Turn in the current local direction and move
along the obstacle boundary until one of the following occurs:
a. Target T is reached; the procedure terminates.
b. The current velocity vector (line tangential to the obstacle at the current
MA position) passes through T , and this point has not been defined
previously as a leave point; then, go to Step 3.
c. MA comes to a previously defined leave point L i , i ≤ j (i.e., a local
cycle has been formed). Go to Step 4.
Step 3. Set j = j + 1; define the current point as a new open leave point;
invert the current local direction; go to Step 1.
Step 4. Close the open leave point L k visited immediately before L i . Invert
the local direction. Retrace the path between L i and L k . (During retracing,
invert the local direction when passing through an open leave point, but
do not close those points; ignore closed leave points.) Now MA is at the
closed leave point L k .If L i is open,gotoStep1.If L i is closed, execute