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

100 MOTION PLANNING FOR A MOBILE ROBOT

Given the fact that no bird’s-eye view of the maze is available to MA (at each
moment it can see only the small cell that it is passing), the MA’s path looks
remarkably efficient and purposeful. (It would look even better if MA’s sensing
was something better than simple tactile sensing; see Figure 3.20 and more on
this topic in Section 3.6.) One reason for this is, of course, that no local cycles
are produced here. In spite of its seeming complexity, this maze is actually an
easy scene for the Bug2 algorithm.
Let’s return to our question, How can we classify in-position situations, so as to
recognize which one would cause troubles to the algorithm Bug2? This question is
not clear at the present time. The answer, likely tied to the topological properties
of the combination (scene, Start, Target), is still awaiting a probing researcher.

3.4 COMBINING GOOD FEATURES OF BASIC ALGORITHMS
Each of the algorithms Bug1 and Bug2 has a clear and simple, and quite distinct,
underlying idea: Bug1 “sticks” to every obstacle it meets until it explores it
fully; Bug2 sticks to the M-line (line (Start, Target)). Each has its pluses and
minuses. Algorithm Bug1 never creates local cycles; its worse-case performance
looks remarkably good, but it tends to be “overcautious” and will never cover
less than the full perimeter of an obstacle on its way. Algorithm Bug2, on the
other hand, is more “human” in that it can “take a risk.” It takes advantage of
simpler situations; it can do quite well even in complex scenes in spite of its
frighteningly high worst-case performance—but it may become quite inefficient,
much more so than Bug1, in some “unlucky” cases.
The difficulties that algorithm Bug2 may face are tied to local cycles—
situations when the robot must make circles, visiting the same points of the
obstacle boundaries more than once. The source of these difficulties lies in what
we called in-position situations (see the Bug2 analysis above). The problem is
of topological nature. As the above estimates of Bug2 “average” behavior show,
its performance in out-positions situations may be remarkably good; these are
situations that mobile robots will likely encounter in real-life scenes.
On the other hand, fixing the procedure so as to handle in-position situations
well would be an important improvement. One simple idea for doing this is to
attempt a procedure that combines the better features of both basic algorithms.
(As always, when attempting to combine very distinct ideas, the punishment will
be the loss of simplicity and elegance of both algorithms.) We will call this
procedure BugM1 (for “modified”) [59]. The procedure combines the efficiency
of algorithm Bug2 in simpler scenes (where MA will pass only portions, instead
of full perimeters, of obstacles, as in Figure 3.5) with the more conservative,
but in the limit the more economical, strategy of algorithm Bug1 (see the bound
(3.7)). The idea is simple: Since Bug2 is quite good except in cases with local
cycles, let us try to switch to Bug1 whenever MA concludes that it is in a local
cycle. As a result, for a given point on a BugM1 path, the number of local cycles