We propose a factored approach to mobile robot map-building that handles qualitatively different types of uncertainty by combining the strengths of topological and metrical approaches. Our framework is based on a computational model of the human cognitive map; thus it allows robust navigation and communication within several different spatial ontologies. This paper focuses exclusively on the issue of map-building using the framework.
Our approach factors the mapping problem into natural sub-goals: building a metrical representation for local small-scale spaces; finding a topological map that represents the qualitative structure of large-scale space; and (when necessary) constructing a metrical representation for large-scale space using the skeleton provided by the topological map. We describe how to abstract a symbolic description of the robot’s immediate surround from local metrical models, how to combine these local symbolic models in order to build global symbolic models, and how to create a globally consistent metrical map from a topological skeleton by connecting local frames of reference.
Angluin, D. ( 1978). On the complexity of minimum inference of regular sets . Information and Control, 39: 337-350.
2.
Beeson, P. ( 2008). Creating and utilizing symbolic representations of spatial knowledge using mobile robots. Ph.D. Thesis, The University of Texas at Austin.
3.
Beeson, P., Jong, N.K. and Kuipers, B. ( 2005). Towards autonomous topological place detection using the extended Voronoi graph. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain, April, pp. 4373-4379.
4.
Beeson, P. et al. (2007). Integrating multiple representations of spatial knowledge for mapping, navigation, and communication. Proceedings of the Symposium on Interaction Challenges for Intelligent Assistants, AAAI Spring Symposium Series, Stanford, CA, AAAI Technical Report SS-07-04, March, pp. 1-9.
5.
Blanco, J.-L., Fernández-Madrigal, J.-A. and González , J. (2008). Toward a unified bayesian approach to hybrid metric-topological SLAM. IEEE Transactions on Robotics, 24(2): 259-270.
6.
Borenstein, J. and Koren, Y. ( 1991). The Vector Field Histogram-fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation , 7(3): 278- 288.
7.
Bosse, M. et al. (2003). Atlas framework for scalable mapping. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, September, pp. 1899-1906.
8.
Buschka, P. ( 2005). An investigation of hybrid maps for mobile robots. Ph.D. Thesis, Örebro University.
9.
Choi, C.-H. et al. (2002). Topological map building based on thinning and its application to localization. Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Lausanne, Switzerland, October, pp. 552-557.
10.
Choset, H. and Nagatani, K. ( 2001). Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 17(2): 125-137.
11.
Chown, E., Kaplan, S. and Kortenkamp, D. ( 1995). Prototypes, location, and associative networks (PLAN): towards a unified theory of cognitive mapping. Cognitive Science , 19(1): 1-51.
12.
Cummins, M. and Newman, P. ( 2007). Probabilistic appearance based navigation and loop closing . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy, November, pp. 2042-2048.
13.
Cummins, M. and Newman, P. ( 2008). FAB-MAP: Probabilistic localization and mapping in the space of appearance. International Journal of Robotics Research , 27(6): 647-665.
14.
Dean, T. et al. (1995). Inferring finite automata with stochastic output functions and an application to map learning. Machine Learning, 18(1): 81-108.
15.
Duckett, T. and Nehmzow, U. ( 1999). Exploration of unknown environments using a compass, topological map and neural network. Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), Monterey, CA, September, pp. 312- 317.
16.
Duckett, T. and Saffiotti, A. ( 2000). Building globally consistent gridmaps from topologies . Proceedings of the International IFAC Symposium on Robot Control (SYROCO), Vienna, Austria, pp. 357-361.
17.
Dudek, G., Freedman, P. and Hadjres, S. ( 1993). Using local information in a non-local way for mapping graph-like worlds. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Chambéry , France, September, pp. 1639-1647.
18.
Dudek, G. et al. (1991). Robotic exploration as graph construction . IEEE Transactions on Robotics and Automation, 7(6): 859-865.
19.
Elfes, A. ( 1989). Occupancy grids: a probabilistic framework for robot perception and navigation. Ph.D. Thesis, Carnegie Mellon University.
20.
Eliazar, A. and Parr, R. ( 2003). DP-SLAM: fast, robust simultaneous localization and mapping without predetermined landmarks. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, August, pp. 1135-1142.
21.
Fortune, S. ( 1992). Voronoi diagrams and Delaunay triangulations. Computing in Euclidean Geometry vol. 1 of Lecture Notes Series on Computing, Du, D.-Z. and Hwang, F. (eds). World Scientific, River Edge , New Jersey, pp. 193-234.
22.
Fox, D., Burgard, W. and Thrun, S. ( 1997). The dynamic window approach to collision avoidance. IEEE Robotics and Automation Magazine, 4(1): 22-33.
23.
Fox, D., Burgard, W. and Thrun, S. ( 1999). Markov localization for mobile robots in dynamic environments . Journal of Artificial Intelligence Research, 11: 391-427.
24.
Gladwin, T. ( 1970). East is a Big Bird: Navigation and Logic on Puluwat Atoll . Cambridge, MA, Harvard University Press.
25.
Gold, E.M. ( 1978). Complexity of automaton identification from given sets . Information and Control, 37: 302-320.
26.
Hähnel, D. et al. (2003a). An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements . Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, October, pp. 206-211.
27.
Hähnel, D. et al. (2003b). Towards lazy data association in SLAM. Proceedings of the International Symposium on Robotics Research (ISRR), Sienna, Italy, October, pp. 83-105.
28.
Harnad, S. ( 1990). The symbol grounding problem. Physica D, 42335-346.
29.
Ko, B.-Y., Song, J.-B. and Lee, S. ( 2004). Real-time building of a thinning-based topological map with metric features. Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Sendai , Japan, September, pp. 797-802.
30.
Koenig, S. and Simmons, R.G. ( 1996). Unsupervised learning of probabilistic models for robot navigation. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN, April, pp. 2301- 2308.
31.
Konolige, K. ( 2000). A gradient method for realtime robot control. Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Takamatsu, Japan, November, pp. 639-646.
32.
Konolige, K. ( 2004). Large-scale map-making. Proceedings of the National Conference on Artificial Intelligence (AAAI), San Jose, CA, July, pp. 457-463.
33.
Kortenkamp, D. and Weymouth, T. ( 1994). Topological mapping for mobile robots using a combination of sonar and vision sensing. Proceedings of the National Conference on Artificial Intelligence (AAAI), Seattle, WA, August, pp. 979-984.
34.
Kuffner, J.J. and LaValle, S.M. ( 2000). RRT-Connect: an efficient approach to single-query path planning. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April, pp. 995- 1,001.
35.
Kuipers, B. ( 2000). The Spatial Semantic Hierarchy. Artificial Intelligence, 119: 191-233.
36.
Kuipers, B. ( 2008). An intellectual history of the Spatial Semantic Hierarchy. Robotics and Cognitive Approaches to Spatial Mapping, vol. 38 of Springer Tracts in Advanced Robotics, Jefferies, M. E. and Yeap, W.-K. (eds). Berlin, Springer, pp. 243-264.
37.
Kuipers, B. and Beeson, P. ( 2002). Bootstrap learning for place recognition. Proceedings of the National Conference on Artificial Intelligence (AAAI), Edmonton, Canada, July, pp. 174-180.
38.
Kuipers, B. et al. (2004). Local metrical and global topological maps in the Hybrid Spatial Semantic Hierarchy. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA, April, pp. 4845-4851.
Kuipers, B.J. and Byun, Y.-T. ( 1991). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 847-63.
41.
Lankenau, A., Röfer, T. and Krieg-Brückner, B. ( 2002). Self-localization in large-scale environments for the bremen autonomous wheelchair. Spatial Cognition III, vol. 2,685 of Lecture Notes in Artificial Intelligence. Berlin, Springer, pp. 34-61.
42.
Lee, W.-Y. ( 1996). Spatial semantic hierarchy for a physical mobile robot. Ph.D. Thesis, The University of Texas at Austin.
43.
Leonard, J. and Newman, P. ( 2003). Consistent, convergent, and constant-time SLAM. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, pages 1,143-1,150.
Lu, F. and Milios, E. ( 1997). Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4: 333-349.
46.
Lynch, K. ( 1960). The Image of the City. Cambridge, MA, MIT Press.
47.
MacMahon, M., Stankiewicz, B. and Kuipers, B.J. ( 2006). Walk the talk: connecting language, knowledge, action in route instructions. Proceedings of the National Conference on Artificial Intelligence (AAAI), Boston, MA , July, pp. 1,475-1,482.
48.
Mataric, M.J. ( 1992). Integration of representation into goal-driven behavior-based robots. IEEE Transactions on Robotics and Automation, 8(3): 304-312.
49.
Modayil, J., Beeson, P. and Kuipers, B. ( 2004). Using the topological skeleton for scalable, global, metrical map-building. Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Sendai , Japan, September, pp. 1,530-1,536.
50.
Montemerlo, M. et al. (2002). FastSLAM: a factored solution to the simultaneous localization and mapping problem. Proceedings of the National Conference on Artificial Intelligence (AAAI), Edmonton, Canada, July, pp. 593-598.
51.
Montemerlo, M. et al. (2003). FastSLAM 2.0: an improved particle filtering algorithm for simultaneous localization and mapping that provably converges . Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, August, pp. 1,151-1,156.
52.
Moravec, H.P. ( 1988). Sensor fusion in certainty grids for mobile robots. AI Magazine, Summer: 61-74.
53.
Morris, A.C. et al. (2005). Towards topological exploration of abandoned mines. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain, April, pp. 2,117-2,123.
54.
Murarka, A., Modayil, J. and Kuipers, B. ( 2006). Building local safety maps for a wheelchair robot using vision and lasers. Proceedings of the Canadian Conference on Computer and Robot Vision (CRV), Quebec City , Canada, June, p. 25.
55.
Olson, E., Leonard, J. and Teller, S. ( 2006). Fast iterative optimization of pose graphs with poor initial estimates. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Orlando, Florida, May, pp. 2,262- 2,269.
56.
Paskin, M.A. ( 2003). Thin junction tree filters for simultaneous localization and mapping. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Acapulco , Mexico, August, pp. 1,157-1,166.
57.
Press, W.H. et al. (1992). Numerical Recipes in C: The Art of Scientific Computing, second edition. London, Cambridge University Press.
58.
Ranganathan, A. and Dellaert, F. ( 2005). Data driven MCMC for appearance-based topological mapping . Proceedings of Robotics: Science and Systems (RSS), Cambridge, MA, June, pp. 209-216.
59.
Ranganathan, A., Menegatti, E. and Dellaert, F. ( 2006). Bayesian inference in the space of topological maps. IEEE Transactions on Robotics, 22(1): 92-107.
60.
Rekleitis, I.M., Dujmovic, V. and Dudek, G. ( 1999). Efficient topological exploration. Proceedings of theIEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, May, pp. 676-681.
61.
Remolina, E. and Kuipers, B. ( 2004). Towards a general theory of topological maps. Artificial Intelligence, 152: 47- 104.
62.
Rivest, R.L. and Schapire, R.E. ( 1989). Inference of finite automata using homing sequences. Proceedings of the ACM Symposium on Theory of Computing (STOC) , Seattle, WA, May, pp. 411-420.
63.
Savelli, F. and Kuipers, B. ( 2004). Loop-closing and planarity in topological map-building . Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Sendai, Japan, September, pp. 1,511-1,517.
64.
Schapire, R.E. ( 1991). The design and analysis of efficient learning algorithms. Technical Report MIT/LCS/TR-493, MIT Laboratory for Computer Science.
65.
Schröter, D. ( 2006). Region & gateway mapping: acquiring structured and object-oriented representations of indoor environments. Ph.D. Thesis, Technical University of Munich.
66.
Schröter, D. et al. (2004). Detection and classification of gateways for the acquisition of structured robot maps. Proceedings of the Symposium of the German Association for Pattern Recognition (DAGM) , Tübingen, Germany, August, pp. 553-561.
67.
Shatkay, H. and Kaelbling, L.P. ( 1997). Learning topological maps with weak local odometric information . Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Nagoya, Japan, August, pp. 920- 929.
68.
Siegel, A.W. and White, S.H. ( 1975). The development of spatial representations of large-scale environments. Advances in Child Development and Behavior, vol. 10, Reese, H. W. (ed). New York, Academic Press, pp. 9-55.
69.
Silver, D. et al. (2004). Feature extraction for topological mine maps . Proceedings of the IEEE/RSJ Conference on Intelligent Robots and Systems (IROS), Sendai, Japan, September, pp. 773-779.
70.
Smith, R., Self, M. and Cheeseman, P. ( 1990). Estimating uncertain spatial relationships in robotics. Autonomous Robot Vehicles, Cox, I. J. and Wilfong, G. T. (eds). New York, Springer, pp. 167-193.
71.
Thrun, S. and Bücken, A. ( 1996). Integrating grid-based and topological maps for mobile robot navigation. Proceedings of the National Conference on Artificial Intelligence (AAAI), Portland, OR, August, pp. 944-950.
72.
Thrun, S., Burgard, W. and Fox, D. ( 2000a). A real-time algorithm for mobile robot mapping with applications to multi-robot and 3d mapping. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisico, CA, April, pp. 321-328.
73.
Thrun, S., Burgard, W. and Fox, D. ( 2005). Probabilistic Robotics. Cambridge, MA, MIT Press.
74.
Thrun, S., Fox, D. and Burgard, W. ( 2000b). Monte Carlo localization with mixture proposal distribution . Proceedings of the National Conference on Artificial Intelligence (AAAI), Austin, TX, August, pp. 859-865.
75.
Thrun, S. et al. (1998). Integrating topological and metric maps for mobile robot navigation: A statistical approach. Proceedings of the National Conference on Artificial Intelligence (AAAI), Madison, July, WI, pp. 989-995.
76.
Tomatis, N., Nourbakhsh, I. and Siegwart, R. ( 2002). Hybrid simultaneous localization and map building: Closing the loop with multi-hypotheses tracking. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May, pp. 2,749-2,754.
77.
Wallgrün, J.O. ( 2005). Autonomous construction of hierarchical voronoi-based route graph representations. Spatial Cognition IV. Reasoning, Action, Interaction, vol. 3,343 of Lecture Notes in Artificial Intelligence, Berlin, Springer, pp. 413-433.
78.
Yannakakis, M. and Lee, D. ( 1991). Testing finite state machines. Proceedings of the ACM Symposium on Theory of Computing (STOC), New Orleans, LA, May, pp. 476-485.
79.
Yeap, W.-K. ( 1988). Towards a computational theory of cognitive maps. Artificial Intelligence, 34297-360.
80.
Yeap, W.-K. and Jefferies, M.E. ( 1999). Computing a representation of the local environment. Artificial Intelligence, 107(2): 265-301.
81.
Zhang, T.Y. and Suen, C.Y. ( 1984). A fast parallel algorithm for thinning digital patterns . Communcations of the ACM, 27(3): 236-239.
82.
Zimmer, U.R. ( 2000). Embedding local metrical map patches in a globally consistent topological map. Proceedings of the International Symposium on Underwater Technology (UT), Tokyo, Japan, May, pp. 301-305.
