Gal A. Kaminka's Publications

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

Efficient Frontier Detection for Robot Exploration

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

Download

(unavailable)

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.

BibTeX

@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 Sun Jul 23, 2017 22:08:49