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

MINIMUM TIME STRATEGY 159

r v was insufficient to see the obstacle far enough to initiate a smooth turn. In
Figure 4.7d, the stop at point P was probably caused by the robot’s temporarily
losing its current intermediate target.

4.3 MINIMUM TIME STRATEGY
We will now consider the second strategy for solving the Jogger’s Problem.The
same model of the robot, its environment, and its control means will be used as
in the Maximum Turn Strategy (see Section 4.2.1).
The general strategy will be as follows: At the given step i, the kinematic
motion planning procedure chosen—we will use again VisBug algorithms—
identifies an intermediate target point, T i , which is the farthest visible point on
a convergent path. Normally, though not always, T i is defined at the boundary
of the sensing range r v . Then a single step that lies on a time-optimal trajectory
to T i is calculated and executed; the robot moves from its current position C i to
the next position C i+1 , and the process repeats.
Similar to the Maximum Turn Strategy, the fact that no information is available
beyond the robot’s sensing range dictates a number of requirements. There must
be an emergency stopping path, and it must lie inside the current sensing area.
Since parts of the sensing range may be occupied or occluded by obstacles, the
stopping path must lie in its visible part. Next, the robot needs a guarantee of
stopping at the intermediate target T i , even if it does not intend to do so. That
is, each step is to be planned as the first step of a trajectory which, given the
robot’s current position, velocity, and control constraints, would bring it to a halt
at T i (though, again, this will be happening only rarely).
The step-planning task is formulated as an optimization problem. It is the
optimization criterion and procedure that will make this algorithm quite different
from the Maximum Turn Strategy. At each step, a canonical solution is found
which, if no obstacles are present, would bring the robot from its current position
C i to its current intermediate target T i with zero velocity and in minimum time.
If the canonical path happens to be infeasible because it crosses an obstacle, a
collision-free near-canonical solution path is found. We will show that in this
case only a small number of path options need be considered, at least one of
which is guaranteed to be collision-free.
By making use of the L ∞ -norm within the duration of a single step, we decou-
ple the two-dimensional problem into two one-dimensional control problems and
reduce the task to the bang-bang control strategy. This results in an extremely
fast procedure for finding the time-optimal subpath within the sensing range. The
procedure is easily implementable in real time. Since only the first step of this
subpath is actually executed—the following step will be calculated when new
sensor information appears after this (first) step is executed—this decreases the
error due to the control decoupling. Then the process repeats. One special case
will have to be analyzed and incorporated into the procedure—the case when
the intermediate target goes out of the robot’s sight either because of the robot
inertia or because of occluding obstacles.