Abstract
This paper addresses the problem of building large-scale geometric maps of indoor environments with mobile robots. It poses the map building problem as a constrained, probabilistic maximum-likelihood estimation problem. It then devises a practical algorithm for generating the most likely map from data, along with the most likely path taken by the robot. Experimental results in cyclic environments of size up to 80 by 25 meter illustrate the appropriateness of the approach.
Article PDF
Similar content being viewed by others
References
Borenstein, J., Everett, B., & Feng, L. (1996). Navigating Mobile Robots: Systems and Techniques. Wellesley, MA: A. K. Peters, Ltd.
Buhmann, J., Burgard, W., Cremers, A. B., Fox, D., Hofmann, T., Schneider, F., Strikos, J., & Thrun, S. (1995). The mobile robot Rhino. AI Magazine, 16, 31–38.
Burgard, W., Fox, D., Hennig, D., & Schmidt, T. (1996). Estimating the absolute position of a mobile robot using position probability grids. Proceedings of the Thirteenth National Conference on Artificial Intelligence (pp. 896–901). Menlo Park, CA: AAAI Press/MIT Press.
Burgard, W., Fox, D., & Hennig, D. (1997). Fast grid-based position tracking for mobile robots. Proceedings of the 21th German Conference on Artificial Intelligence (pp. 289–300). Berlin: Springer Verlag.
Burgard, W., Cremers, A.B., Fox, D., Haehnel, D., Lakemeyer, G., Schulz, D., Steiner, W. & Thrun, S. (1998). Proceedings of the AAAI National Conference on Artificial Intelligence. Forthcoming.
Chatila, R., & Laumond, J.-P. (1985). Position referencing and consistent world modeling for mobile robots. Proceedings of the 1985 IEEE International Conference on Robotics and Automation (pp. 138–145).
Choset, H. (1996). Sensor based motion planning: The hierarchical generalized voronoi graph. Doctoral dissertation, California Institute of Technology.
Dempster, A., Laird, A., & Rubin, D. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series B, 39, 1–38.
Elfes, A. (1989). Occupancy Grids: A Probabilistic Framework for Robot Perception and Navigation. Doctoral dissertation, Department of Electical and Computer Engineering, Carnegie Mellon University.
Fox, D., Burgard, W., & Thrun, S. (1997). A hybrid collision avoidance method for mobile robots. (Internal Report). Bonn, Germany: Universität Bonn, Institut für Informatik III.
Gutmann, J.-S. (1996). Vergleich von Algorithmen zur Selbstlokalisierung eines mobilen Roboters. Master's thesis, University of Ulm, Ulm, Germany.
Kaelbling, L., Cassandra, A., & Kurien, J. (1996). Acting under uncertainty: Discrete bayesian models for mobilerobot navigation. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 963–972).
Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Transactions ASME, Journal of Basic Engineering, 82, 35–45.
King, S., & Weiman, C. (1990). Helpmate autonomous mobile robot navigation system. Proceedings of the SPIE Conference on Mobile Robots (pp. 190–198). Volume 2352. Boston, MA.
Koenig, S., & Simmons, R. (1996). Passive distance learning for robot navigation. Proceedings of the Thirteenth International Conference on Machine Learning (pp. 266–274). San Mateo, CA: Morgan Kaufmann.
Kuipers, B., & Byun, Y.-T. (1991). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 8, 47–63.
Leonard, J., Durrant-Whyte, H., & Cox, I. (1992). Dynamic map building for an autonomous mobile robot. International Journal of Robotics Research, 11, 89–96.
Lopez, M., Lopez de Mantaras, R., & Sierra, C. (1997). Incremental map generation by low cost robots based on possibility/necessity grids. Proceedings of the Thirteenth International Conference on Uncertainty in AI (pp. 351–357). Providence, RI.
Lu, F., & Milios, E. (1997). Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4, 333–349.
Matarić, M. J. (1997). Reinforcement learning in the multi-robot domain. Autonomous Robots, 4(1), 73–83.
Matarić, M. (1994). Interaction and intelligent behavior (Tech. rep. AI-TR-1495). Cambridge, MA: Massachusetts Institute of Technology, Artificial Intelligence Laboratory.
Moravec, H. P. (1988). Sensor fusion in certainty grids for mobile robots. AI Magazine, 9, 61–74.
Nourbakhsh, I., Powers, R., & Birchfield, S. (1995). DERVISH: An office-navigating robot. AI Magazine, 16, 53–60.
Oore, S., Hinton, G., & Dudek, G. (1997). A mobile robot that learns its place. Neural Computation, 9, 683–699.
Parker, L. E. (1996). On the design of behavior-based multi-robot teams. Journal of Advanced Robotics, 10(6).
Rabiner, L., & Juang, B. (1986). An introduction to hidden Markov models. IEEE ASSP Magazine.
Rencken, W. (1993). Concurrent localisation and map building for mobile robots using ultrasonic sensors. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 2129–2197). Yokohama, Japan.
Shatkay, H., & Kaelbling, L. (1997a). Learning topological maps with weak local odometric information. Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (pp. 920–927). San Mateo, CA: Morgan Kaufmann.
Shatkay, H., & Kaelbling, L. (1997b). Learning hidden Markov models with geometric information (Tech. rep. CS–97–04). Providence, RI: Brown University, Computer Science Department.
Simmons, R., & Koenig, S. (1995). Probabilistic robot navigation in partially observable environments. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (pp. 1080–1087). San Mateo, CA: Morgan Kaufmann.
Thrun, S. (1993). Exploration and model building in mobile robot domains. Proceedings of the International Conference on Neural Networks (pp. 175–180). San Francisco, CA: IEEE Neural Network Council.
Thrun, S. (1998). Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence, 99(1), pp. 21–71.
Thrun, S. (in press). Bayesian landmark learning for mobile robot localization. Machine Learning.
Thrun, S., Bücken, A., Burgard, W., Fox, D., Fröhlinghaus, T., Hennig, D., Hofmann, T., Krell, M. & Schimdt, T. (1998). Map learning and high-speed navigation in RHINO. In D. Kortenkamp, R. Bonasso, & R. Murphy (Eds.), AI-based mobile robots: Case studies of successful robot systems. Cambridge, MA: MIT Press, pp. 21–52.
Yamauchi, B., & Beer, R. (1996). Spatial learning for navigation in dynamic environments. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, Special Issue on Learning Autonomous Robots. Also available at http://www.aic.nrl.navy.mil/~yamauchi/.
Rights and permissions
About this article
Cite this article
Thrun, S., Burgard, W. & Fox, D. A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots. Machine Learning 31, 29–53 (1998). https://doi.org/10.1023/A:1007436523611
Issue Date:
DOI: https://doi.org/10.1023/A:1007436523611