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

MINIMUM TIME STRATEGY 163

maximum velocity, the availability of a stopping path has to be ascertained at
every step i. Our stopping path will be a straight-line path along the corresponding
vector V i . If a candidate step cannot guarantee a stopping path, it is discarded. 4

Step Planning. Normally the stopping path is not used; it is only an “insurance”
option. The actual step is based on the canonical solution, a path which, if
fully executed, would bring the robot from C i to T i with zero velocity and
in minimum time, assuming no obstacles. The optimization problem is set up
based on Pontryagin’s optimality principle. We assume that within a step time
interval [t i ,t i+1 ) the system’s controls (p, q) are bounded in the L ∞ -norm, and
apply it with respect to the secondary coordinate frame (ξ i ,η i ). The result is
a fast computational scheme easily implementable in real time. Of course only
the very first step of the canonical path is explicitly calculated and used in the
actual motion. At the next step, a new solution is calculated based on the new
sensory information that arrived during the previous step, and so on. With such a
step-by-step execution of the optimization scheme, a good approximation of the
globally time-optimal path from C i to T i is achieved. On the other hand, little
computation is wasted on the part of the path solution that will not be utilized.
If the step suggested by the canonical solution is not feasible due to obstacles,
a close approximation, called the near-canonical solution, is found that is both
feasible and -acceptable. For this case we show, first, that only a finite number
of path options need be considered and, second, that there exists at least one path
solution that is -acceptable. A special case here is when the intermediate target
goes out of the robot’s sight either because of the robot’s inertia or because of
occluding obstacles.

Convergence. Once a step is physically executed, new sensing information
appears and the process repeats. If an obstacle suddenly appears on the robot’s
intended path, a detour is arranged, which may or may not require the robot to
stop. The detour procedure is tied to the issue of convergence, and it is built
similar to the case of normal motion. Because of the effect of dynamics, the con-
vergence mechanism borrowed from a kinematic algorithm—here VisBug—will
need some modification. The intermediate target points T i produced by VisBug
lie either on the boundaries of obstacles or on the M-line, and they are visible
from the corresponding robot’s positions.
However, the robot’s inertia may cause it to move so that T i will become
invisible, either because it goes outside of the sensing range r v (as after point P ,
Figure 4.1) or due to occluding obstacles (as in Figure 4.11). This may endanger
path convergence. A safe but inefficient solution would be to slow down or to
keep the speed small at all times to avoid such overshoots. The solution chosen
(Section 4.3.6) is to keep the velocity high and, if the intermediate target T i goes
out of sight, modify the motion locally until T i is found again.

4 A deeper, multistep analysis would be hardly justifiable here because of high computational costs,
though occasionally it could produce locally shorter paths.