This paper describes a graph search-based exploration method. Segmented frontier nodes and their relative transformations constitute a frontier-graph structure. Frontier detection and segmentation are performed using local grid maps of adjacent nodes. The proposed frontier-graph structure can systematically manage local information according to the exploration state and overcome the problem caused by updating a single global grid map. The robot selects the next target using breadth-first search (BFS) exploration of the frontier-graph. The BFS exploration is improved to generate an efficient loop-closing sequence between adjacent nodes. We verify that our BFS-based exploration method can gradually extend the frontier-graph structure and efficiently map the entire environment, regardless of the starting position.
Keywords: breadth-first search; depth-first search; exploration; frontier detection; loop-closing; mobile robots.