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

OTHER APPROACHES 125

this Class. Their dogmatically reaching the upper performance bound in the most
simple scenes, where a more agile strategy would likely do much better, does not
leave much room for creativity. Besides, Bug1 does already reach the universal
lower bound (3.13) of the sensor-based motion planning problem, so there is not
much one can expect in advancing theory.
Performance aside, one may wonder how much variety there is in Class 1.
Most likely not much, but we do not know for sure.
This makes Bug1 an unrivaled champion among “tactile” algorithms—a some-
what ironic title, given that Bug1 is not a likely candidate for real-world robots,
except perhaps in special applications. One such application is generation of the
outline of a scene in question, which is producing contours of obstacles present
in the scene. You supply the robot with a few pairs of S and T points to ensure
that it will visit all obstacles of interest, make sure that it stores the files of coor-
dinates while walking around obstacles, and let it go. As a side product of those
trips, the robot will bring back a map of the scene. The technique is especially
good for obtaining such outlines and contours in a database, with an imaginary
point robot. This method of obtaining the map, while not theoretically sound, is
7
quite competitive compared to other techniques. With this technique the robot
cannot, of course, uncover pieces of free space trapped inside obstacles, unless
the robot explicitly starts there.
The situation is more interesting with Class 2 algorithms, including extensions
to vision and range sensing. If the Bug family (as some researchers started calling
these procedures) is to grow, this will likely be happening in Class 2. Between
1984 and now (1984 being the year of first publications on sensor-based motion
planning), over a dozen provable algorithms from this class have been reported
in the literature. Besides, many heuristic procedures relying on the “engineering
approach” have been described; their convergence and performance properties in
arbitrary scenes is anybody’s guess.
The following brief review of significant work on provable Class 2 sensor-
based algorithms is admittedly incomplete. Ideas similar to those explored in
this book—that is, with a focus on topological rather than geometrical prop-
erties of space—has been considered by a number of researchers. Algorithms
Alg1 and Alg2 by Sankaranarayanan and Vidyasagar [65] successfully fight the
unpleasant tendency of the Bug2 algorithm to produce multiple local cycles in
some special scenes (see Section 3.5). Whereas local cycles can be stopped via
a straightforward combination of Bug1 and Bug2 procedures (see the BugM1
algorithm, Section 3.5), Alg1 and Alg2 do it better and they do it more econom-
ically. Importantly, they reach the path length lower bound (3.14) for the Class 2
algorithms, and by doing so they “close” the Class 2 of sensor-based planning
algorithms, similar to how Bug1 closes Class 1.
Also in this group are elegant provable algorithms TangentBug [66] by Kamon,
Rivlin, and Rimon, and DistBug [67, 68] by Kamon and Rivlin. Algorithm
7 This is not to suggest that Bug1 is an algorithm for map-making. Map-making (terrain acquisition
and terrain coverage are other terms one finds in literature) is a different problem. See, for example,
Ref. 1.