Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

Fast Frontier Detection for Robot Exploration

Matan Keidar. Fast Frontier Detection for Robot Exploration. Master's Thesis, Bar Ilan University,2012.

Download

[PDF]3.1MB  

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).

Additional Information

BibTeX

@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 Fri Aug 30, 2024 17:29:51