Page 339 - Introduction to AI Robotics

322
Part II
INFORMATION 4. Information collection. What does this place look like? Have I ever seen it
COLLECTION before? What has changed since the last time I was here?
ROUTE OR Spatial memory takes two forms: route,or qualitative,and layout,or metric,
QUALITATIVE representations. Route representations express space in terms of the connec-
tions between landmarks. An example of a route representation is when a
person gives directions propositionally (as a list): “go out of the parking lot,
and turn left onto Fowler Drive. Look for the museum on the right, and turn
left at next traffic light.” Notice that is perspective dependent; landmarks
that are easy for a human to see may not be visible to a small robot operating
close to the floor. Route representations also tend to supply orientation cues:
“out of the parking lot” (versus being contained in it), “turn left,” “on the
right.” These orientation cues are egocentric, in that they assume the agent
is following the directions at each step.
LAYOUT OR METRIC Layout representations are the opposite of route representations. When a
person gives directions by drawing a map, the map is a layout representa-
tion. Layout representations are often called metric representations because
most maps have some approximate scale to estimate distances to travel. The
major differences between layout and route representations are the view-
point and utility. A layout representation is essentially a bird’s-eye view of
the world. It is not dependent of the perspective of the agent; the agent is
assumed to be able to translate the layout into features to be sensed. The lay-
out is orientation and position independent. Layout representations can be
used to generate a route representation, but this doesn’t necessarily work the
other way. (Consider how easy it is to read a map and give verbal directions
to a driver, versus drawing an accurate map of a road you’ve only been on
once.) Most maps contain extra information, such as cross streets. An agent
can use this information to generate alternative routes if the desired route is
blocked.
While spatial memory is clearly an important key to robust navigation, it
does involve memory, representation, and planning. The successes of the Re-
active Paradigm suggest that for robots “less is more.” Therefore, it merits
considering how much spatial memory an agent needs to navigate. This is a
gray area. The amount of representation needed depends on many factors.
How accurately and efficiently does the robot have to navigate? Is time crit-
ical, or can it take a slightly sub-optimal route? Navigational tasks which
require optimality tend to require more dense and complex world represen-
tations. What are the characteristics of the environment? Are there land-
marks to provide orientation cues? Are distances known accurately? What