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

96    MOTION PLANNING FOR A MOBILE ROBOT

                                              T




















                                              S

                             Figure 3.9  Illustration for Theorem 3.3.4.

           defined hit point. Now, move from Q along the already generated path segment
           in the direction opposite to the accepted local direction, until the closest hit point
                                                   j
           on the path is encountered; say, that point is H . We are interested only in those
           cases where Q is involved in at least one local cycle—that is, when MA passes
                                                                           j
           point Q more than once. For this event to occur, MA has to pass point H at
                                                              j
           least as many times. In other words, if MA does not pass H more than once, it
           cannot pass Q more than once.
              According to the Bug2 procedure, the first time MA reaches point H j  it
           approaches it along the M-line (straight line (Start, Target))—or, more precisely,
           along the straight line segment (L j−1 ,T ). MA then turns left and starts walking
           around the obstacle. To form a local cycle on this path segment, MA has to
                          j
           return to point H again. Since a point can become a hit point only once (see the
                                                               j
           proof for Lemma 3.3.4), the next time MA returns to point H it must approach
           it from the right (see Figure 3.9), along the obstacle boundary. Therefore, after
                          j
           having defined H , in order to reach it again, this time from the right, MA must
           somehow cross the M-line and enter its right semiplane. This can take place in
           one of only two ways: outside or inside the interval (S, T ). Consider both cases.
              1. The crossing occurs outside the interval (S, T ). This case can correspond
                only to an in-position configuration (see Definition 3.3.2). Theorem 3.3.4,
                therefore, does not apply.
              2. The crossing occurs inside the interval (S, T ). We want to prove now
                that such a crossing of the path with the interval (S, T ) cannot produce
                local cycles. Notice that the crossing cannot occur anywhere within the
                            j
                interval (S, H ) because otherwise at least a part of the straight-line seg-
                             j
                ment (L j−1 ,H ) would be included inside the obstacle. This is impossible
   116   117   118   119   120   121   122   123   124   125   126