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

172 ACCOUNTING FOR BODY DYNAMICS: THE JOGGER’S PROBLEM

C i + 1 C i + 1
C i C k
C i
C k
t
T i + 1
C k + 1
t
T i + 1

T i T i

Figure 4.11 In these examples, because of the system inertia the robot temporarily
“loses” the intermediate target point T i . (a) The robot keeps moving forward until at C k
it sees T i . (b) At C k the robot initiates a stopping path, stops at C k+1 , returns back to C i ,
and moves toward T i along the line (C i ,T i ).

4.3.7 Convergence. Computational Complexity
Convergence. The collision-free motion along the path is guaranteed by the
design of the canonical and near-canonical solutions. To prove convergence, we
need to show that the algorithm will find a path to the target position T if one
exists, or will infer in finite time that T is not reachable if true. This is guaran-
teed by the convergence properties of the kinematic algorithm (Section 3.6). The
following two statements, Claim 1 and Claim 2, hold:

Claim 1. Under the Minimum Time Strategy, assuming zero velocity V S = 0 at
the starting position S, at each step of the path there exists at least one stop-
ping path.

To see this, recall that according to our model the stopping path lies along
a straight line. Guaranteeing a stopping path implies two requirements: a safe
direction and the velocity value that will allow a stop within the visible area.
Because the latter is ensured by the choice of the system parameters in (4.10),
we focus now on the existence of safe directions. Proceed by induction: We have
to show that if a safe direction exists at the start point and on an arbitrary step
i, then there is a safe direction on the step (i + 1).
Since at the start point S the velocity is zero, any direction of motion at S
will be a safe direction. This gives the basis of induction. The induction step is
as follows. Under the algorithm, a candidate step is accepted for execution only
if 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), at the least this very direction can be
used for a stopping path.