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

MINIMUM TIME STRATEGY 173

Remark: Claim 1 will hold for V S = 0 as well if there exists at least one stopping
path originating at the start point S.

In practical terms, this is a reasonable condition. If for some reason the robot
did not start at S and was passing through it on the fly—which is already strange
enough—it is hard to imagine that point S happened to be so bad that it could
not even provide a stopping path.

Claim 2. The Minimum Time Strategy guarantees convergence.

To see this, note that at each step i at its current position C i , the robot uses
its sensing to generate the next intermediate target point T i . That point T i is
known to lie on a convergent path of the kinematic algorithm (Section 3.6.3).
At the moment when T i is generated, it is visible. Hence, the only way that
the robot can get lost is if at the next step C i+1 point T i becomes invisible
due to the robot inertia or obstacle occlusion: This would make it impossible to
generate the intermediate target T i+1 as required by the kinematic algorithm. But,
if indeed point T i becomes invisible, the Find Lost Target procedure is invoked
and a set of temporary intermediate targets T t and associated steps are executed
i+1
until point T i becomes visible again (see Figure 4.11a). Thus the robot always
moves toward a point that lies on a convergent path and itself converges to the
target T .

Computational Complexity. As with other on-line sensor-based algorithms, it
would not be very informative to try to assess the algorithm complexity the way
it is usually done for algorithms with complete information, as a function of the
number of vertices of approximated obstacles (see Chapter 1). As one reason,
algorithms with complete information deal with one-time computation, whereas
in sensor-based algorithms the important complexity measure is the amount of
computations at each step; the total computation time is simply a linear function
of the path length.
As shown in Section 4.3.4, though the canonical solution found by the algo-
rithm at each path step is the solution of a fairly complex time-optimal problem,
its computational cost is remarkably low, thanks to the (optimal) bang-bang con-
trol. This computation includes (a) substituting the initial conditions (ξ, η, ξ, ¨η)
¨
into the equations for parabolas [Eqs. (4.16) and (4.17)] to see if the start point is
above or below the corresponding parabola and (b) simply taking the correspond-
ing control pair ( ˆp, ˆq) from the four choices in (4.18). The parabola equations
themselves are found beforehand, only once. The near-canonical solution, when
needed, is similar and as fast. Note that a single-step computation is of constant
time: Though the canonical solution represents the whole multistep trajectory
within the sensing range of radius r v , the computation time is independent of the
value r v and of the length of path within the sensing range.