TABLE OF CONTENTS As described in chapters 2 and 4, a planner plans a path from a particular start configuration to a particular goal configuration. If we knew that many paths were to be planned in the same environment, then it would make sense to construct a data structure once and then use that data structure to plan subsequent paths more quickly. This data structure is often called a map, and mapping is the task of generating models of robot environments from sensor data. Mapping is important when the robot does not have a priori information about its environment and must rely on its sensors to gather information to incrementally construct its map. In the context of indoor systems, three map concepts prevail: topological, geometric, and grids (see figure 5.1).
Topological representations aim at representing environments with graphlike structures, where nodes correspond to "something distinct" and edges represent an adjacency relationship between nodes. For example, places may be locations with specific distinguishing features, such as intersections and T-junctions in an office building, and edges may correspond to specific behaviors or motion commands that enable the robot to move from one location to another, such as wall-following. Recently, it has become popular to augment topological maps with metric information (e.g., relative distance, angle) to help disambiguate places that "look" the same [108,250,382,418] or to use them for navigation [188,213,240,339].
Geometric models use geometric primitives for representing the...
