• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Matan Keidar. Fast Frontier Detection for Robot Exploration. Master's Thesis, Bar Ilan University,2012.
Frontier-based exploration is the most common approach to exploration, a fundamental problem in robotics. In frontier-based exploration, robots explore by repeatedly computing (and moving towards) frontiers, the segments which separate the known regions from those unknown. However, most frontier detection algorithms process the entire map data. This can be a time consuming process which slows down the exploration. In this thesis, we present two novel frontier detection algorithms: WFD, a graph search based algorithm and FFD, which is based on processing only the new laser readings data. In contrast to state-of-the-art methods, both algorithms do not process the entire map data. This thesis contains a theoretical complexity analysis for both algorithms and since FFD is a novel approach, we proof its correctness. We succeeded to improve WFD and FFD performance even further by combining them into two new algorithms called WFD-INC and WFD-IP. We implemented all algorithms and showed that all are faster than a state-of-the-art frontier detector implementation (by several orders of magnitude).
@MastersThesis{matan-msc,
author = {Matan Keidar},
title = {Fast Frontier Detection for Robot Exploration},
school = {{B}ar {I}lan {U}niversity},
year = {2012},
OPTkey = {},
OPTtype = {},
OPTaddress = {},
OPTmonth = {},
OPTnote = {Available at \url{http://www.cs.biu.ac.il/~galk/Publications/b2hd-matan-msc.html}},
OPTannote = {},
wwwnote = {},
abstract = {
Frontier-based exploration is the most common approach to exploration, a fundamental problem
in robotics. In frontier-based exploration, robots explore by repeatedly computing (and moving
towards) frontiers, the segments which separate the known regions from those unknown. However,
most frontier detection algorithms process the entire map data. This can be a time consuming
process which slows down the exploration. In this thesis, we present two novel frontier detection
algorithms: WFD, a graph search based algorithm and FFD, which is based on processing only
the new laser readings data. In contrast to state-of-the-art methods, both algorithms do not process
the entire map data. This thesis contains a theoretical complexity analysis for both algorithms
and since FFD is a novel approach, we proof its correctness. We succeeded to improve WFD
and FFD performance even further by combining them into two new algorithms called WFD-INC
and WFD-IP. We implemented all algorithms and showed that all are faster than a state-of-the-art
frontier detector implementation (by several orders of magnitude).
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Mon Feb 03, 2025 16:33:37