Evaluation of map quality by matching and scoring high-level, topological map structures

Mapping is an important task for mobile robots. But assessing the quality of maps in a simple, efficient and automated way is not trivial and an ongoing research topic. A new approach on map evaluation is presented here. It is based on Topology Graphs as a topological, abstracted representation of 2D grid maps. The Topology Graphs are derived from Voronoi Diagrams that get post-processed to capture the high-level spatial structures. Based on a similarity metric on vertices in Topology Graphs, the vertices can be matched across maps and spatial (dis)similarities and hence errors in the mapping can be identified and measured. More precisely, the vertex-similarity is the basis to match the structures of Topology Graphs up to the identification of subgraph isomorphisms through wave-front propagation. This allows to determine important map quality attributes up to very challenging structural elements like brokenness, i.e., the number of locally correct partitions in the candidate map and their relative placement towards each other. Experiments with real robot generated maps including examples from various teams in the RoboCup Rescue competition are used to validate the usefulness of this method for map quality assessment.