We present a novel algorithm for topological mapping, which is the problem of finding the graph structure of an environment from a sequence of measurements. Our algorithm, called Online Probabilistic Topological Mapping (OPTM), systematically addresses the problem by constructing the posterior on the space of all possible topologies given measurements. With each successive measurement, the posterior is updated incrementally using a Rao—Blackwellized particle filter. We present efficient sampling mechanisms using data-driven proposals and prior distributions on topologies that further enable OPTM’s operation in an online manner. OPTM can incorporate various sensors seamlessly, as is demonstrated by our use of appearance, laser, and odometry measurements. OPTM is the first topological mapping algorithm that is theoretically accurate, systematic, sensor independent, and online, and thus advances the state of the art significantly. We evaluate the algorithm on a robot in diverse environments.
Angeli A., Filliat D., Doncieux S. and Meyer J.-A (2008) Fast and incremental method for loop-closure detection using bags of visual words. IEEE Transactions on Robotics24(5): 1027- 1037.
2.
Aycard O., Charpillet F., Fohr D. and Mari JF ( 1997) Place learning and recognition using hidden Markov models . In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1741-1746.
3.
Bailey T. and Durrant-Whyte HF ( 2006) Simultaneous localisation and mapping (SLAM): Part II state of the art. Robotics and Automation Magazine (September).
4.
Blackwell D. and MacQueen JB ( 1973) Ferguson distributions via Polya urn schemes. Annals of Statistics1: 353-355.
5.
Blanco J-L., Fernandez-Madrigal J-A. and Gonzalez J. ( 2006) Consistent observation grouping for generating metric-topological maps that improves robot localization. In IEEE International Conference on Robotics and Automation (ICRA), pp. 818-823.
6.
Blanco J-L., Fernandez-Madrigal J-A. and Gonzalez J. ( 2008) Towards a unified Bayesian approach to hybrid metric-topological SLAM. IEEE Transactions on Robotics24: 259-270.
7.
Bolles R. and Fischler M. ( 1981) A RANSAC-based approach to model fitting and its application to finding cylinders in range data. In International Joint Conference on AI (IJCAI), Vancouver, BC, Canada, pp. 637-643.
8.
Bosse MC, Newman PM, Leonard JJ and Teller S. ( 2004) Simultaneous localization and map building in large-scale cyclic environments using the Atlas framework. The International Journal of Robotics Research23: 1113-1139.
9.
Burgard W., Fox D., Jans H., Matenar C. and Thrun S. ( 1999) Sonar-based mapping of large-scale mobile robot environments using EM. In International Conference on Machine Learning (ICML), Bled, Slovenia, pp. 67-76.
10.
Chen Y. and Medioni G. ( 1991) Object modelling by registration of multiple range images . In IEEE International Conference on Robotics and Automation (ICRA), pp. 2724-2729.
11.
Choset H. and Nagatani K. ( 2001) Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation17: 125-137.
12.
Cummins M. and Newman P. ( 2008) FAB-MAP: Probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research27: 647-665.
13.
Dedeoglu G., Mataric M. and Sukhatme H. ( 1999) Incremental, online topological map building with a mobile robot. In Proceedings of Mobile Robots.
14.
Dellaert F. ( 2001) Monte Carlo EM for Data Association and its Applications in Computer Vision. PhD thesis, School of Computer Science, Carnegie Mellon, September 2001. Also available as Technical Report CMU-CS-01-153.
15.
Dellaert F., Seitz SM, Thorpe CE and Thrun S. ( 2003) EM, MCMC, and chain flipping for structure from motion with unknown correspondence. Machine Learning50: 45-71.
16.
Doucet A., Godsill S. and Andrieu C. ( 2000) On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing10: 197-208.
17.
Dudek G., Hadjres S. and Freedman P. ( 1993) Using local information in a non-local way for mapping graph-like worlds. In International Joint Conference on AI (IJCAI), pp. 1639-1645.
18.
Dudek G. and Jugessur D. ( 2000) Robust place recognition using local appearance based methods. In IEEE International Conference on Robotics and Automation (ICRA), pp. 1030-1035.
19.
Eliazar A. and Parr R. ( 2003) DP-SLAM: Fast, robust simultaneous localization and mapping without predetermined landmarks. In International Joint Conference on AI (IJCAI).
20.
Fearnhead P. and Clifford P. ( 2003) Online inference for hidden Markov models. Journal of the Royal Statistical Society: Series B, 65: 887-899.
21.
Ferguson TS ( 1973) A Bayesian analysis of some nonparametric problems. Annals of Statistics1: 209-230.
22.
Goedemé T., Nuttin M., Tuytelaars T. and Van Gool L. ( 2007) Omnidirectional vision based topological navigation. International Journal of Computer Vision74: 219-236.
23.
Gutierrez-Osuna R. and Luo RC ( 1996) Lola: Probabilistic navigation for topological maps. AI Magazine17: 55-62.
24.
Gutmann J-S. and Konolige K. ( 2000) Incremental mapping of large cyclic environments. In IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), pp. 318-325.
25.
Hähnel D., Burgard W., Fox D. and Thrun S. ( 2003a) A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements . In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 206-211.
26.
Hähnel D., Burgard W., Wegbreit B. and Thrun S. ( 2003b) Towards lazy data association in SLAM. In Proceedings of the 11th International Symposium of Robotics Research (ISRR’03), Sienna, Italy. Berlin: Springer.
27.
Kaelbling L., Cassandra AR and Kurien JA ( 1996) Acting under uncertainty: Discrete Bayesian models for mobile-robot navigation. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
28.
Kaess M. and Dellaert F. ( 2005) A Markov chain Monte Carlo approach to closing the loop in SLAM. In IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain, April 2005, pp. 645-650.
29.
Kuipers B. and Beeson P. ( 2002) Bootstrap learning for place recognition. In Proceedings 19th AAAI National Conference on AI, Edmonton, Alberta, Canada, 2002, pp. 174-180.
30.
Kuipers BJ and Byun Y.-T (1991) A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems8: 47-63.
31.
Kuipers BJ, Modayil J., Beeson P., MacMahon M. and Savelli F. ( 2004) Local metrical and global topological maps in the hybrid spatial semantic hierarchy. In IEEE International Conference on Robotics and Automation (ICRA).
32.
Lowe DG Distinctive image features from scale-invariant key-points. International Journal of Computer Vision60: 91-110.
33.
Lu F. and Milios E. ( 1997) Globally consistent range scan alignment for environment mapping. Autonomous Robots, pp. 333-349.
34.
Lynch K. ( 1971) The Image of the City. Cambrdige, MA: MIT Press.
35.
Madsen RE, Kauchak D. and Elkan C. ( 2005) Modeling word burstiness using the dirichlet distribution . In International Conference on Machine Learning (ICML), pp. 545-552.
36.
Matarić MJ ( 1990) A Distributed Model for Mobile Robot Environment-learning and Navigation. Master’s thesis, MIT, Artificial Intelligence Laboratory, Cambridge, January 1990. Also available as MIT AI Lab Technical Report AITR1228.
37.
Minka TP ( 2003) Estimating a Dirichlet distribution, http://www.stat.cmu.edu/∼minka/papers/dirichlet.
38.
Modayil J., Beeson P. and Kuipers B. ( 2004) Using the topological skeleton for scalable global metrical map-building. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
39.
Montemerlo M. and Thrun S. ( 2003) Simultaneous localization and mapping with unknown data association using FastSLAM. In IEEE International Conference on Robotics and Automation (ICRA).
40.
Neira J. and Tardos JD ( 2001) Data association in stochastic mapping using the joint compatibility test. IEEE Transactions on Robotics and Automation17: 890-897.
41.
Newman P., Cole D. and Ho K. ( 2006) Outdoor SLAM using visual appearance and laser ranging . In IEEE International Conference on Robotics and Automation (ICRA).
42.
Nijenhuis A. and Wilf H. ( 1978) Combinatorial Algorithms, 2nd ed. New York: Academic Press .
43.
Pierce D. and Kuipers B. ( 1997) Map learning with uninterpreted sensors and effectors . Artificial Intelligence92: 169-229.
44.
Pradeep V., Medioni G. and Weiland J. ( 2009) Visual loop closure detection using multi-resolution SIFT grids in metric-topological SLAM. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
45.
Ranganathan A. and Dellaert F. ( 2004) Inference in the space of topological maps: An MCMC-based approach. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
46.
Ranganathan A. and Dellaert F. ( 2006) A Rao-Blackwellized particle filter for topological mapping . In IEEE International Conference on Robotics and Automation (ICRA), pp. 810-817.
47.
Ranganathan A. and Dellaert F. ( 2009) Bayesian surprise and landmark detection. In IEEE International Conference on Robotics and Automation (ICRA) .
48.
Ranganathan A., Menegatti E. and Dellaert F. ( 2006) Bayesian inference in the space of topological maps. IEEE Transactions on Robotics22: 92-107.
49.
Remolina E. and Kuipers B. ( 2004) Towards a general theory of topological maps. Artificial Intelligence152: 47-104.
50.
Savelli F. and Kuipers B. ( 2004) Loop-closing and planarity in topological map-building . In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
51.
Schroter D., Beetz M. and Radig B. ( 2003) RG Mapping: Building object-oriented representations of structured human environments. In 6th Open Russian-German Workshop on Pattern Recognition and Image Understanding (OGRW).
52.
Se S., Lowe DG and Little JJ ( 2005) Vision-based global localization and mapping for mobile robots. IEEE Transactions on Robotics21: 364-375.
53.
Shatkay H. and Kaelbling L. ( 1997) Learning topological maps with weak local odometric information . In International Joint Conference on AI (IJCAI) , pp. 920-929.
54.
Sivic J., Russell B., Efros AA, Zisserman A. and Freeman B. ( 2005) Discovering objects and their location in images. In International Conference on Computer Vision (ICCV).
55.
Tapus A. ( 2005) Topological SLAM - Simultaneous Localization and Mapping with Fingerprints of Places. PhD thesis, Swiss Federal Institute of Technology Lausanne (EPFL).
56.
Thrun S., Burgard W. and Fox D. ( 2005) Probabilistic Robotics. Cambridge, MA: The MIT Press.
57.
Thrun S., Fox D. and Burgard W. ( 1998a) A probabilistic approach to concurrent mapping and localization for mobile robots. Machine Learning31: 29-53.
58.
Thrun S., Gutmann S., Fox D., Burgard W. and Kuipers BJ ( 1998b) Integrating topological and metric maps for mobile robot navigation: A statistical approach. In Proceedings of the 15th AAAI National Conference on AI, pp. 989-995.
59.
Tomatis N., Nourbakhsh I. and Siegwart R. ( 2002) Hybrid simultaneous localization and map building: Closing the loop with multi-hypotheses tracking. In IEEE International Conference on Robotics and Automation (ICRA), pp. 2749-2754.
60.
Valgren C., Lilienthal A. and Duckett T. ( 2006) Incremental topological mapping using omnidirectional vision. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
61.
Williams B., Klein G. and Reid I. ( 2007) Real-time SLAM relocalisation. In International Conference on Computer Vision (ICCV).
62.
Yamauchi B. and Beer R. ( 1996) Spatial learning for navigation in dynamic environments. IEEE Transactions on Systems, Man, and Cybernetics-Part B26: 496-505.
63.
Yamauchi B. and Langley P. ( 1997) Place recognition in dynamic environments. Journal of Robotic Systems14: 107-120.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
