Abstract
The article proposes a solution to map-based self-localization for an autonomous robot operating in cluttered and crowded environments. To detect features for localization, 2D laser range-finders traditionally scan a plane parallel to the floor. This work hypothesizes the existence of a “low frequency cross-section” of the 3D Workspace where cluttered and dynamic environments become “more regular” and “less dynamic”. The contribution of the article is twofold. First, an “unevenness index” U is introduced to quantitatively measure the complexity of the environment as it would be perceived if the laser range-finder were located at different heights from the floor. The article shows that, by choosing the laser scanning plane to statistically minimize U (in most cases, above the heads of people), it is possible to deal more efficiently with non-linearities in the measurement model, moving objects and occluded features. Second, it is demonstrated that, when adopting an extended Kalman filter for position tracking (a very common and widely used technique in real-world scenarios), the a posteriori covariance of the estimated robot pose converges faster, on average, when U is lower, which leads to better localization performance. Experimental results show hours of continuous robot operation in real-world, cluttered and crowded environments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adams, M., Probert, P.: The interpretation of phase and intensity data from AMCW light detection sensor for reliable ranging. Int. J. Rob. Res. 15(5), 441–458 (1996)
Antonelli, G., Chiaverini, S., Fusco, G.: A calibration method for odometry of mobile robots based on the least-squares technique: theory and experimental validation. IEEE Trans. Robot. 21(5), 994–1004 (2005)
Arleo, A., Millan, J., Floreano, D.: Efficient learning of variable-resolution cognitive maps for autonomous indoor navigation. IEEE Trans. Robot. Autom. 15(6), 990–1000 (1999)
Armesto, L., Ippoliti, G., Longhi, S., Tornero, J.: FastSLAM 2.0: least-squares approach. In: Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2006). Beijing, China (2006)
Baltzakis, H., Trahanias, P.: A hybrid framework for mobile robot localization: formulation using switching state-space models. Auton. Robots 15, 169–191 (2003)
Bennewitz, M., Burgard, W., Thrun, S.: Using EM to learn motion behaviors of persons with mobile robots. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2002). Lausanne, Switzerland (2002)
Bennewitz, M., Stachniss, C., Behnke, S., Burgard, W.: Utilizing reflection properties of surfaces to improve mobile robot localization. In: Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA 2009). Kobe, Japan (2009)
Blanco, J., Gonzalez, J., Fernandez-Madrigal, J.: Consistent observation grouping for generating metric-topological maps that improves robot localization. In: Proceedings of the 2006 International Conference on Robotics and Automation (ICRA 2006). Orlando, FL (2006)
Borenstein, J.: Experimental results from internal odometry error correction with the OmniMate mobile robot. IEEE Trans. Robot. Autom. 14(6), 963–969 (1998)
Bosse, M., Roberts, J.: Histogram matching and global initialization for laser-only slam in large unstructured environments. In: Proceedings of the 2007 IEEE International Conference on Robotics and Automation (ICRA 2007). Rome, Italy (2007)
Bosse, M., Zlot, R.: Map matching and data association for large-scale two-dimensional laser scan-based SLAM. Int. J. Robot. Res. 27(6), 667–691 (2009)
Brscic, D., Hashimoto, H.: Model based robot localization using onboard and distributed laser range finders. In: Proceedings of the 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2008). Nice, France (2008)
Burgard, W., Trahanias, P., Hanel, D., Moors, M., Shulz, D., Baltzakis, H., Argyros, A.: Tele-presence in populated exhibitions through Web-operated mobile robots. Auton. Robots 15, 299–316 (2003)
Choset, H., Nagatani, K.: Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Trans. Robot. Autom. 17(2), 125–137 (2001)
Cox, I.: BLANCHE—an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Trans. Robot. Autom. 7(2), 193–204 (1991)
Dissanayake, G., Williams, S.B., Durrant-Whyte, H., Bailey, T.: Map management for efficient simultaneous localization and mapping (SLAM). Auton. Robots 12, 267–286 (2002)
Doh, N., Lee, K., Chung, W., Cho, H.: Simultaneous localisation and mapping algorithm for topological maps with dynamics. IET Control Theory Appl. 3(9), 1249–1260 (2009)
Dong, J., Wijesoma, S., Shacklock, A.: Extended Rao-Blackwellised genetic algorithmic filter SLAM in dynamic environments with raw sensor measurements. In: Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007). San Diego, CA (2007)
Duda, R., Hart, P.: Pattern Classification and Scene Analysis. Wiley and Sons, New York (1973)
Estrada, C., Neira, J., Tardós, J.: Hierarchical SLAM: real-time accurate mapping of large environments. IEEE Trans. Robot. 21(4), 588–596 (2005)
Folkensson, J., Christensen, H.: Robust SLAM. In: Proceedings of the Fifth IFAC/EURON Symposium on Intelligent Autonomous Vehicles (IAV 2004). Lisbon, Portugal (2004)
Fox, D.: Markov localization: a probabilistic framework for mobile robot localization and navigation. Ph.D. thesis, Institute of Computer Science III, University of Bonn (1998)
Fox, D., Burgard, W., Dellaert, F., Thrun, S.: Monte Carlo localization: efficient position estimation for mobile robots. In: Proceedings of the 16th National Conference on Artificial Intelligence (NCAI 1999). Bhankrota, India (1999)
Fox, D., Burgard, W., Thrun, S.: Markov localization for mobile robots in dynamic environments. J. Artif. Intell. Res. 11, 391–427 (1999)
Fox, D., Thrun, S., Burgard, W., Dellaert, F.: Particle Filters for mobile robot localization. In: Doucet, A., de Freitas, N., Gordon, N. (eds.) Sequential Monte Carlo Methods in Practice, Statistics for Engineering and Information Science. Springer, New York (2001)
Frese, U.: A discussion of simultaneous localization and mapping. Auton. Robots 20, 25–42 (2006)
Georgiev, A., Allen, P.: Localization methods for a mobile robot in urban environments. IEEE Trans. Robot. 20(5), 851–864 (2004)
Glas, D., Kanda, T., Ishiguro, H., Hagita, N.: Simultaneous people tracking and localization for social robots using external laser range finders. In: Proccedings of the 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009). Nice, France (2009)
Guivant, J., Nebot, E.: Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE Trans. Robot. Autom. 17(3), 242–257 (2001)
Guivant, J., Nebot, E.: Solving computational and memory requirements of feature-based simultaneous localization and mapping algorithms. IEEE Trans. Robot. Autom. 19(4), 749–755 (2003)
Haehnel, D., Fox, D., Burgard, W., Thrun, S.: A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements. In: Proceedings of 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003). Las Vegas, USA (2003)
Haehnel, D., Triebel, R., Burgard, W., Thrun, S.: Map building with mobile robots in dynamic environments. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA 2003). Taipei, Taiwan (2003)
Iagnemma, K., Kang, S., Shibly, H., Dubowsky, S.: Online terrain parameter estimation for wheeled mobile robots with application to planetary rovers. IEEE Trans. Robot. 20(5), 921–927 (2004)
Jensfelt, P., Christensen, H.: Pose tracking using laser scanning and minimalistic environmental models. IEEE Trans. Robot. Autom. 17(2), 138–147 (2001)
Julier, S., Uhlman, J.: A counter example to the theory of simultaneous localisation and map building. In: Proceedings of the 2001 IEEE International Conference on Robotics and Automation (ICRA 2001). Seoul, Korea (2001)
Kaess, M., Dellaert, F.: A Markov Chain Monte Carlo approach to closing the loop in SLAM. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA 2005). Barcelona, Spain (2005)
Konolige, K.: SLAM via variable reduction from constraint maps. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA 2005). Barcelona, Spain (2005)
Konolige, K., Grisetti, G., Kummerle, R., Burgard, W., Limketkai, B., Vincent, R.: Efficient sparse pose adjustment for 2d mapping. In: Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010). Taipei, Taiwan (2010)
Lidoris, G., Wollherr, D., Buss, M.: Bayesian state estimation and behavior selection for autonomous robotic exploration in dynamic environments. In: Proceedings of the 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2008). Nice, France (2008)
Lisien, B., Morales, D., Silver, D., Kantor, G., Rekleitis, I., Choset, H.: The hierarchical atlas. IEEE Trans. Robot. 21(3), 473–481 (2005)
Liu, Y., Emery, R., Chakrabati, D., Burgard, W., Thrun, S.: Using EM to learn 3D models of indoor environments with mobile robots. In: Proceedings of the 2001 International Conference on Machine Learning (ICML 2001). Berkshires, MA (2001)
Lopez, M., Bergasa, L., Barea, R., Escudero, M.: A navigation system for assistant robots using visually augmented POMDPs. Auton. Robots 19, 67–87 (2005)
Martinelli, A.: The odometry error of a mobile robot with a synchronous drive system. IEEE Trans. Robot. Autom. 18(3), 399–405 (2002)
Maybank, S.: Filter based estimates of depth. In: Proceedings of the 1990 British Machine Vision Conference (BMVC 1990), pp. 349–354. London, UK (1990)
Miller, I., Campbell, M.: Rao-Blackwellized particle filtering for mapping dynamic environments. In: Proceedings of the 2007 IEEE International Conference on Robotics and Automation (ICRA 2007). Rome, Italy (2007)
Montemerlo, M., Thrun, S., Koller, D., Wegbreit, B.: FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI 2003). Acapulco, Mexico (2003)
Neira, J., Tardós, J.: Data association in stochastic mapping using the joint compatibility test. IEEE Trans. Robot. Autom. 17(6), 890–897 (2001)
Nguyen, V., Martinelli, A., Tomatis, N., Siegwart, R.: A comparison of line extraction algorithms using 2d laser rangefinder for indoor mobile robotics. In: Proceedings of the 2005 IEEE International Conference on Intelligent Robots and Systems (IROS 2005). Edmonton, Canada (2005)
Nieto, J., Bailey, T., Nebot, E.: Scan-SLAM: combining EKF-SLAM and scan correlation. In: Proceedings of the 2005 International Conference on Field and Service Robotics (FSR 2005). Port Douglas, Australia (2005)
Nieto, J., Guivant, J., Nebot, E.: DenseSLAM: the unidirectional information flow (UIF). In: Proceedings of the Fifth IFAC/EURON Symposium on Intelligent Autonomous Vehicles (IAV 2004). Lisbon, Portugal (2004)
Ojeda, L., Borenstein, J.: Methods for the reduction of odometry errors in over-constrained mobile robots. Auton. Robots 16, 273–286 (2004)
Ojeda, L., Cruz, D., Reina, G., Borenstein, J.: Current-based slippage detection and odometry correction for mobile robots and planetary rovers. IEEE Trans. Robot. 22(2), 366–378 (2006)
Olson, C.: Probabilistic self-localization for mobile robots. IEEE Trans. Robot. Autom. 16(1), 55–66 (2000)
Pfister, S., Kreichbaum, K., Roumeliotis, S., Burdick, J.: Weighted range sensor matching algorithms for mobile robot displacement estimation. In: Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA 2002). Washington, DC (2002)
Pfister, S., Roumeliotis, S., Burdick, J.: Weighted line fitting algorithms for mobile robot map building and efficient data representation. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA 2003). Taipei, Taiwan (2003)
Rady, S., Wagner, A., Badreddin, E.: Hierarchical localization using entropy-based feature map and triangulation techniques. In: Proceedings of the 2010 IEEE International Conference on Systems Man and Cybernetics (SMC 2010). Istanbul, Turkey (2010)
Ramos, F., Nieto, J., Durrant-Whyte, H.: Recognising and modelling landmarks to close loops in outdoor slam. In: Proceedings of the 2007 IEEE International Conference on Robotics and Automation (ICRA 2007). Rome, Italy (2007)
Sack, D., Burgard, W.: A comparison of methods for line extraction from range data. In: Proceedings of the 5th IFAC/EURON Symposium on Intelligent Autonomous Vehicles (IAV 2004). Lisbon, Portugal (2004)
Scalmato, A., Sgorbissa, A., Capezio, F., Mastrogiovanni, F., Vernazza, P., Vernazza, T., Zaccaria, R.: Mobile robots in hospital environments: an installation case study. In: Proceedings of the 5th International Conference on Mobile Robots (ECMR 2011). Orebro, Sweden (2011)
Scheding, S., Dissanayake, G., Nebot, E., Durrant-Whyte, H.: An experiment in autonomous navigation of an underground mining vehicle. IEEE Trans. Robot. Autom. 15(1), 85–95 (1999)
Schulz, D., Burgard, W., Fox, D., Cremers, A.: Tracking multiple moving targets with a mobile robot using particle filters and statistical data association. In: Proceedings of the 2001 IEEE International Conference on Robotics and Automation (ICRA 2001). Seoul, Korea (2001)
Sim, R., Roy, N.: Global A-optimal robot esploration in SLAM. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA 2005). Barcelona, Spain (2005)
Simoncelli, M., Zunino, G., Christensen, H., Lange, K.: Autonomous pool cleaning: self localization and autonomous navigation for cleaning. Auton. Robots 9, 261–270 (2000)
Stachniss, C., Grisetti, G., Burgard, W.: Recovering particle diversity in a Rao-Blackwellized particle filter for SLAM after actively closing loops. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation (ICRA 2005). Barcelona, Spain (2005)
Thrun, S., Beetz, M., Bennewitz, M., Burgard, W., Creemers, A., Dellaert, F., Fox, D., Hahnel, D., Rosenberg, C., Roy, N., Schulte, J., Schulz, D.: Probabilistic algorithms and the interactive museum tour-guide robot Minerva. Int. J. Rob. Res. 19(11), 972–999 (2000)
Thrun, S., Martin, C., Liu, Y., Hahnel, D., Emery-Montemerlo, R., Chakrabarti, D., Burgard, W.: A real-time Expectation-Maximization algorithm for acquiring multilanar maps of indoor environments with mobile robots. IEEE Trans. Robot. 20(3), 433–442 (2004)
Thrun, S., Montemerlo, M., Koller, D., Wegbreit, B., Nieto, J., Nebot, E.: FastSLAM: an efficient solution to the simultaneous localization and mapping problem with unknown data association. J. Mach. Learn. Res. 4, 1–48 (2004)
Tur, J., Gordillo, J., Borja, C.: A closed-form expression for the uncertainty in odometry position estimate of an autonomous vehicle. IEEE Trans. Robot. 21(5), 1017–1022 (2005)
Vu, T.D., Burlet, J., Aycard, O.: Grid-based localization and online mapping with moving objects detection and tracking: new results. In: Proceedings of the 2008 IEEE Intelligent Vehicles Symposium (IV 2008). Eindhoven, Netherlands (2008)
Wolf, D., Sukhatme, G.: Online simultaneous localization and mapping in dynamic environments. In: Proceedings of the 2004 IEEE International Conference on Robotics and Automation (ICRA 2004). New Orleans, LA (2004)
Wolf, D., Sukhatme, G.: Mobile robot simultaneous localization and mapping in dynamic environments. Auton. Robots 19, 53–65 (2005)
Wong, R., Xiao, J., Joseph, S.: A robust data association for simultaneous localization and mapping in dynamic environments. In: Proceedings of the 2010 IEEE International Conference on Information and Automation (ICIA 2010). Heilongjiang, China (2010)
Wulf, O., Lecking, D., Wagner, B.: Robust self-localization in industrial environments based on 3d ceiling structures. In: Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2006). Beijing, China (2006)
Zhou, H., Sakane, S.: Localizing objects during robot slam in semi-dynamic environments. In: Proceedings of the 2008 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM 2008). Xian, China (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mastrogiovanni, F., Sgorbissa, A. & Zaccaria, R. How the Location of the Range Sensor Affects EKF-based Localization. J Intell Robot Syst 68, 121–145 (2012). https://doi.org/10.1007/s10846-012-9673-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-012-9673-x