Page 365 - Introduction to AI Robotics

348
9.6 Summary 9 Topological Path Planning
Landmarks simplify the where am I? problem by providing orientation cues.
Gateways are a special case of landmarks which reflect a potential for the
robot to change directions (turn down a different road or hall, enter a room,
etc.). There are two categories of qualitative navigation methods: relational
and associative. Relational methods relate distinctive places (nodes) to each
other by the local control strategies (lcs), or behaviors, needed to travel between
them (edges), forming a graph. The robot can use the graph to plan a path us-
ing techniques such as the single source shortest path algorithm. It executes
the path by employing the behavior associated with that edge it is travers-
ing. When it sees the landmark of the location, it is in the neighborhood, and
then can use another behavior, such as hill-climbing, to localize itself rela-
tive to the landmark. Associative methods directly couple perception with
acting. An image can be compared to a image signature or a viewframe to
generate the next movement for the robot to take. Relational methods are
commonly used for topological navigation.

9.7 Exercises

Exercise 9.1
List the four questions associated with navigation.
Exercise 9.2
List and describe the criteria for evaluating a path planner.

Exercise 9.3
Describe the difference between route and metric representations of space.

Exercise 9.4
Define the difference between natural and artificial landmarks and give one example
of each.
Exercise 9.5
Define a gateway. What gateways would be in a museum? What sensors would be
needed to reliably detect them?
Exercise 9.6
Build a relational graph representation labeling the distinctive places and local con-
trol strategies using gateways for a floor of a building on campus.