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

BASIC ALGORITHMS 99

Test for Target Reachability. If, on the pth local cycle, p = 0, 1,... ,after
j
having defined a hit point H , MA returns to this point before it defines at least
k
j
the first two out of the possible set of points L ,H j+1 ,... ,H , this means that
MA has been trapped and hence the target is not reachable.
We have learned that in in-position situations algorithm Bug2 may become
inefficient and create local cycles, visiting some areas of its path more than
once. How can we characterize those situations? Does starting or ending “inside”
the obstacle—that is, having an in-position situation—necessarily lead to such
inefficiency? This is clearly not so, as one can see from the following example of
Bug2 operating in a maze (labyrinth). Consider a version of the labyrinth problem
where the robot, starting at one point inside the labyrinth, must reach some
other point inside the labyrinth. The well-known mice-in-the-labyrinth problem
4
is sometimes formulated this way. Consider an example shown in Figure 3.11.

T

S

Figure 3.11 Example of a walk (dashed line) in a maze under algorithm Bug2. S,Start;
T ,Target.

4 To fit the common convention of maze search literature, we present a discrete version of the
continuous path planning problem: The maze is a rectangular cell structure, with each cell being a
little square; any cell crossed by the M-line (straight line (S, T )) is considered to be lying on the
line. This same discussion can be carried out using an arbitrary curvilinear maze.