Loop-closing and planarity in topological map-building

Loop-closing has long been recognized as a critical issue when building maps of large-scale environments from local observations. Topological mapping methods abstract the problem of determining the topological structure of the environment (i.e., how loops are closed) from the problem of determining the metrical layout of places in the map and dealing with noisy sensors. A recently developed incremental topological mapping algorithm [E. Remolina et al. (2004), B. Kuipers et al. (2004)] generates all possible topological maps consistent with the experienced sequence of actions and observations and the topological axioms. These are then ordered by a preference criterion such as minimality or probability, to determine the single best map for continued planning and exploration. This paper presents the planarity constraint and analyzes its impact on the search-tree of all topological maps consistent with (non-metrical) exploration experience. Experimental studies demonstrate excellent results even in artificial environments where loop-closing is particularly difficult due to large amounts of perceptual aliasing and structural symmetry.