A Graph-Based Method for Efficient Frontier Detection and Traversability Assessment in Autonomous Exploration

Autonomous exploration has become a widely adopted capability that enables robots to navigate and map unknown environments without human intervention. However, conventional methods often suffer from limited efficiency due to the costly process of extracting frontiers - the boundaries between known free space and unknown space - which typically requires scanning all grid cells in the occupancy map. Moreover, these methods usually neglect the traversability of frontier regions, which may lead to infeasible navigation goals and failed exploration attempts. This paper proposes a graph-based frontier extraction method for autonomous exploration, enhanced with a traversability check to filter infeasible goals. First, a topological graph is constructed by performing spatially uniform sampling on the occupancy map, where edges are added between neighboring nodes only if the connecting paths are traversable. Then, the amount of unknown space surrounding each peripheral node is evaluated to identify frontier nodes - nodes adjacent to unexplored regions. Finally, the identified frontier nodes are clustered to generate representative frontier points for navigation planning. Experimental results demonstrate that the proposed method reduces computational complexity by more than 50%, while maintaining comparable task completion time. Furthermore, it successfully filters out frontiers that are detected but unreachable, thereby avoiding invalid navigation attempts. The practical applicability of the proposed method has been validated in real-world robotic exploration scenarios. The open-source code is available at https://github.com/joooyce7666/GraphExplorer.git.