Matching maps based on the Area Graph

Topological maps are often used in robotics. This paper presents a novel topological map representation, the Area Graph, and how to extract it from 2D grid maps. This representation is then utilized for map matching, which we present in two variants. Experiments are presented which evaluate these methods and explore the effects of the important parameters. The Area Graph generation algorithm is based on the Voronoi Diagram (VD), which is filtered and pruned to get the Topology Graph. During this process, the faces of the regions are maintained and then used as the areas of the Area Graph, which is then post-processed with a room detection step to avoid over-segmentation. The map matching is utilizing extracted features from the Area Graph and also using the neighborhood information encoded in it to find matching areas. The results of the experiments show that the Area Graph generation algorithm outperforms the other methods in terms of accuracy. Additionally, our matching algorithm is superior to image-based as well as state of the art map matching approaches.