Page 345 - Introduction to AI Robotics

328
9 Topological Path Planning

Figure 9.1 Artificial landmarks used in the 1992 AAAI Mobile Robot Competition.
(Photograph courtesy of AAAI.)

9.3 Relational Methods

Relational methods represent the world as a graph or network of nodes and
edges. Nodes represent gateways, landmarks, or goals. Edges represent
a navigable path between two nodes, in effect that two nodes have a spa-
tial relationship. Additional information may be attached to edges, such
as direction (N,S,E,W), approximate distance, terrain type, or the behaviors
needed to navigate that path. Paths can be computed between two points us-
ing standard graph algorithms, such as Dijkstra’s single source shortest path
algorithm. (See any algorithm textbook for details.)
One of the earliest investigations of relational graphs for navigation was by
Smith and Cheeseman. 133 They represented the world as a relational graph,
where the edges represented the direction and distance between nodes. They