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

126 MOTION PLANNING FOR A MOBILE ROBOT

TangentBug, in turn, has inspired procedures WedgeBug and RoverBug [69, 70]
by Laubach, Burdick, and Matthies, which try to take into account issues spe-
cific for NASA planet rover exploration. A number of schemes with and without
proven convergence have been reported by Noborio [71].
Given the practical needs, it is not surprising that many attempts in sensor-
based planning strategies focus on distance sensing—stereo vision, laser range
sensing, and the like. Some earlier attempts in this area tend to stick to more
familiar graph-theoretical approaches of computer science, and consequently treat
space in a discrete rather than continuous manner. A good example of this
approach is the visibility-graph based approach by Rao et al. [72].
Standing apart is the approach described by Choset et al. [73, 74], which
can be seen as an attempt to fill the gap between the two paradigms, motion
planning with complete information (Piano Mover’s model) and motion planning
with incomplete information [other names are sensor-based planning, or Sens-
ing–Intelligence–Motion (SIM)]. The idea is to use sensor-based planning to
first build the map and then the Voronoi diagram of the scene, so that the future
robot trips in this same area could be along shorter paths—for example, along
links of the acquired Voronoi diagram. These ideas, and applications that inspire
them, are different from the go-from-A-to-B problem considered in this book and
thus beyond our scope. They are closer to the systematic space exploration and
map-making. The latter, called in the literature terrain acquisition or terrain cov-
erage, might be of use in tasks like robot-assisted map-making, floor vacuuming,
lawn mowing, and so on (see, e.g., Refs. 1 and 75).
While most of the above works provide careful analysis of performance and
convergence, the “engineering approach” heuristics to sensor-based motion plan-
ning procedures usually discuss their performance in terms of “consistently better
than” or “better in our experiments,” and so on. Since idiosyncracies of these
algorithms are rarely analyzed, their utility is hard to assess. There have been
examples when an algorithm published as provable turned out to be ruefully
divergent even in simple scenes. 8
Related to the area of two-dimensional motion planning are also works directed
toward motion planning for a “point robot” moving in three-dimensional space.
Note that the increase in dimensionality changes rather dramatically the formal
foundation of the sensor-based paradigm. When moving in the (two-dimensional)
plane, if the point robot encounters an obstacle, it has a choice of only two ways
to pass around it: from the left or from the right, clockwise or counterclockwise.
When a point robot encounters an object in the three-dimensional space, it is
faced with an infinite number of directions for passing around the object. This
means that unlike in the two-dimensional case, the topological properties of three-
dimensional space cannot be used directly anymore when seeking guarantees of
algorithm completeness.

8 As the principles of design of motion planning algorithms have become clearer, in the last 10–15
years the level of sophistication has gone up significantly. Today the homework in a graduate course
on motion planning can include an assignment to design a new provable sensor-based algorithm, or
to decide if some published algorithm is or is not convergent.