Expanding wavefront frontier detection: An approach for efficiently detecting frontier cells

Abstract

Frontier detection is a key step in many robot exploration algorithms. The more quickly frontiers can be detected, the more efficiently and rapidly exploration can be completed. This paper proposes a new frontier detection algorithm called Expanding Wavefront Frontier Detection (EWFD), which uses the frontier cells from the previous timestep as a starting point for detecting the frontiers in the current timestep. As an alternative to simply comparing against the naive frontier detection approach of evaluating all cells in a map, a new benchmark algorithm for frontier detection is also presented, called Naive Active Area frontier detection, which operates in bounded constant time. EWFD and NaiveAA are evaluated in simulations and the results compared against existing state-of-the-art frontier detection algorithms, such as Wavefront Frontier Detection and Incremental-Wavefront Frontier Detection.