• Sorted by Date • Classified by Publication Type • Classified by Topic • Grouped by Student (current) • Grouped by Former Students •
Matan Keidar and Gal A. Kaminka. Efficient Frontier Detection for Robot
Exploration. International Journal of Robotics Research, 33(2):215–236, 2014.
The article's web
page on the journal home is at http://ijr.sagepub.com/content/early/2013/10/22/0278364913494911
(unavailable)
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.
@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 <a href="http://ijr.sagepub.com/content/early/2013/10/22/0278364913494911">http://ijr.sagepub.com/content/early/2013/10/22/0278364913494911</a>},
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.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Fri Aug 30, 2024 17:29:51