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

UNIVERSAL LOWER BOUND FOR THE PATH PLANNING PROBLEM 83

only actual obstacles count, the algorithm X will not be judged as efficient:
It creates an additional path component at least equal to (2 · L + (C − D)),
in a scene with no obstacles!
2. MA touches more than once one or both inside walls of the virtual obsta-
cle (Figure 3.1b). That is, between consecutive touches of walls, MA is
temporarily “out of touch” with the virtual obstacle. As a result, part P 1
of the path will produce a number of disconnected actual obstacles. The
smallest of these, of length δ, corresponds to point touches. Observe that
in terms of the “path per obstacle” assessment, this kind of strategy is
not very wise either. First, for each actual obstacle, a segment of the path
at least as long as the obstacle perimeter is created. Second, additional
segments of P 1, those due to traveling between the actual obstacles, are
produced. Each of these additional segments is at least not smaller than
2W, if the two consecutive touches correspond to the opposite walls of
the virtual obstacle, or at least not smaller than the distance between two
sequentially visited disconnected actual obstacles on the same wall. There-
fore, the length P of the path exceeds the right side in (3.1), and so the
theorem holds.
3. MA touches the inside walls of the virtual obstacle at most once. This
case includes various possibilities, from a point touching, which creates a
single actual obstacle of length δ, to the case when MA closely follows the
inside wall of the virtual obstacle. As one can see in Figure 3.1c, this case
contains interesting paths. The shortest possible path would be created if
MA goes directly from point S to the furthest point of the virtual obstacle
and then directly to point T (path P a , Figure 3.1c). (Given the fact that
MA knows nothing about the obstacles, a path that good can be generated
only by an accident.) The total perimeter of the obstacle(s) here is 2δ,and
the theorem clearly holds.
Finally, the most efficient path, from the “path per obstacle” standpoint,
is produced if MA closely follows the inside wall of the virtual obstacle
and then goes directly to point T (path P b ,Figure 3.1c).HereMA is
doing its best in trying to compensate each segment of the path with an
equivalent segment of the actual obstacle. In this case, the generated path
P is equal to

2
2
P = p i + D + W − W (3.3)
i

(In the path P b in Figure 3.1c, there is only one term in i p i .) Since no
constraints have been imposed on the choice of lengths D and W,take
them such that

2
δ ≥ D + W − D + W 2 (3.4)
which is always possible because the right side in (3.4) is nonnegative for
any D and W. Reverse both the sign and the inequality in (3.4), and add