Poly line map extraction in sensor-based mobile robot navigation using a consecutive clustering algorithm

In this paper a new technique is presented for online mapping of unknown indoor environments using laser range data scans performed by a mobile robot. The developed algorithm hierarchically utilizes clustering methods to convert data points into point-clusters and eventually to line-segments. In addition to using the KK-means algorithm to form appropriate point-clusters, the Rank Order Clustering (ROC) technique is used for the first time in mapping, where no preset number of clusters is required for recognizing line clusters. To do this, a set of five fuzzy membership functions are designed for calculating the Similarity Index Matrix (SIM) of line-segments, after which line-segments lying in each cluster are merged to form the final perceived lines in the constructed map. The map-building process is performed dynamically: it incrementally adds new lines to the previously calculated map-lines and merges them with the overall map. Various simulations exhibit favorable results for a mobile robot navigating in indoor environments, both with static and dynamic obstacles.