Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration

Quin, Phillip and Nguyen, Dac Dang Khoa and Vu, Thanh Long and Alempijevic, Alen and Paul, Gavin (2021) Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration. Frontiers in Robotics and AI, 8. ISSN 2296-9144

[thumbnail of pubmed-zip/versions/2/package-entries/frobt-08-616470.pdf] Text
pubmed-zip/versions/2/package-entries/frobt-08-616470.pdf - Published Version

Download (3MB)

Abstract

Many robot exploration algorithms that are used to explore office, home, or outdoor environments, rely on the concept of frontier cells. Frontier cells define the border between known and unknown space. Frontier-based exploration is the process of repeatedly detecting frontiers and moving towards them, until there are no more frontiers and therefore no more unknown regions. The faster frontier cells can be detected, the more efficient exploration becomes. This paper proposes several algorithms for detecting frontiers. The first is called Naïve Active Area (NaïveAA) frontier detection and achieves frontier detection in constant time by only evaluating the cells in the active area defined by scans taken. The second algorithm is called Expanding-Wavefront Frontier Detection (EWFD) and uses frontiers from the previous timestep as a starting point for searching for frontiers in newly discovered space. The third approach is called Frontier-Tracing Frontier Detection (FTFD) and also uses the frontiers from the previous timestep as well as the endpoints of the scan, to determine the frontiers at the current timestep. Algorithms are compared to state-of-the-art algorithms such as Naïve, WFD, and WFD-INC. NaïveAA is shown to operate in constant time and therefore is suitable as a basic benchmark for frontier detection algorithms. EWFD and FTFD are found to be significantly faster than other algorithms.

Item Type: Article
Subjects: Institute Archives > Mathematical Science
Depositing User: Managing Editor
Date Deposited: 29 Jun 2023 03:28
Last Modified: 11 Oct 2023 03:53
URI: http://eprint.subtopublish.com/id/eprint/2596

Actions (login required)

View Item
View Item