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

80 MOTION PLANNING FOR A MOBILE ROBOT

d(A) is used as a shorthand notation for d(A, T ).
d(A i ) signifies the fact that point A is located on the boundary of the ith
obstacle met by MA on its way to point T .
P is the total length of the path generated by MA on its way from S to T .
p i is the perimeter of ith obstacle encountered by MA.

p i is the sum of perimeters of obstacles met by MA on its way to T ,or
i
of obstacles contained in a specific area of the scene; this quantity will be
used to assess performance of a path planning algorithm or to compare path
planning algorithms.

3.2 UNIVERSAL LOWER BOUND FOR THE PATH
PLANNING PROBLEM

This lower bound, formulated in Theorem 3.2.1 below, informs us what per-
formance can be expected in the worst case from any path planning algorithm
operating within our model. The bound is formulated in terms of the length of
paths generated by MA on its way from point S to point T .Wewill seelater
that the bound is a powerful means for measuring performance of different path
planning procedures.

Theorem 3.2.1 ([58]). For any path planning algorithm satisfying the assump-
tions of our model, any (however large) P> 0, any (however small) D> 0, and
any (however small) δ> 0, there exists a scene in which the algorithm will gen-
erate a path of length no less than P ,

P ≥ D + p i − δ (3.1)
i
where D is the distance between points S and T , and p i are perimeters of obstacles
intersecting the disk of radius D centered at point T .

Proof: We want to prove that for any known or unknown algorithm X a scene
can be designed such that the length of the path generated by X in it will satisfy
2
(3.1). Algorithm X can be of any type: It can be deterministic or random; its
intermediate steps may or may not depend on intermediate results; and so on.
The only thing we know about X is that it operates within the framework of
our model above. The proof consists of designing a scene with a special set of
obstacles and then proving that this scene will force X to generate a path not
shorter than P in (3.1).

2 In Section 3.5 we will learn of a lower bound that is better and tighter: P ≥ D + 1.5 i p i − δ.
The proof of that bound is somewhat involved, so in order to demonstrate the underlying ideas we
prefer to consider in detail the easier proof of the bound (3.1).