Page 222 - Introduction to Autonomous Mobile Robots

Mobile Robot Localization

Figure 5.17 207
Example of an occupancy grid map representation (courtesy of S. Thrun [145]).

occupancy grid must have memory set aside for every cell in the matrix. Furthermore, any
fixed decomposition method such as this imposes a geometric grid on the world a priori,
regardless of the environmental details. This can be inappropriate in cases where geometry
is not the most salient feature of the environment.
For these reasons, an alternative, called topological decomposition, has been the subject
of some exploration in mobile robotics. Topological approaches avoid direct measurement
of geometric environmental qualities, instead concentrating on characteristics of the envi-
ronment that are most relevant to the robot for localization.
Formally, a topological representation is a graph that specifies two things: nodes and the
connectivity between those nodes. Insofar as a topological representation is intended for the
use of a mobile robot, nodes are used to denote areas in the world and arcs are used to
denote adjacency of pairs of nodes. When an arc connects two nodes, then the robot can
traverse from one node to the other without requiring traversal of any other intermediary
node.
Adjacency is clearly at the heart of the topological approach, just as adjacency in a cell
decomposition representation maps to geometric adjacency in the real world. However, the
topological approach diverges in that the nodes are not of fixed size or even specifications
of free space. Instead, nodes document an area based on any sensor discriminant such that
the robot can recognize entry and exit of the node.
Figure 5.18 depicts a topological representation of a set of hallways and offices in an
indoor environment. In this case, the robot is assumed to have an intersection detector, per-
haps using sonar and vision to find intersections between halls and between halls and