Cargando…
Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration
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 th...
Autores principales: | , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Frontiers Media S.A.
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7959836/ https://www.ncbi.nlm.nih.gov/pubmed/33732732 http://dx.doi.org/10.3389/frobt.2021.616470 |
_version_ | 1783665037875871744 |
---|---|
author | Quin, Phillip Nguyen, Dac Dang Khoa Vu, Thanh Long Alempijevic, Alen Paul, Gavin |
author_facet | Quin, Phillip Nguyen, Dac Dang Khoa Vu, Thanh Long Alempijevic, Alen Paul, Gavin |
author_sort | Quin, Phillip |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-7959836 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Frontiers Media S.A. |
record_format | MEDLINE/PubMed |
spelling | pubmed-79598362021-03-16 Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration Quin, Phillip Nguyen, Dac Dang Khoa Vu, Thanh Long Alempijevic, Alen Paul, Gavin Front Robot AI Robotics and AI 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. Frontiers Media S.A. 2021-02-25 /pmc/articles/PMC7959836/ /pubmed/33732732 http://dx.doi.org/10.3389/frobt.2021.616470 Text en Copyright © 2021 Quin, Nguyen, Vu, Alempijevic and Paul. http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) and the copyright owner(s) are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms. |
spellingShingle | Robotics and AI Quin, Phillip Nguyen, Dac Dang Khoa Vu, Thanh Long Alempijevic, Alen Paul, Gavin Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title | Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title_full | Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title_fullStr | Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title_full_unstemmed | Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title_short | Approaches for Efficiently Detecting Frontier Cells in Robotics Exploration |
title_sort | approaches for efficiently detecting frontier cells in robotics exploration |
topic | Robotics and AI |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7959836/ https://www.ncbi.nlm.nih.gov/pubmed/33732732 http://dx.doi.org/10.3389/frobt.2021.616470 |
work_keys_str_mv | AT quinphillip approachesforefficientlydetectingfrontiercellsinroboticsexploration AT nguyendacdangkhoa approachesforefficientlydetectingfrontiercellsinroboticsexploration AT vuthanhlong approachesforefficientlydetectingfrontiercellsinroboticsexploration AT alempijevicalen approachesforefficientlydetectingfrontiercellsinroboticsexploration AT paulgavin approachesforefficientlydetectingfrontiercellsinroboticsexploration |