@COMMENT This file was generated by bib2html.pl version 0.94
@COMMENT written by Patrick Riley
@COMMENT This file came from Gal A. Kaminka's publication pages at
@COMMENT http://www.cs.biu.ac.il/~galk/publications/
@Article{ijrr14,
author={Matan Keidar and Gal A. Kaminka},
title = {Efficient Frontier Detection for Robot Exploration},
journal = IJRR,
year = {2014},
OPTkey = {},
volume = {33},
number = {2},
pages = {215--236},
OPTmonth = {February},
OPTurl = {},
OPTdoi = {10.1177/0278364913494911},
wwwnote = {The article's web page on the journal home is at http://ijr.sagepub.com/content/early/2013/10/22/0278364913494911},
OPTnote = {In press.},
OPTannote = {},
abstract = {Frontier-based exploration is the most common approach to exploration, a fundamental
problem in robotics. In frontier-based exploration, robots explore by repeatedly detecting (and moving
towards) frontiers, the segments which separate the known regions from those unknown. A frontier
detection sub-process examines map and/or sensor readings to identify frontiers for exploration.
However, most frontier detection algorithms process the entire map data. This can be a time
consuming process, which affects the exploration decisions. In this work, we present several novel
frontier detection algorithms that do not process the entire map data, and explore them in depth. We begin
by investigating algorithms that represent two approaches: WFD, a graph search based algorithm
which examines only known areas, and FFD, which examines only new laser readings data. We analytically
examine the complexity of both algorithms, and discuss their correctness. We then improve by
combining elements of both, to create two additional algorithms, called WFD-INC and WFD-IP.
We empirically evaluate all algorithms, and show that they are all faster than a state-of-the-art
frontier detector implementation (by several orders of magnitude). We additionally contrast them
with each other and demonstrate the FFD and WFD-IP are faster than the others by one additional order
of magnitude.
},
}