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

86 MOTION PLANNING FOR A MOBILE ROBOT

If point S happens to be on an obstacle boundary and the line (S, T ) crosses that
obstacle, then D = d(H 1 ).
According to our model, if MA’s path touches an obstacle tangentially, then
MA needs not walk around it; it will simply continue its straight-line walk toward
point T . In all other cases of meeting an ith obstacle, unless point T lies on
an obstacle boundary, a relation d(H i )>d(L i ) holds. This is because, on the
one hand, according to the model, any straight line (except a line that touches
the obstacle tangentially) crosses the obstacle at least in two distinct points.
This is simply a reflection of the finite “thickness” of obstacles. On the other
hand, according to algorithm Bug1, point L i is the closest point from obstacle
i to point T . Starting from L i , MA walks straight to point T until (if ever) it
meets the (i + 1)th obstacle. Since, by the model, obstacles do not touch one
another, then d(L i )>d(H i+1 ). Our sequence of distances, therefore, satisfies
the relation

d(H 1 )>d(L 1 )>d(H 2 )>d(L 2 )>d(H 3 )> d(L 3 )... (3.6)

where d(H 1 ) is or is not equal to D.Since d(L i ) is the shortest distance from the
ith obstacle to point T , and since (3.6) guarantees that algorithm Bug1 monoton-
ically decreases the distances d(H i ) and d(L i ) to point T , Lemma 3.3.1 follows.
Q.E.D.

The important conclusion from Lemma 3.3.1 is that algorithm Bug1 guarantees
to never create cycles.

Corollary 3.3.1. Under Bug1, independent of the geometry of an obstacle, MA
defines on it no more than one hit and no more than one leave point.

To assess the algorithm’s performance—in particular, we will be interested
in the upper bound on the length of paths that it generates—an assurance is
needed that on its way to point T , MA can encounter only a finite number
of obstacles. This is not obvious: While following the algorithm, MA may be
“looking” at the target not only from different distances but also from different
directions. That is, besides moving toward point T , it may also rotate around it
(see Figure 3.3). Depending on the scene, this rotation may go first, say, clock-
wise, then counterclockwise, then again clockwise, and so on. Hence we have
the following lemma.

Lemma 3.3.2. Under Bug1, on its way to the Target, MA can meet only a finite
number of obstacles.

Proof: Although, while walking around an obstacle, MA may sometimes be
at distances much larger than D from point T (see Figure 3.3), the straight-
line segments of its path toward the point T are always within the same circle
of radius D centered at point T . This is guaranteed by inequality (3.6). Since,