In this paper we describe a new technique for the creation of feature-based stochastic maps using standard Polaroid sonar sensors. The fundamental contributions of our proposal are: (1) a perceptual grouping process that permits the robust identification and localization of environmental features, such as straight segments and corners, from the sparse and noisy sonar data; (2) a map joining technique that allows the system to build a sequence of independent limited-size stochastic maps and join them in a globally consistent way; (3) a robust mechanism to determine which features in a stochastic map correspond to the same environment feature, allowing the system to update the stochastic map accordingly, and perform tasks such as revisiting and loop closing. We demonstrate the practicality of this approach by building a geometric map of a medium size, real indoor environment, with several people moving around the robot. Maps built from laser data for the same experiment are provided for comparison.
Bar-Shalom, Y., and Fortmann, T.E.1988. Tracking and Data Association. Boston, MA: Academic Press.
5.
Barshan, B., and Kuc, R.1990. Differentiating sonar reflections from corners and planes by employing an intelligent sensor. IEEE Trans. Pattern Analysis and Machine Intelligence12(6):560-569.
6.
Brooks, R.A.1984. Aspects of mobile robot visual map making. Second Int. Symp. Robotics Research, pp. 287-293. Tokyo , Japan: MIT Press.
7.
Castellanos, J.A., Montiel, J.M.M., Neira, J., and Tardós, J.D.1999. The SPmap: A probabilistic framework for simultaneous localization and map building. IEEE Trans. Robot. Automat . 15(5):948-953.
8.
Castellanos, J.A., Neira, J., and Tardós, J.D.2001. Multisensor fusion for simultaneous localization and map building. IEEE Trans. Robot. Automat. 17(6):908-914.
9.
Castellanos, J.A., and Tardós, J.D.1999. Mobile Robot Localization and Map Building: A Multisensor Fusion Approach. Boston, MA: Kluwer Academic Publishers.
10.
Chong, K.S., and Kleeman, L.1999. Feature-based mapping in real, large scale environments using an ultrasonic array. Int. J. Robotics Research18(1):3-19.
11.
Chong, K.S., and Kleeman, L.1999. Mobile-robot map building from an advanced sonar array and accurate odometry. Int. J. Robotics Research18(1):20-36.
12.
Choset, H., and Nagatani, K.2001. Topological simultaneous localization and mapping (SLAM): Toward exact localization without explicit localization. IEEE Trans. Robot. Automat. 17(2):125-137.
13.
Cox, I.J., and Leonard, J.J.1994. Modeling a dynamic environment using a Bayesian multiple hypothesis approach. Artificial Intelligence66(2):311-344. London: Elsevier Science Publishers.
14.
Davison, A.J.1998. Mobile Robot Navigation Using Active Vision. University of Oxford. Available from http://www.robots.ox.ac.uk/″ajd/.
15.
Dissanayake, M.W.M.G., Newman, P., Durrant-Whyte, H.F., Clark, S., and Csorba, M.2001. A solution to the simultaneous localization and map building (SLAM) problem. IEEE Trans. Robot. Automat. 17(3):229-241.
16.
Doucet, A., de Freitas, N., and Gordan, N.2001. Sequential Monte Carlo Methods in Practice. Springer-Verlag.
17.
Elfes, A.1987. Sonar-based real-world mapping and navigation. IEEE J. Robotics and Automation3(3):249-265.
18.
Faugeras, O.1993. Three-Dimensional Computer Vision: A Geometric Viewpoint . Cambridge, MA: MIT Press .
19.
Faugeras, O., and Luong, Q.T.2001. The Geometry of Multiple Images: The Laws That Govern the Formation of Multiple Images of a Scene and Some of their Applications . Cambridge, MA: The MIT Press .
20.
Feder, H.J.S., Leonard, J.J., and Smith, C.M.1999. Adaptive mobile robot navigation and mapping. Int. J. Robotics Research18(7):650-668.
21.
Fischler, M.A., and Bolles, R.C.1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. Assoc. Comp. Mach. 24(6):381-395.
22.
Grossmann, A., and Poli, R.2001. Robust mobile robot localisation from sparse and noisy proximity readings using Hough transform and probability grids. Robotics and Autonomous Systems37:1-18.
23.
Guivant, J.E., and Nebot, E.M.2001. Optimization of the simultaneous localization and map building algorithm for real time implementation. IEEE Trans. Robot. Automat. 17(3):242-257.
24.
Gutmann, J.S., and Konolige, K.1999. Incremental mapping of large cyclic environments . IEEE Int. Symp. on Computational Intelligence in Robotics and Automation CIRA, pp. 318-325.
25.
Hartley, R., and Zisserman, A.2000. Multiple View Geometry in Computer Vision. Cambridge, UK: Cambridge University Press .
26.
Illingworth, J., and Kittler, J.1988. A survey of the Hough transform. Computer Vision , Graphics and Image Processing44:87-116.
27.
Jazwinski, A.H.1970. Stochastic Processes and Filtering Theory. New York: Academic Press.
28.
Jensfelt, P.2001. Approaches to Mobile Robot Localization in Indoor Environments , PhD thesis, Royal Institute of Technology , Sweden. Available from http://www.nada.kth.se/″patric/ .
29.
Johnson, D., and Dudgeon, D.1993. Array Signal Processing. Prentice Hall .
30.
Julier, S.J.2001. A sparse weight Kalman filter approach to simultaneous localisation and map building. Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems IROS, Maui, Hawaii, vol. 3, pp. 1251-1256.
31.
Kleeman, L., and Kuc, R.1995. Mobile robot sonar for target localization and classification . Int. J. Robotics Research14(4):295-318.
32.
Knight, J., Davison, A., and Reid, I.2001. Towards constant time SLAM using postponement. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems IROS, Maui, Hawaii, vol. 1, pp. 405-413.
33.
Kuc, R., and Siegel, M.W.1987. Physically based simulation model for acoustic sensor robot navigation. IEEE Trans. Pattern Analysis and Machine Intelligence9(6):766-778.
34.
Kuipers, B.J.2000. The spatial semantic hierarchy. Artificial Intelligence, 119:191-233. London : Elsevier Science Publishers.
35.
Leonard, J.J., and Durrant-Whyte, H.F.1992. Directed Sonar Sensing for Mobile Robot Navigation. London: Kluwer Academic Pub.
36.
Leonard, J.J., and Feder, H.J.S.2000. A computationally efficient method for large-scale concurrent mapping and localization. In Robotics Research: The Ninth International Symposium, eds. D. Koditschek and J. Hollerbach, 169- 176. Snowbird, Utah: Springer-Verlag.
37.
Lozano-Pérez, T.1989. Foreword. In Autonomous Robot Vehicles , eds. I. J. Cox and G. T. Wilfong.Springer-Verlag.
38.
Lu, F., and Milios, E.1997. Globally consistent range scan alignment for environment mapping. Autonomous Robots4:333-349.
39.
Moutarlier, P., and Chatila, R.1989. Stochastic multisensory data fusion for mobile robot location and environment modeling. 5th Int. Symp. on Robotics Research. Tokyo, Japan.
40.
Neira, J., and Tardós, J.D.2001. Data association in stochastic mapping using the joint compatibility test. IEEE Trans. Robot. Automat. 17(6):890-897.
41.
Ortín, D., and Montiel, J.M.M.2001. Indoor robot motion from monocular images. Robotica19(3):331-342.
42.
Papoulis, A.1991. Probability, Random Variables, and Stochastic Processes . McGraw-Hill.
43.
Peremans, H., Audenaert, K., and Van, C.J.M.1993. A high-resolution sensor based on tri-aural perception . IEEE Trans. Robot. Automat. 9(1):36-48.
44.
Schultz, A.C., and Adams, W.1998. Continuous localization using evidence grids. Proc. IEEE Int. Conf. Robotics and Automation, pp. 2833-2839.
45.
Smith, R.C., and Cheeseman, P.1986. On the representation and estimation of spatial uncertainty . Int. J. Robotics Research5(4):56-68.
46.
Smith, R., and Self, M., and Cheeseman, P.1988. A stochastic map for uncertain spatial relationships . In Robotics Research, The Fourth Int. Symp., eds. O. Faugeras and G. Giralt , 467-474. The MIT Press.
47.
Thrun, S.2001. An online mapping algorithm for teams of mobile robots . Int. J. Robotics Research20(5):335-363.
48.
Wijk, O., and Christensen, H.I.2000. Triangulation based fusion of sonar data with application in robot pose tracking. IEEE Trans. Robot. Automat. 16(6):740-752.
49.
Wijk, O.2001. Triangulation Based Fusion of Sonar Data with Application in Mobile Robot Mapping and Localization, PhD thesis, Royal Institute of Technology, Stockholm, Sweden. Available from http://www.e.kth.se/″olle/.
50.
Williams, S.B.2001. Efficient Solutions to Autonomous Mapping and Navigation Problem, PhD thesis, Dept. of Mechanical and Mechatronic Engineering, University of Sydney. Available from http://www.acfr.usyd.edu.au/.
51.
Zunino, G., and Christensen, H.I.2001. Navigation in realistic environments . In 9th Int. Symp. on Intelligent Robotic Systems , SIRS, ed. M. Devy. Toulouse, France.
