{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T07:44:06Z","timestamp":1780472646764,"version":"3.54.1"},"reference-count":43,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2013,10,22]],"date-time":"2013-10-22T00:00:00Z","timestamp":1382400000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>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: Wavefront Frontier Detector (WFD), a graph-search-based algorithm which examines only known areas, and Fast Frontier Detector (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.<\/jats:p>","DOI":"10.1177\/0278364913494911","type":"journal-article","created":{"date-parts":[[2013,10,23]],"date-time":"2013-10-23T03:09:52Z","timestamp":1382497792000},"page":"215-236","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":123,"title":["Efficient frontier detection for robot exploration"],"prefix":"10.1177","volume":"33","author":[{"given":"Matan","family":"Keidar","sequence":"first","affiliation":[{"name":"Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gal A.","family":"Kaminka","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2013,10,22]]},"reference":[{"key":"bibr1-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.933270"},{"key":"bibr2-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2003.1242003"},{"key":"bibr3-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1248932"},{"key":"bibr4-0278364913494911","volume-title":"National conference on control architectures of robots","author":"Bouraqadi N","year":"2009"},{"key":"bibr5-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1147\/sj.41.0025"},{"key":"bibr6-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844100"},{"key":"bibr7-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2004.839232"},{"key":"bibr8-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20216"},{"key":"bibr9-0278364913494911","volume-title":"Introduction to Algorithms","author":"Cormen TH","year":"2001"},{"issue":"99","key":"bibr10-0278364913494911","first-page":"80","volume":"13","author":"Durrant-Whyte H","year":"2006","journal-title":"Robotics and Automation Magazine"},{"issue":"1","key":"bibr11-0278364913494911","first-page":"1325","volume":"94","author":"Fox D","year":"2010","journal-title":"Proceedings of the IEEE"},{"key":"bibr12-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177011137"},{"key":"bibr13-0278364913494911","first-page":"2443","volume-title":"Proceedings of IEEE International conference on robotics and automation (ICRA-05)","author":"Grisetti G","year":"2005"},{"key":"bibr14-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2006.889486"},{"key":"bibr15-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"bibr16-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844104"},{"key":"bibr17-0278364913494911","unstructured":"Howard A, Roy N (2003) The robotics data set repository (RADISH). http:\/\/radish.sourceforge.net\/ ."},{"key":"bibr18-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9298-8"},{"key":"bibr19-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.1999.816643"},{"key":"bibr20-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1249654"},{"key":"bibr21-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1007\/11552246_13"},{"key":"bibr22-0278364913494911","first-page":"193","volume-title":"Proceedings from the 2003 International workshop on multi-robot systems: from swarms to intelligent autonoma","volume":"2","author":"Konolige K","year":"2003"},{"key":"bibr23-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1016\/0921-8890(91)90014-C"},{"key":"bibr24-0278364913494911","volume-title":"Australasian conference on robotics and automation (ACRA)","author":"Lau H","year":"2003"},{"key":"bibr25-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/70.88147"},{"key":"bibr26-0278364913494911","volume-title":"Probabilistic Inference Using Markov Chain Monte Carlo Methods","author":"Neal RM","year":"1993"},{"issue":"1","key":"bibr27-0278364913494911","first-page":"35","volume":"4","author":"Puig Valls D","year":"2010","journal-title":"Journal of Physical Agents"},{"key":"bibr28-0278364913494911","first-page":"1340","volume-title":"International joint conference on artificial intelligence (IJCAI)","volume":"15","author":"Rekleitis I","year":"1997"},{"key":"bibr29-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016636024246"},{"key":"bibr30-0278364913494911","first-page":"73","volume-title":"Proceedings of the eighth International joint conference on autonomous agents and multi-agent systems (AAMAS-09)","author":"Sawhney R","year":"2009"},{"key":"bibr31-0278364913494911","first-page":"852","volume-title":"Proceedings of the seventeenth National conference on artificial intelligence (AAAI-00)","author":"Simmons R","year":"2000"},{"key":"bibr32-0278364913494911","unstructured":"Stachniss C (2006) Exploration and Mapping with Mobile Robots. Ph.D. thesis, University of Freiburg, Department of Computer Science."},{"key":"bibr33-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1641950"},{"key":"bibr34-0278364913494911","first-page":"767","volume-title":"Proceedings of the International conference on intelligent autonomous systems","author":"Stoeter S","year":"2000"},{"key":"bibr35-0278364913494911","volume-title":"Probabilistic Robotics (Intelligent Robotics and Autonomous Agents Series)","author":"Thrun S","year":"2005"},{"key":"bibr36-0278364913494911","unstructured":"Visser A (2011) Personal communication by email, 4 January."},{"key":"bibr37-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/wiopt.2008.4586160"},{"key":"bibr38-0278364913494911","unstructured":"Welch G, Bishop G (1995) An Introduction to the Kalman Filter. Technical Report, University of North Carolina at Chapel Hill, Chapel Hill, NC. http:\/\/www.cs.unc.edu\/~welch\/media\/pdf\/kalman_intro.pdf."},{"key":"bibr39-0278364913494911","unstructured":"Wurm K (2011) Personal communication by email, 20 January."},{"key":"bibr40-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2008.4650734"},{"key":"bibr41-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/CIRA.1997.613851"},{"key":"bibr42-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1145\/280765.280773"},{"key":"bibr43-0278364913494911","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2002.1013690"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913494911","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364913494911","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913494911","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:18:22Z","timestamp":1777457902000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364913494911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,22]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1177\/0278364913494911"],"URL":"https:\/\/doi.org\/10.1177\/0278364913494911","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,22]]}}}