Abstract
In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for guiding movement. We refer to such a representation as a map, and the process of constructing a map from a set of measurements as map learning. In this paper, we develop a framework for describing map-learning problems in which the measurements taken by the robot are subject to known errors. We investigate approaches to learning maps under such conditions based on Valiant's probably approximately correct learning model. We focus on the problem of coping with accumulated error in combining local measurements to make global inferences. In one approach, the effects of accumulated error are eliminated by the use of local sensing methods that never mislead but occasionally fail to produce an answer. In another approach, the effects of accumulated error are reduced to acceptable levels by repeated exploration of the area to be learned. We also suggest some insights into why certain existing techniques for map learning perform as well as they do. The learning problems explored in this paper are quite different from most of the classification and boolean-function learning problems appearing in the literature. The methods described, while specific to map learning, suggest directions to take in tackling other learning problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L. & Rackoff, C., (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Symposium on the Foundations of Computer Science, pages 218-223.
Basye, K. & Dean, T., (1989). Map learning with indistinguishable locations. In Proceedings of the 1989 Workshop on Uncertainty in Artificial Intelligence, pages 7-13.
Brooks, R.A., (1984). Aspects of mobile robot visual map making. In H. Hanafusa and H. Inoue, editors, Second International Symposium on Robotics Research, pages 325-331, Cambridge, Massachusetts: MIT Press.
Davis, E., (1986). Representing and Acquiring Geographic Knowledge. Morgan-Kaufmann, Los Altos, California.
Dean, T., (1988). On the complexity of integrating spatial measurements. In Proceedings of the SPIE Conference on Advances in Intelligent Robotic Systems. SPIE.
Dudek, G., Jenkins, M., Milios, E. & Wilkes, D., (1988). Robotic exploration as graph construction. Technical Report RBCV-TR-88-23, University of Toronto.
Durrant-Whyte, H.F., (1988). Integration, Coordination and Control of Multi-Sensor Robot Systems. Kluwer, Boston, Massachusetts.
Graham, R.L., Knuth, D.E. & Oren, P., (1994). Concrete Mathematics. Addison-Wesley, Reading, Massachusetts, 2nd edition.
Hoeffding, W., (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30.
Kuipers, B., (1978). Modeling spatial knowledge. Cognitive Science, 2:129-153.
Kuipers, B.J. & Byun, Y.-T., (1988). A robust, qualitative method for robot spatial reasoning. In Proceedings AAAI-88, pages 774-779. AAAI.
Levitt, T.S., Lawton, D.T., Chelberg, D.M. & Nelson, P.C., (1987). Qualitative landmark-based path planning and following. In Proceedings AAAI-87, pages 689-694. AAAI.
McDermott, D.V. & Davis, E., (1982). Planning routes through uncertain territory. Artificial Intelligence, 22:107-156.
Moravec, H.P. & Elfes, A., (1985). High resolution maps from wide angle sonar. In IEEE International Conference on Robotics and Automation, pages 138-145, 1985.
Rivest, R.L. & Sloan, R., (1994). A formal model of hierarchical concept learning. Information and Computation, 114(1):88-114.
Smith, R. & Cheeseman, P., (1986). On the representation and estimation of spatial uncertainty. The International Journal of Robotics Research, 5:56-68.
Valiant, L.G., (1984). A theory of the learnable. Communications of the ACM, 27:1134-1142.
Yemini, Y. (1979). Some theoretical aspects of position-location problems. In Proceedings of the 20th Symposium on the Foundations of Computer Science, pages 1-7.