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

82 MOTION PLANNING FOR A MOBILE ROBOT

segment is of length l, then the perimeter of the corresponding actual obstacle is
equal to 2l; this takes into account the inside and outside walls of the segment
and also the fact that the thickness of the wall is negligible (see Figure 3.1).
This method of producing the resultant scene is justified by the fact that, under
the accepted model, the behavior of MA is affected only by those obstacles that
it touches along its way. Indeed, under algorithm X the very same path would
have been produced in two different scenes: in the scene with the virtual obstacle
and in the resultant scene. One can therefore argue that the areas of the virtual
obstacle that MA has not touched along its way might have never existed, and
that algorithm X produced its path not in the scene with the virtual obstacle
but in the resultant scene. This means the performance of MA in the resultant
scene can be judged against (3.1). This completes the design of the scene. Note
that depending on the MA’s behavior under algorithm X, zero, one, or more
actualized obstacles can appear in the scene (Figure 3.1b).
We now have to prove that the MA’s path in the resultant scene satisfies
inequality (3.1). Since MA starts at a distance D = d(S, T ) from point T ,it
obviously cannot avoid the term D in (3.1). Hence we concentrate on the second
term in (3.1). One can see by now that the main idea behind the described
process of designing the resultant scene is to force MA to generate, for each
actual obstacle, a segment of the path at least as long as the total length of that
obstacle’s boundary. Note that this characteristic of the path is independent of
the algorithm X.
The MA’s path in the scene can be divided into two parts, P 1and P 2; P 1
corresponds to the MA’s traveling inside the corridor, and P 2 corresponds to its
traveling outside the corridor. We use the same notation to indicate the length
of the corresponding part. Both parts can become intermixed since, after having
left the corridor, MA can temporarily return into it. Since part P 2startsat the
exit point of the corridor, then

P 2 ≥ L + C (3.2)

√
2
2
where C = D + W is the hypotenuse AT of the triangle ATS (Figure 3.1a).
As for part P1 of the path inside the corridor, it will be, depending on the
algorithm X, some curve. Observe that in order to defeat the bound—that is,
produce a path shorter than the bound (3.1)—algorithm X has to decrease the
“path per obstacle” ratio as much as possible. What is important for the proof
is that, from the “path per obstacle” standpoint, every segment of P 1 that does
not result in creating an equivalent segment of the actualized obstacle makes the
path worse. All possible alternatives for P 1 can be clustered into three groups.
We now consider these groups separately.

1. Part P 1 of the path never touches walls of the virtual obstacle (Figure 3.1a).

As a result, no actual obstacles will be created in this case, p i = 0. Then
i
the resulting path is P> D, and so for an algorithm X that produces this
kind of path the theorem holds. Moreover, at the final evaluation, where