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

156 ACCOUNTING FOR BODY DYNAMICS: THE JOGGER’S PROBLEM

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

T i T i

(a) (b)
Figure 4.6 Because of its inertia, immediately after its position C i the robot temporarily
“loses” the intermediate target T i . (a) The robot keeps moving around the obstacle until
it spots T i , and then it continues toward T i . (b) When because of an obstacle the whole
segment (C i ,T i ) becomes invisible at point C k+1 , the robot stops, returns back to C i ,and
then moves toward T i along the line (C i ,T i ).

Convergence. To prove convergence of the described procedure, we need to
show the following:

(i) At every step of the path the algorithm guarantees collision-free motion.
(ii) The set of intermediate targets T i is guaranteed to lie on the convergent
path.
(iii) The planning strategy guarantees that the current intermediate target will
not be lost.

Together, (ii) and (iii) assure that a path to the target position T will be found
if one exists. Condition (i) can be shown by induction; condition (ii) is provided
by the VisBug procedure (see Section 3.6), which also includes the test for target
reachability. Condition (iii) is satisfied by the procedure Find Lost Target of the
Maximum Turn Strategy. The following two propositions hold:

Proposition 2. Under the Maximum Turn Strategy algorithm, assuming zero
velocity, V S = 0, at the start position S, at each step of the path there exists
at least one stopping path.

By design, the stopping path is a straight-line segment. Choosing the next step
so as to guarantee existence of a stopping path implies two requirements: There
should be at least one safe direction of motion and the value of velocity that
would allow stopping within the visible area. The latter is ensured by the choice
of system parameters [see Eq. (4.1) and the safety conditions, Section 4.2.2]. As
to the existence of safe directions, proceed by induction: We need to show that