Histogram based frontier exploration

Abstract

This paper proposes a method for mobile robot exploration based on the idea of frontier exploration which suggests navigating the robot toward the boundaries between free and unknown areas in the map. A global occupancy grid map of the environment is constantly updated, based on which a global frontier map is calculated. Then, a histogram based approach is adopted to cluster frontier cells and score these clusters based on their distance from the robot as well as the number of frontier cells they contain. In each stage of the algorithm, a sub-goal is set for the robot to navigate. A combination of distance transform and A* search algorithms is utilized to generate a plausible path toward the sub-goal through the free space. This way keeping a reliable distance from obstacles is guaranteed while searching for the shortest path toward the sub-goal. When such a path is generated, a B-spline interpolated and smoothed trajectory is produced as the control reference for the mobile robot to follow. The whole process is iterated until no unexplored area remains in the map. The efficiency of the method is shown through simulated and real experiments.