Probabilistic Topological Maps

While probabilistic approaches to metric mapping have proven highly successful, similar approaches to topological mapping have not yet appeared. Probabilistic Topological Maps (PTMs) offer a general and comprehensive Bayesian solution to the problem of topological mapping. The main thrust is towards solving the perceptual aliasing problem in a manner that supports quantification of the correctness of the mapping result, and hence, graceful failure.

This project aims to extend the probabilistic approach to topological mapping by computing the probability distribution over the space of all topological maps. Bayesian inference is used to produce a sample-based representation of the posterior over topological maps using sampling algorithms such as Markov Chain Monte Carlo (MCMC) and Sequential Importance Sampling (SIS). The figure above shows examples of the posterior over topological maps computed using these algorithms. Our computational framework supports the use of a wide variety of sensors 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.

Publications

• 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. The results demonstrate that this approach produces good results even when odometry is the only measurement available.
   
• 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.
   
• Bayesian Inference in the Space of Topological Maps.
  Ananth Ranganathan, Emanuele Menegatti, and Frank Dellaert.
  IEEE Transactions on Robotics (In press).
  

  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 Ockham'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.
   

• 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. We show that the metric map can be recovered from the topological map using a Lu-Milios post-processing step.
  
  
• 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.