nach oben

Autonomous Robots

Erschienen in:

01.11.2012

A comparison of path planning strategies for autonomous exploration and mapping of unknown environments

verfasst von: Miguel Juliá, Arturo Gil, Oscar Reinoso

Erschienen in: Autonomous Robots | Ausgabe 4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

To date, a large number of algorithms to solve the problem of autonomous exploration and mapping has been presented. However, few efforts have been made to compare these techniques. In this paper, an extensive study of the most important methods for autonomous exploration and mapping of unknown environments is presented. Furthermore, a representative subset of these techniques has been chosen to be analysed. This subset contains methods that differ in the level of multi-robot coordination and in the grade of integration with the simultaneous localization and mapping (SLAM) algorithm. These exploration techniques were tested in simulation and compared using different criteria as exploration time or map quality. The results of this analysis are shown in this paper. The weaknesses and strengths of each strategy have been stated and the most appropriate algorithm for each application has been determined.

Vorheriger Artikel Localization of a door handle of unknown geometry using a single camera for door-opening with a mobile manipulator

Nächster Artikel Distributed orientation agreement in a group of robots

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Arkin, R., & Diaz, J. (2002). Line-of-sight constrained exploration for reactive multiagent robotic teams. In: Proceedings of the international workshop on advanced motion control (AMC’02), Maribor, Slovenia.

Balaguer, B., Balakirsky, S., Carpin, S., & Visser, A. (2009). Evaluating maps produced by urban search and rescue robots: lessons learned from RoboCup. Autonomous Robots, 27(4), 449–464. CrossRef

Balch, T., & Arkin, R. (1993). Avoiding the past: a simple but effective strategy for reactive navigation. In Proceedings of the IEEE international conference on robotics and automation (ICRA’93).

Batalin, M., & Sukhatme, G. (2007). The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment. IEEE Transactions on Robotics, 23(4), 661–675. CrossRef

Bourgoult, F., Makarenko, A., Williams, S., Grocholsky, B., & Durrant-Whyte, F. (2002). Information based adaptive robotic exploration. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’02), Lausanne, Switzerland.

Burgard, W., Moors, M., Fox, D., Simmons, R., & Thrun, S. (2000). Collaborative multi-robot exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’00) (Vol. 1, pp. 476–481).

Burgard, W., Moors, M., Stachniss, C., & Schneider, F. (2005). Coordinated multi-robot exploration. IEEE Transactions on Robotics, 21(3), 376–386. CrossRef

Castellanos, J., Neira, J., & Tardós, J. D. (2006). Map building and SLAM algorithms. Series in control engineering (pp. 335–371). Boca Raton: CRC, Taylor & Francis Group.

Choset, H., & Burdick, J. (2000). Sensor-based exploration: the hierarchical generalized Voronoi graph. International Journal of Robotics Research, 19(2), 96–125. CrossRef

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. MathSciNetMATHCrossRef

Dissanayake, M., Newman, P., Clark, S., Durrant-Whyte, H., & Csorba, M. (2001). A solution to the simultaneous localization and map building (SLAM) problem. IEEE Transactions on Robotics and Automation, 17(3), 229–241. CrossRef

Feder, H., Leonard, J., & Smith, C. (1999). Adaptive mobile robot navigation and mapping. International Journal of Robotics Research, 18(7), 650–668. CrossRef

Fox, D., Ko, J., Limketkai, B., Schulz, D., & Stewart, B. (2006). Distributed multi-robot exploration and mapping. Proceedings of the IEEE, 94(7), 1325–1339. CrossRef

Franchi, A., Freda, L., Oriolo, G., & Vendittelli, M. (2007a). A decentralized strategy for cooperative robot exploration. In Proceedings of the 1st international conference on robot communication and coordination (p. 7). New York: IEEE Press.

Franchi, A., Freda, L., Oriolo, G., & Vendittelli, M. (2007b). A randomized strategy for cooperative robot exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’07), Roma, Italy.

Franchi, A., Freda, L., Oriolo, G., & Vendittelli, M. (2009). The sensor-based random graph method for cooperative robot exploration. IEEE/ASME Transactions on Mechatronics, 14(2), 163–175. CrossRef

Freda, L., & Oriolo, G. (2005). Frontier-based probabilistic strategies for sensor-based exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’05), Barcelona, Spain.

Freda, L., Loiudice, F., & Oriolo, G. (2006). A randomized method for integrated exploration. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’06), Beijing, China.

Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119–139. MathSciNetMATHCrossRef

Gifford, C. M., Webb, R., Bley, J., Leung, D., Calnon, M., Makarewicz, J., Banz, B., & Agah, A. (2010). A novel low-cost, limited-resource approach to autonomous multi-robot exploration and mapping. Robotics and Autonomous Systems, 58(2), 186–202. CrossRef

González-Baños, H. H., & Latombe, J. C. (2002). Navigation strategies for exploring indoor environments. International Journal of Robotics Research, 21(10), 829–848. CrossRef

Grabowski, R., Khosla, P., & Choset, H. (2003). Autonomous exploration via regions of interest. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’03), Las Vegas, Nevada, USA.

Hartigan, J., & Wong, M. (1979). A k-means clustering algorithm. Journal of the Royal Statistical Society Series C, Applied statistics, 28, 100–108. MATH

Hougen, D. F., Erickson, M. D., Rybski, P. E., Stoeter, S. A., Gini, M., & Papanikolopoulos, N. (2000). Autonomous mobile robots and distributed exploratory missions. In Proceedings of the 5th international symposium on distributed autonomous robotic systems (pp. 221–230). CrossRef

Juliá, M., Gil, A., Payá, L., & Reinoso, O. (2008). Local minima detection in potential field based cooperative multi-robot exploration. International Journal of Factory Automation, Robotics and Soft Computing, 3.

Juliá, M., Reinoso, O., Gil, A., Ballesta, M., & Payá, L. (2010). A hybrid solution to the multi-robot integrated exploration problem. Engineering Applications of Artificial Intelligence, 23(4), 473–486. CrossRef

Juliá, M., Reinoso, O., Gil, A., Ballesta, M., & Payá, L. (2011). Behaviour based multi-robot integrated exploration. International Journal of Innovative Computing, Information and Control, 7(9).

Kleiner, A., Prediger, J., & Nebel, B. (2006). RFID technology-based exploration and SLAM for search and rescue. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’06), Beijing, China.

Kollar, T., & Roy, N. (2008). Trajectory optimization using reinforcement learning for map exploration. International Journal of Robotics Research, 27(2), 175–196. CrossRef

Kuhn, H. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1), 83–97. MathSciNetCrossRef

Kuipers, B., & Byun, Y. (1991). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Robotics and Autonomous Systems, 8, 47–63. CrossRef

Lau, H. (2003). Behavioural approach for multi-robot exploration. In Proceedings of the Australasian conference on robotics and automation (ACRA’03), Brisbane, Australia.

Lee, D., & Recce, M. (1997). Quantitative evaluation of the exploration strategies of a mobile robot. International Journal of Robotics Research, 16(4), 413–447. CrossRef

Lidoris, G., Rohrmueller, F., Wollherr, D., & Buss, M. (2009). The autonomous city explorer (ACE) project—mobile robot navigation in highly populated urban environments. In Proceedings of the IEEE international conference on robotics and automation (ICRA’09), Kobe, Japan.

Makarenko, A., Williams, S., Bourgoult, F., & Durrant-Whyte, F. (2002). An experiment in integrated exploration. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’02), Lausanne, Switzerland.

Martinez-Cantin, R., de Freitas, N., Brochu, E., Castellanos, J., & Doucet, A. (2009). A Bayesian exploration-exploitation approach for optimal online sensing and planning with a visually guided mobile robot. Autonomous Robots, 27(2), 93–103. CrossRef

Montemerlo, M., & Thrun, S. (2003). Simultaneous localization and mapping with unknown data association using FastSLAM. In Proceedings of the IEEE international conference on robotics and automation (ICRA’03), Taipei, Taiwan.

Moravec, H., & Elfes, A. (1985). High resolution maps from wide angle sonar. In Proceedings of the IEEE international conference on robotics and automation (ICRA’85).

Murphy, L., & Newman, P. (2008). Using incomplete online metric maps for topological exploration with the gap navigation tree. In Proceedings of the IEEE international conference on robotics and automation (ICRA’08), Pasadena, CA, USA.

Murray, D., & Little, J. (2000). Using real-time stereo vision for mobile robot navigation. Autonomous Robots, 8(2), 161–171. CrossRef

Nevatia, Y., Stoyanov, T., Rathnam, R., Pfingsthorn, M., Markov, S., Ambrus, R., & Birk, A. (2008). Augmented autonomy: improving human-robot team performance in urban search and rescue. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’08) (pp. 2103–2108). CrossRef

Newman, P., Bosse, M., & Leonard, J. (2003). Autonomous feature-based exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’03), Taipei, Taiwan.

Pei, Y., Mutka, M., & Xi, N. (2010). Coordinated multi-robot real-time exploration with connectivity and bandwidth awareness. In Proceedings of the IEEE international conference on robotics and automation (ICRA’10) (pp. 5460–5465). New York: IEEE.

Porta, J. M., Vlassis, N., Spaan, M. T., & Poupart, P. (2006). Point-based value iteration for continuous POMDPs. Journal of Machine Learning Research, 7, 2329–2367. MathSciNetMATH

Prestes, E., Engel, P., Trevisan, M., & Idiart, M. (2002). Exploration method using harmonic functions. Robotics and Autonomous Systems, 40(1), 25–42. CrossRef

Rekleitis, I., Sim, R., Dudek, G., & Milios, E. (2001). Collaborative exploration for the construction of visual maps. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’01), Wailea, Hawaii.

Rooker, M. N., & Birk, A. (2007). Multi-robot exploration under the constraints of wireless networking. Control Engineering Practice, 15(4), 435–445. CrossRef

Santosh, D., Achar, S., & Jawahar, C. (2008). Autonomous image-based exploration for mobile robot navigation. In Proceedings of the IEEE international conference on robotics and automation (ICRA’08), Pasadena, CA, USA.

Schmidt, D., Luksch, T., Wettach, J., & Berns, K. (2006). Autonomous behavior-based exploration of office environments. In Proceedings of the international conference on informatics in control, automation and robotics (ICINCO’06), Setúbal, Portugal.

Schultz, A., Adams, W., & Yamauchi, B. (1999). Integrating exploration, localization, navigation and planning with a common representation. Autonomous Robots, 6, 293–308. CrossRef

Sheng, W., Yang, Q., Tan, J., & Xi, N. (2006). Distributed multi-robot coordination in area exploration. Robotics and Autonomous Systems, 54, 945–955. CrossRef

Sim, R., & Little, J. J. (2009). Autonomous vision-based robotic exploration and mapping using hybrid maps and particle filters. Image and Vision Computing, 27(1–2), 167–177. CrossRef

Sim, R., & Roy, N. (2005). Global A-optimal robot exploration in SLAM. In Proceedings of the IEEE international conference on robotics and automation (ICRA’05) (pp. 661–666). CrossRef

Sim, R., Dudek, G., & Roy, N. (2004). On line control policy optimization for minimizing map uncertainty during exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’04), New Orleans, LA, USA.

Simmons, R., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., & Younes, H. (2000). Coordination for multi-robot exploration and mapping. In Proceedings of the AAAI national conference on artificial intelligence, Austin, TX, USA.

Solanas, A., & Garcia, M. (2004). Coordinated multi-robot exploration through unsupervised clustering of unknown space. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’04), Sendai, Japan (pp. 717–721).

Stachniss, C. (2009). Robotic mapping and exploration. Springer tracts in advanced robotics. Berlin: Springer. CrossRef

Stachniss, C., Grisetti, G., & Burgard, W. (2005a). Information gain-based exploration using Rao-Blackwellized particle filters. In Proceedings of robotics: science and systems (RSS’05), Cambridge, MA, USA.

Stachniss, C., Haehnel, D., Burgard, W., & Grisetti, G. (2005b). On actively closing loops in grid-based FastSLAM. RSJ Advanced Robotics, 19(10), 1059–1080. CrossRef

Stachniss, C., Mozos, O. M., & Burgard, W. (2006). Speeding-up multi-robot exploration by considering semantic place information. In Proceedings of the IEEE international conference on robotics and automation (ICRA’06), Orlando, FL, USA.

Surmann, H., Nuechter, A., & Hertzberg, J. (2003). An autonomous mobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments. Robotics and Autonomous Systems, 45(3–4), 181–198. CrossRef

Thornburg, K., & Thomas, G. (2009). Robotic exploration utility for urban search and rescue tasks. Journal of Computers, 4(10), 975–980. CrossRef

Thrun, S., Thayer, S., Whittaker, W., Baker, C., Burgard, W., Ferguson, D., Hahnel, D., Montemerlo, D., Morris, A., Omohundro, Z., Reverte, C., & Whittaker, W. (2004). Autonomous exploration and mapping of abandoned mines. IEEE Robotics and Automation Magazine, 11(4), 79–91. CrossRef

Tovar, B., Munoz-Gómez, L., Murrieta-Cid, R., Alencastre-Miranda, M., Monroy, R., & Hutchinson, S. (2006). Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems, 54(4), 314–331. CrossRef

Vazquez, J., & Malcolm, C. (2004). Distributed multirobot exploration maintaining a mobile network. In Proceedings of the 2nd international IEEE conference on intelligent systems (pp. 113–118).

Wullschleger, F. H., Arras, KO, & Vestli, S. J. (1999). A flexible exploration framework for map building. In Third European workshop on advanced mobile robots (Eurobot’99).

Wurm, K. M., Stachniss, C., & Burgard, W. (2008). Coordinated multi-robot exploration using a segmentation of the environment. In Proceedings of the IEEE-RSJ international conference on intelligent robots and systems (IROS’08), Nice, France.

Yamauchi, B. (1997). A frontier based approach for autonomous exploration. In Proceedings of the IEEE international symposium on computational intelligence in robotics and automation (CIRA’97), Monterey, CA, USA.

Yamauchi, B. (1998). Frontier-based exploration using multiple robots. In Proceedings of the international conference on autonomous agents, Minneapolis/Saint Paul, MN, USA.

Zelinsky, A. (1992). A mobile robot exploration algorithm. IEEE Transactions on Robotics and Automation, 8(6), 707–717. CrossRef

Zlot, R., Stentz, A., Dias, M. B., & Thayer, S. (2002). Multi-robot exploration controlled by a market economy. In Proceedings of the IEEE international conference on robotics and automation (ICRA’02), Washington, DC, USA.

Titel: A comparison of path planning strategies for autonomous exploration and mapping of unknown environments
verfasst von: Miguel Juliá
Arturo Gil
Oscar Reinoso
Publikationsdatum: 01.11.2012
Verlag: Springer US
Erschienen in: Autonomous Robots / Ausgabe 4/2012
Print ISSN: 0929-5593
Elektronische ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-012-9298-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2012

Distributed orientation agreement in a group of robots

Localization of a door handle of unknown geometry using a single camera for door-opening with a mobile manipulator

Force feedback exploiting tactile and proximal force/torque sensing

Robot task plan representation by Petri nets: modelling, identification, analysis and execution

Erratum to: Autonomous construction using scarce resources in unknown environments

A momentum-based balance controller for humanoid robots on non-level and non-stationary ground