Bayesian inference is used to produce a sample-based representation (as shown above) of the posterior over topological maps using sampling algorithms such as Markov Chain Monte Carlo (MCMC) and Sequential Importance Sampling (SIS). The challenge is to design these algorithms so that they work efficiently and terminate relatively quickly with meaningful results. This is a significant challenge because the number of possible topologies increases at a hyper-exponential rate (faster than exponentially) with the number of landmarks observed. The number of topologies for n landmarks is given by the Bell number. The growth of the Bell number is shown in the table below -

Our computational framework overcomes this challenge of a combinatorial space and also supports the use of a wide variety of sensors (cameras, laser, odometry) that have been used to obtain results presented in the publications listed at the bottom. A couple of environments used in our experiments and their corresponding PTMs are shown below.

PTMs were the topic of my PhD thesis, and Frank and I have built up this edifice over a number of publications.

Publications

1. •Inference in the Space of Topological Maps: An MCMC-based Approach
   Ananth Ranganathan and Frank Dellaert, IROS 2004
   
   This paper introduces the concept of Probabilistic Topological Map (PTM) and provides an algorithm for obtaining a PTM using MCMC sampling. We obtain good results even when using only odometry and no other sensors!
   

2. •Dirichlet Process based Bayesian Partition Models for Robot Topological Mapping
   Ananth Ranganathan and Frank Dellaert, GIT-GVU-04-21 2004
   
   In this tech report, we explore the use of the Dirichlet Process as a prior over topologies. The Dirichlet process encodes the intuition that places that have been visited frequently in the past are also more likely to be visited in the future. Results obtained using this prior show a significant improvement over the use of a uniform prior on the space of topologies.
   

1. •Data driven MCMC for Appearance-based Topological Mapping
   Ananth Ranganathan and Frank Dellaert, RSS 2005
   
   This paper extends the previous paper by introducing the use of Fourier signatures of panoramic images as appearance measurements. In addition, we provide a data-driven proposal distribution using odometry that significantly improves the efficiency of the algorithm.
    
   

2. •Bayesian Inference in the Space of Topological Maps
   Ananth Ranganathan, Emanuele Menegatti, and Frank Dellaert
   IEEE Transactions on Robotics, 2006
   
   This journal paper combines the work of the previous two papers and, in addition, introduces the use of an urn-model prior over the space of topologies. This prior encodes a form of Occam's razor by making topologies with a large number of distinct landmarks unlikely. The prior also states that the robot is equally likely to visit any of the landmarks visited previously or a completely new landmark at any point in time.
    
   

3. •A Rao-Blackwellized Particle Filter for Topological Mapping
   Ananth Ranganathan and Frank Dellaert, ICRA 2006
   
   This paper adds to the previous work by providing a means to compute the PTMs incrementally using particle filtering. While the state space is combinatorial in nature, efficient computation is made possible by Rao-Blackwellization using the location of the landmarks. A data-driven proposal distribution is used for fast convergence. This is also the first PTM paper to use laser range scans as sensor input.
   

1. •Bayesian Surprise and Landmark Detection
   

2. Ananth Ranganathan and Frank Dellaert, ICRA 2009.
   
   None of the previous papers deal with the problem of landmark detection, i.e. identifying which places are worthy of becoming nodes in the topological map. In this paper, we propose the use of Bayesian surprise, first used in computer vision, for this purpose. The results, obtained in conjunction with the PTM algorithm, are promising.
   

3. 
   

4. •Online Probabilistic Topological Mapping
   

5. Ananth Ranganathan and Frank Dellaert
   

6. International Journal of Robotics Research, In Press
   
   This paper extends the particle filtering algorithm to use a bag-of-words appearance model founded on the Multivariate Polya distribution. This model is more powerful than the Fourier signatures used previously. We present extensive results on widely used SLAM datasets as well as timing comparisons between the various PTM algorithms.