Frontier Exploration Technique for 3D Autonomous SLAM Using K-Means Based Divisive Clustering

Autonomous mapping of unknown environments is a well-known problem in the field of robotics. The autonomous mapping process involves localisation, mapping, and exploration. With the emergence of unmanned aerial vehicles, there is now a need for autonomous exploration algorithms that work in tandem with simultaneous localisation and mapping (SLAM) algorithms to map three dimensional spaces efficiently. Frontier based exploration technique is a frequently used autonomous exploration strategy for two dimensional environments. This paper proposes a modified frontier based exploration technique for efficient mapping of three dimensional environments. A novel approach is presented wherein the three dimensional space is divided into cells of fixed resolution. Frontier cells which represent the boundary between known and unknown regions are identified and then clustered using a combination of k-means and divisive clustering. A unique cost function is then evaluated to choose an optimal cluster to visit. Finally, Dijkstra's shortest path algorithm is applied to choose intermediate clusters that can be visited while travelling to the chosen optimal cluster in order to increase the efficiency of the proposed technique. A simulation based model is developed on the popular Robot Operating System platform and the proposed method is tested on two different simulated environments. To validate the efficacy of the method, it is compared with the classic nearest frontier exploration technique.