1Incremental Topological Segmentation for Semi-structured Environments

Abstract—In the last decades, topological segmentation has been much studied, especially for structured environments. It is an important approach to provide preliminary results for further semantic labeling or topological navigation, for instance. However, topological segmentation for semi-structured environ-ments is challenging, since the definition of regions in those environments is difficult. Compared with indoor environments, semi-structured environments do not contain areas that can be intuitively categorized into rooms, corridors etc. Moreover, the assessment of the quality of a segmentation result is vague. In this work, we first propose a set of criteria to assess the quality of topological segmentation. These criteria provide a general benchmark for different segmentation algorithms. Then we introduce an incremental approach to create topological seg-mentation for semi-structured environments. Our novel approach is based on spectral clustering of an incremental generalized Voronoi decomposition for metric maps. It extracts sparse spatial information from the maps, and builds an environment model which aims at simplifying the navigation task for mobile robots. Experimental results in real semi-structured environments show the robustness and the quality of the topological map created by the proposed method. An extended set of repetitive ex-periments for urban search and rescue missions were performed to show the global consistency of 6 different runs of incremental segmentation, during which the test robot traveled 1.8 km in total