Spectral clustering for feature-based metric maps partitioning in a hybrid mapping framework

Hybrid maps combine metric and topological information for efficiently managing large-scale environments. In a feature-based mapping framework, this paper describes the application of a spectral clustering approach for automatically detecting the transitions between subsequently traversed local maps. Contrary to recently proposed approaches, this algorithm considers each individual map feature as a node of a graph whose edges link two nodes if they are simultaneously observed. Thus, given a sequence of observations, an auxiliary graph is incrementally built whose edges carry non-negative weights according to the locality of the features. Given a feature, its locality defines the set of features that has been observed simultaneously with it at least once. At each execution of the mapping approach, the feature-based graph is split into two subgraphs using a normalized spectral clustering algorithm. If the graph partition is validated, the algorithm determines that the robot is moving into a new area and a new local map is generated. We have tested the proposed approach in real environments where features are obtained using 2D laser sensors or vision. Experimental results demonstrate the performance of the proposal.