Map Representation

In order to navigate through the environment, the robot must create a model of it. There are two approaches to model the environment, the metric or grid-based approach, and the topological approach. Depending on the type of environment one or the other approach is most appropriate. Table 2.1 summarizes the advantages and disadvantages of these two approaches.

Table 2.1: Advantages and disadvantages of grid-based and topological mapping approaches

	Grid-based approaches	Topological approaches
ADVANTAGES	easy to build, represent and maintain non-ambiguous recognition of places and view-point independent facilitates computation of shortest paths	permits efficient planning, low space complexity does not require accurate determination of robot's pose convenient representation for symbolic planner/problem solver
DISADVANTAGES	inefficient and space-consuming planning requires accurate determination of the robot's position poor interface for most symbolic problem solvers	difficult to construct and maintain in large-scale environments if sensor information is ambiguous recognition of places often difficult, sensitive to viewpoint may yield suboptimal paths