Topological segmentation for indoor environments from grid maps using an improved NJW algorithm

In a large-scale indoor environment, a mobile robot needs a proper internal representation of the surrounding environment to carry out its tasks. The metric (grid-based) map and topological map are two common internal representations in robotic realm. In order to take advantage of the two kinds of environmental representations, this paper aims to construct a topological map of an indoor environment from its grid map, which is usually acquired by a SLAM method. The cells on the grid map have three types of states: free, unknown and occupied. After grid map is obtained, the improved NJW method will be applied to cluster the free cells on the grid map. Instead of using the traditionally Euclidean distance, we propose to use the wavefront distance transform algorithm to calculate the distance between each two free cells on the grid map. Based on the segmenting results, we make some optimizations on the boundaries between each two sub-regions. Finally, taking the specific application backgrounds into consideration, we make some discussion on the value of the scale parameter σ and the selection of clusters k. The simulation experiment results show that our improved NJW algorithm has a better performance on topological segmentation of an indoor environment.