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

GOING AFTER TIGHTER BOUNDS 103

3.5 GOING AFTER TIGHTER BOUNDS

The above analysis raises two questions:

1. There is a gap between the bound given by (3.1), P ≥ D + p i − δ (the
i
universal lower bound for the planning problem), and the bound given by

(3.7), P ≤ D + 1.5 · p i (the upper bound for Bug1 algorithm).
i
What is there in the gap? Can the lower bound (3.1) be tightened
upwards—or, inversely, are there algorithms that can reach it?
2. How big and diverse are Classes 1 and 2?

To remind the reader, Class 1 combines algorithms in which the robot never
leaves an obstacle unless and until it explores it completely. Class 2 combines
algorithms that are complementary to those in Class 1: In them the robot can
leave an obstacle and walk further, and even return to this obstacle again at
some future time, without exploring it in full.
A decisive step toward answering the above questions was made in 1991 by
A. Sankaranarayanan and M. Vidyasagar [60]. They proposed to (a) analyze the
complexity of Classes 1 and 2 of sensor-based planning algorithms separately and
(b) obtain the lower bounds on the lengths of generated paths for each of them.
This promised tighter bounds compared to (3.1). Then, since together both classes
cover all possible algorithms, the lower of the obtained bounds would become
the universal lower bound. Proceeding in this direction, Sankaranarayanan and
Vidyasagar obtained the lower bound for Class 1 algorithms as

P ≥ D + 1.5 p i (3.13)
i

and the lower bound for Class 2 algorithms as

P ≥ D + 2 · p i (3.14)
i
As before, P is the length of a generated path, D is the distance (Start, Target),
and p i refers to perimeters of obstacles met by the robot on its way to the target.
There are three important conclusions from these results:

• It is the bound (3.13), and not (3.1), that is today the universal lower bound:
in the worst case no sensor-based motion planning algorithm can produce a
path shorter than P in (3.13).
• According to the bound (3.13), algorithm Bug1 reaches the universal lower
bound. That is, no algorithm in Class 1 will be able to do better than Bug1
in the worst case.
• According to bounds (3.13) and (3.14), in the worst case no algorithm from
either of the two classes can do better than Bug1.