Extracting topology-based maps from gridmaps

We propose topology-based maps as a new representation of the workspace of a mobile robot. These maps capture the structure of the free space in the environment in terms of the basic topological notions of connectivity and adjacency. Topology-based maps can be automatically extracted from an occupancy grid built from sensor data using techniques borrowed from the image processing field. Since these techniques can be soundly defined on fuzzy values, our approach is well suited to deal with the uncertainty inherent in the sensor data. Topology-based maps are fairly robust with respect to sensor noise and to small environmental changes, and have nice computational properties