Efficient frontier detection for robot exploration
The DOI matches its Crossref record; 41 of the 45 references it cites were found in a registry or an index.
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: 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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Monte Carlo sampling methods using Markov chains and their applications.
Hastings, W. K. (1970) · Biometrika · doi:10.1093/biomet/57.1.97 · Cited by 15,195 · cited 1×
“A particle filter is the online version of Markov chain Monte Carlo (MCMC) methods (Hastings, 1970; Geyer, 1992; Neal, 1993).”
MethodSimultaneous localization and mapping (SLAM): part II
Bailey, T., & Durrant-Whyte, H. (2006) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2006.1678144 · Cited by 2,554
Improved Techniques for Grid Mapping With Rao-Blackwellized Particle Filters
Grisetti, G., Stachniss, C., & Burgard, W. (2007) · IEEE Transactions on Robotics · doi:10.1109/tro.2006.889486 · Cited by 2,439 · cited 5×
“The system is based on GMapping, an open-source SLAM implementation (Grisetti et al., 2005, 2007).”
BackgroundMethodInfluentialAlgorithm for computer control of a digital plotter
Bresenham, J. E. (1965) · IBM Systems Journal · doi:10.1147/sj.41.0025 · Cited by 2,172
Practical markov chain monte carlo
Geyer, C. J. (1992) · Statistical Science · doi:10.1214/ss/1177011137 · Cited by 2,045 · cited 1×
“A particle filter is the online version of Markov chain Monte Carlo (MCMC) methods (Hastings, 1970; Geyer, 1992; Neal, 1993).”
MethodA frontier-based approach for autonomous exploration
Yamauchi, B. (2002) · Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA'97. 'Towards New Computational Principles for Robotics and Automation' · doi:10.1109/cira.1997.613851 · Cited by 1,695 · cited 3×
“Yamauchi (1997, 1998) developed the first frontier-based exploration methods.”
BackgroundO’Regan, G. (2023) · Texts in Computer Science · doi:10.1007/978-3-031-26212-8_4 · Cited by 1,614
Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)
Thrun, S., Burgard, W., & Fox, D. (2005) · The MIT Press eBooks · Cited by 1,422
Mobile robot localization by tracking geometric beacons
Leonard, J. J., & Durrant-Whyte, H. F. (1991) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.88147 · Cited by 1,245 · cited 1×
“The term SLAM was originally developed by Leonard and Durrant-Whyte (1991) (see also Durrant-Whyte and Bailey, 2006).”
BackgroundCoordinated multi-robot exploration
Burgard, W., Moors, M., Stachniss, C., & Schneider, F. E. (2005) · IEEE Transactions on Robotics · doi:10.1109/tro.2004.839232 · Cited by 1,177 · cited 3×
“Burgard et al. (2000, 2005) focus their investigation on a probabilistic approach for coordinating a team of robots.”
BackgroundProbabilistic Inference Using Markov Chain Monte Carlo Methods
Neal, R. M. (2011) · Cited by 1,039
Collaborative multi-robot exploration
Burgard, W., Moors, M., Fox, D., Simmons, R., & Thrun, S. (2002) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844100 · Cited by 762 · cited 3×
“Burgard et al. (2000, 2005) focus their investigation on a probabilistic approach for coordinating a team of robots.”
BackgroundGrisetti, G., Stachniss, C., & Burgard, W. (2005) · Proceedings of the 2005 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2005.1570477 · Cited by 734 · cited 2×
“The system is based on GMapping, an open-source SLAM implementation [13, 14].”
MethodFrontier-based exploration using multiple robots
Yamauchi, B. (1998) · Proceedings of the second international conference on Autonomous agents - AGENTS '98 · doi:10.1145/280765.280773 · Cited by 717 · cited 4×
“Yamauchi (1997, 1998) developed the first frontier-based exploration methods.”
BackgroundInfluentialA robot exploration and mapping strategy based on a semantic hierarchy of spatial representations
Kuipers, B., & Byun, Y.-T. (1991) · Robotics and Autonomous Systems · doi:10.1016/0921-8890(91)90014-c · Cited by 707 · cited 1×
“Kuipers and Byun (1991) presented a method for exploration and mapping for large-scale spatial environments.”
MethodCoordination for Multi-Robot Exploration and Mapping
Simmons, R. G., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., & Younes, H. L. S. (2000) · Cited by 502
Multi-robot exploration controlled by a market economy
Zlot, R., Stentz, A., Dias, M. B., & Thayer, S. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1013690 · Cited by 489 · cited 1×
“Zlot et al. (2002) coordinates a team of exploring robots by applying a market-based approach.”
BackgroundThe International Joint Conference on Artificial Intelligence (IJCAI)
(1972) · Artificial Intelligence · doi:10.1016/0004-3702(72)90052-5 · Cited by 480
Distributed Multirobot Exploration and Mapping
Fox, D., Ko, J., Konolige, K., Limketkai, B., Schulz, D., & Stewart, B. (2006) · Proceedings of the IEEE · doi:10.1109/jproc.2006.876927 · Cited by 344 · cited 1×
“Fox et al. (2010) presented an exploration and mapping distributed system for multi-robot exploring teams.”
BackgroundA robot exploration and mapping strategy based on a semantic hierarchy of spatial representations
Kuipers, B. J., & Byun, Y.-T. (1993) · Cited by 327
Kitano, H., Tadokoro, S., Noda, I., Matsubara, H., Takahashi, T., Shinjou, A., & Shimada, S. (2003) · IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No.99CH37028) · doi:10.1109/icsmc.1999.816643 · Cited by 306 · cited 2×
“Applications of efficient exploration include search and rescue (Kitano et al., 1999), planetary exploration (Apostolopoulos et al.”
BackgroundJuliá, M., Gil, A., & Reinoso, O. (2012) · Autonomous Robots · doi:10.1007/s10514-012-9298-8 · Cited by 256 · cited 2×
“Ko et al. (2003) presented a decision-theoretic approach to the mapping and exploration problem.”
MethodCoordinated multi-robot exploration using a segmentation of the environment
Wurm, K. M., Stachniss, C., & Burgard, W. (2008) · 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems · doi:10.1109/iros.2008.4650734 · Cited by 251 · cited 4×
“Burgard et al. (2000, 2005) focus their investigation on a probabilistic approach for coordinating a team of robots.”
BackgroundMethodInfluentialRobot exploration with combinatorial auctions
Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., & Kleywegt, A. (2004) · Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453) · doi:10.1109/iros.2003.1248932 · Cited by 183 · cited 5×
“Berhault et al. (2003) proposed a combinatorial auction mechanism where the robots bid on a bunch of targets to navigate. The robots are able to use different bidding strategies. Each robot has to visit all of the targets that are included in his winning bid. After combining each robot’s sensor readings, the auctionee…”
BackgroundMethodInfluentialMulti-Robot Exploration of an Unknown Environment, Efficiently Reducing the Odometry Error
Rekleitis, I. M., Dudek, G., & Milios, E. (1997) · Cited by 176
A practical, decision-theoretic approach to multi-robot mapping and exploration
Ko, J., Stewart, B., Fox, D., Konolige, K., & Limketkai, B. (2004) · Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453) · doi:10.1109/iros.2003.1249654 · Cited by 175 · cited 1×
“Ko et al. (2003) presented a decision-theoretic approach to the mapping and exploration problem.”
Multi-robot collaboration for robust exploration
Rekleitis, I., Dudek, G., & Milios, E. (2001) · Annals of Mathematics and Artificial Intelligence · doi:10.1023/a:1016636024246 · Cited by 161 · cited 2×
“[28, 29] presented a strategy of localization and exploration designed for small-scale and large-scale environments.”
BackgroundA miniature robotic system for reconnaissance and surveillance
Hougen, D. F., Benjaafar, S., Bonney, J., Budenske, J. R., Dvorak, M., Gini, M. L., French, H. B., Krantz, D. G., Li, P. Y., Malver, F., et al. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2000.844104 · Cited by 147 · cited 2×
“Applications of efficient exploration include search and rescue (Kitano et al., 1999), planetary exploration (Apostolopoulos et al., 2001) and military uses (Hougen et al., 2000).”
BackgroundCentibots: Very Large Scale Distributed Robotic Teams
Konolige, K., Fox, D., Ortiz, C., Agno, A., Eriksen, M., Limketkai, B., Ko, J., Morisset, B., Schulz, D., Stewart, B., et al. (2006) · Springer tracts in advanced robotics · doi:10.1007/11552246_13 · Cited by 98
Multi‐objective exploration and search for autonomous rescue robots
Calisi, D., Farinelli, A., Iocchi, L., & Nardi, D. (2007) · Journal of Field Robotics · doi:10.1002/rob.20216 · Cited by 75 · cited 1×
“It builds on ideas suggested in earlier work (Calisi et al., 2007) which were not evaluated as an alternative to the edge-detection state of the art (SOTA).”
BackgroundSpeeding-up multi-robot exploration by considering semantic place information
Stachniss, C., Mozos, Ó. M., & Burgard, W. (2006) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2006.1641950 · Cited by 61 · cited 1×
“Stachniss et al. (2006) investigated the assignment of targets to the robot team members.”
BackgroundEfficient exploration without localization
Batalin, M. A., & Sukhatme, G. S. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2003.1242003 · Cited by 60 · cited 3×
“Batalin and Sukhatme (2003) presented an exploration method which does not utilize a map for navigating in the environment. Their algorithm uses markers which are dropped off by the robot and aid the exploration. Puig Valls (2010) presented an algorithm for coordinating the team members during the exploration task. Th…”
BackgroundMethodInfluentialRobotic Antarctic meteorite search: outcomes
Apostolopoulos, D. S., Pedersen, L., Shamah, B., Shillcutt, K. J., Wagner, M. D., & Whittaker, W. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2001.933270 · Cited by 50 · cited 2×
“, 1999), planetary exploration (Apostolopoulos et al., 2001) and military uses (Hougen et al.”
BackgroundIncluding communication success in the estimation of information gain for multi-robot exploration
Visser, A., & Slamet, B. A. (2008) · International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) · doi:10.1109/wiopt.2008.4586160 · Cited by 39
Behavioural Approach for Multi-Robot Exploration
Lau, H. T. (2003) · UTS ePRESS (University of Technology Sydney) · Cited by 31
On fast exploration in 2D and 3D terrains with multiple robots
Sawhney, R., Krishna, K. M., & Srinathan, K. (2009) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/fjia9154 · Cited by 18
Flocking-Based Multi-Robot Exploration
Bouraqadi, N., & Doniec, A. (2009) · HAL · Cited by 17
Balanced multi-robot exploration through a global optimization strategy
Ling, W., Puig, D., & García, M. Á. (2010) · Journal of Physical Agents (JoPha) · doi:10.14198/jopha.2010.4.1.06 · Cited by 14 · cited 2×
“Puig Valls (2010) presented an algorithm for coordinating the team members during the exploration task.”
Method
Research works printed but not linked: 10
- Bouraqadi N, 2009, National conference on control architectures of robots
- Durrant-Whyte H, 2006, Robotics and Automation Magazine, 13, 80
- Fox D, 2010, Proceedings of the IEEE, 94, 1325
- Konolige K, 2003, Proceedings from the 2003 International workshop on multi-robot systems: from swarms to intelligent autonoma, 2, 193
- Lau H, 2003, Australasian conference on robotics and automation (ACRA)
- Puig Valls D, 2010, Journal of Physical Agents, 4, 35
- Sawhney R, 2009, Proceedings of the eighth International joint conference on autonomous agents and multi-agent systems (AAMAS-09), 73
- Simmons R, 2000, Proceedings of the seventeenth National conference on artificial intelligence (AAAI-00), 852
- Stachniss C (2006) Exploration and Mapping with Mobile Robots. Ph.D. thesis, University of Freiburg, Department of Computer Science.
- Stoeter S, 2000, Proceedings of the International conference on intelligent autonomous systems, 767
Cited by
Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., & Leonard, J. J. (2016) · IEEE Transactions on Robotics · doi:10.1109/tro.2016.2624754 · Cited by 3,596
“• SLAM helps Semantics: The first robotic researchers working on semantic mapping started by the straightforward approach of segmenting the metric map built by a classical SLAM system into semantic concepts.”
Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I. D., & Leonard, J. J. (2016) · Zurich Open Repository and Archive (University of Zurich) · doi:10.5167/uzh-138892 · Cited by 3,048
A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers
Placed, J. A., Strader, J., Carrillo, H., Atanasov, N., Indelman, V., Carlone, L., & Castellanos, J. A. (2023) · IEEE Transactions on Robotics · doi:10.1109/tro.2023.3248510 · Cited by 332
“Keidar and Kaminka [109] proposed the wavefront frontier detector (WFD) and fast frontier detector (FFD).”
BackgroundInfluentialGoal-Driven Autonomous Exploration Through Deep Reinforcement Learning
Cimurs, R., Suh, I. H., & Lee, J. H. (2022) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2021.3133591 · Cited by 184
Active Mapping and Robot Exploration: A Survey
Lluvia, I., Lazkano, E., & Ansuategi, A. (2021) · Sensors · doi:10.3390/s21072445 · Cited by 201
“Frontiers can be searched by applying computer vision techniques such as edge detection or region extraction [66].”
Background
Metadata
- Authors
- Keidar, M., & Kaminka, G. A.
- Affiliations
- Bar-Ilan University (IL)
- ORCID
- Kaminka, Gal A.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2013-10-22
- Volume
- 33
- Issue
- 2
- Pages
- 215-236
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2169781427
- Cited by
- 151
- References
- 45
- Citations by year
- 2026: 13 · 2025: 24 · 2024: 18 · 2023: 18 · 2022: 14 · 2021: 16 · 2020: 10 · 2019: 9 · 2018: 11 · 2017: 2 · 2016: 6 · 2015: 4 · 2014: 6
- FWCI
- 8.57
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- journals.sagepub.com/page/policies/text-and-data-mining-license (tdm)
- Locations
- The International Journal of Robotics Research (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Robotics and Sensor-Based Localization
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
- Keywords
- frontier detection, robot exploration, frontier exploration, graph search, computational complexity, map partitioning, mobile robot navigation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.