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

MAXIMUM TURN STRATEGY 157

if a safe direction exists at the start point and at an arbitrary step i, then there is
a safe direction at the step (i + 1).
Since at the start point S the velocity is zero, V S = 0, then any direction
of motion at S will be a safe direction; this gives the basis of induction. The
induction proceeds as follows. Under the algorithm, a candidate step is accepted
for execution if only its direction guarantees a safe stop for the robot if needed.
Namely, at point C i ,step i is executed only if the resulting vector V i+1 at C i+1
will point in a safe direction. Therefore, at step (i + 1),atthe leastthisvery
direction presents a safe stopping path.

Remark: Proposition 2 will hold for V S = 0 as well if the start point S is known
to possess at least one stopping path originating in it.

Proposition 3. The Maximum Turn Strategy is convergent.

To see this, note that by design of the VisBug algorithm (see Section 3.6.3), each
intermediate target T i lies on a convergent path and is visible at the moment
when it is generated.
That is, the only way the robot can get lost is if at the following step(s)
point T i becomes invisible due to the robot’s inertia or an obstacle occlusion:
This would make it impossible to generate the next intermediate target, T i+1 ,as
required by VisBug. However, if point T i does become invisible, the procedure
Find Lost Target is invoked, a set of temporary intermediate targets T t are
i+1
defined, each with a guaranteed stopping path, and more steps are executed until
point T i becomes visible again (see Figure 4.6). The set T t is finite because of
i+1
finite distances between every pair of points in it and because the set must lie
within the sensing range of radius r v . Therefore, the robot always moves toward
a point which lies on a path that is convergent to the target T .

4.2.7 Examples

Examples shown in Figures 4.7a to 4.7d demonstrate performance of the Max-
imum Turn Strategy in a computer simulated environment. Generated paths are
shown by thicker lines. For comparison, also shown by thin lines are paths pro-
duced under the same conditions by the VisBug algorithm. Polygonal shapes are
chosen for obstacles in the examples only for the convenience of generating the
scene; the algorithms are oblivious to the obstacle shapes.
To understand the examples, consider a simplified version of the relationship
√ √
that appears in Section 4.2.3, V max = 2r v p max = 2r v · f max /m.Inthe simu-
lations, the robot’s mass m and control force f max are kept constant; for example,
an increase in sensing radius r v would “raise” the velocity V max .Radius r v is
the same in Figures 4.7a and 4.7b. In the more complex scene (b), because of
three additional obstacles (three small squares) the robot’s path cannot curve as
freely as in scene (a). Consequently, the robot moves more “cautiously,” that is,
slower; the path becomes tighter and closer to the obstacles, allowing the robot