The way in which the environment is represented has an important impact on the performance of the robot. Accurate maps are fundamental for navigation. One way to des cribe the environment is to use a detailed geometrical description of all the objects in it. These spatial representations can be very accurate and are well suited f or various important tasks like motion control and accurate localization. A fundamental question when representing the environment geometrically is the choice of geo metrical primitive to be used. Using lines, for example, imposes a linear structure on the underlying environment. This is well suited for some environments such as an office, but can be inappropriate for others. Points are the most general geometrical primitive. Using points allows different environments to be accurately repres ented without imposing any geometrical structure on them.

To construct a map, the information about the environment perceived by the robot is used. This information can be, for example, the distance to the objects detected by the robot's sensors while moving through the environment. Using the distance measurements directly in the way they are produced by the sensors is straight-forward and general since it does not rely on the environment having some specific features. By converting these measurements into a set of points in an absolut coordinate system a \emph{sample-based} map is constructed. Such a map constitutes a point-based geometrical representation of the environment where each point or sample corres ponds to a measurement made by the robot. Thus, beside their accuracy and generality, sample-based maps are also consistent with the observations.

This thesis investigates the idea of using samples to model the environment and presents different techniques for generating sample-based maps from the distance meas urements acquired by the robot. We seek to find an efficient representation to accurately describe the environment. Obviously, if all the measurements acquired by th e robot are used, the resulting map would be the best representation of the environment given that data. Distance measurements, however, come in large amounts and ma y lead to too large models. Additionally, not every sample contributes in the same way to the representation, and we may be interested in representing the environmen t using fewer samples. Thus, our goal is to find a subset of the complete dataset to efficiently represent the environment.

The contribution of this thesis are the various approaches to generate sample-based geometrical maps from range measurements gathered with a mobile robot as an effic ient representation of the environment. Sample-based maps are general in the sense that they are not limited to a specific type of environment and by using points as primitives for the representation do not impose any structure to the environment that is being represented. Additionally, sample-based maps are consistent with the data since they do not contain spurious points. Every point in a sample based map can be explained by an existing measurement.