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

BASIC ALGORITHMS 87

ob 2

L 1 L 2

H 2 H 2

ob 1 T

ob 3 L 3

S H 1

Figure 3.3 Algorithm Bug1. Arrows indicate straight-line segments of the robot’s path.
Path segments around obstacles are not shown; they are similar to those in Figure 3.2.

according to our model, any disc of finite radius can intersect only a finite number
of obstacles, the lemma follows. Q.E.D.

Corollary 3.3.2. The only obstacles that MA can be meet under algorithm Bug1
are those that intersect the disk of radius D centered at target T .

Together, Lemma 3.3.1, Lemma 3.3.2, and Corollary 3.3.2 guarantee conver-
gence of the algorithm Bug1.

Theorem 3.3.1. Algorithm Bug1 is convergent.

We are now ready to tackle the performance of algorithm Bug1. As discussed, it
will be established in terms of the length of paths that the algorithm generates. The
following theorem gives an upper bound on the path lengths produced by Bug1.

Theorem 3.3.2. The length of paths produced by algorithm Bug1 obeys the limit,

P ≤ D + 1.5 · p i (3.7)
i

where D is the distance (Start, Target), and i p i includes perimeters of obstacles
intersecting the disk of radius D centered at the Target.