Efficient frontier detection and management for robot exploration

The most common way to select target points for sensing during autonomous robot exploration is to employ the concept of frontiers. Frontiers in an occupancy grid map are defined as the boundaries between grid cells categorized as free and unknown. Most of the current single and multi-robot exploration algorithms have focused on developing efficient exploration and coordination strategies, and have used a simple frontier generation scheme that processes the entire occupancy grid map. While this approach is simple, it is not scalable as the map width increases, the computational cost to generate frontiers increases exponentially. This paper presents an efficient approach to generate frontiers by tracking intermediate changes to grid cells and considering only the updated grid cells for the final frontier generation operation. The proposed approach was implemented and simulated in a standard simulator and is evaluated in two different environment types with different map sizes. It was shown that the proposed method provides a significant performance improvement in frontier generation while providing over 85% accuracy.