Page 334 - Introduction to AI Robotics

317
Part II
methods fall into two categories: qualitative and quantitative (or metric).
Qualitative path planning methods will be covered in Ch. 9, while metric
methods will be presented in Ch. 10.
Where have I been? Map making is an overlooked aspect of navigation.
As a robot explores new environments, it may be part of its mission to map
the environment. But even if the robot is operating in the same environment
(e.g., delivering mail in an office building), it may improve its performance
by noting changes. A new wall may be erected, furniture rearranged, paint-
ings moved or replaced. Or, as discovered by Xavier, one of the indoor robots
at the Robotics Institute at Carnegie Mellon University, certain hallways and
foyers are too crowded at specific times of the day (end of class, lunchtime)
and should be avoided.
Where am I? In order to follow a path or build a map, the robot has to
know where it is; this is referred to as localization. However, as has already
been seen in Ch. 6, a robot is very poor at dead reckoning. Imagine what
happens to map making when a robot goes around the perimeter of a room
but cannot record its footsteps. Localization can be relative to a local environ-
ment (e.g., the robot is in the center of the room), in topological coordinates
(e.g., in Room 311), or in absolute coordinates (e.g., latitude, longitude, alti-
tude). Both map making and localization are covered in Ch. 11.
The Rhino and Minerva Tour Guide Robots (shown in Fig. II) provide an
excellent example of how these four questions arise naturally in applica-
tions. 139 Rhino and Minerva were designed by researchers from CMU and
the University of Bonn to perform all the functions of a tour guide in a mu-
seum, including leading groups of people to exhibits upon request and an-
swering questions. Rhino hosted tours of the Deutsches Museum in Bonn,
Germany, while Minerva was used in the Smithsonian’s National Museum
of History in Washington, DC.
The tour guide robots had to know where they were at any given time (lo-
calization) in order to answer questions about an exhibit or give directions
to another exhibit. Minerva also could create a custom tour of requested
exhibits, requiring it to know how to get to each of the exhibits (path plan-
ning). The tour path had to be reasonably efficient, otherwise the robot might
have the group pass a targeted exhibit repeatedly before stopping at it. This
also means that the robot had to remember where it had been. Rhino op-
erated using a map of the museum, while Minerva created her own. An
important aspect of the map was that it included the time needed to navi-
gate between exhibits, not just the distance. This time of information allows
a planner to factor in areas to avoid at certain times of day. For example,