RBPF-SLAM algorithms (C++ library mrpt-slam)

1. Mathematical background

References for reading:

  • “Rao-Blackwellised particle filtering for dynamic Bayesian networks”, Doucet, A. and De Freitas, N. and Murphy, K. and Russell, S. (2000) – PDF
  • Some slides, by Boris Lipchin.

 

2. RBPF-based SLAM solutions implemented in MRPT

A RBPF is a special instance of a particle filter, thus in principle any of the four generic filtering algorithms declared in the virtual C++ base classes can be used to sequentially estimate the robot path. Just a quick summary of the algorithms:

  • Sequential Importance Resampling – SIR with the “standard” proposal distribution (enum value: pfStandardProposal)
  • Auxiliary Particle Filter – APF with the “standard” proposal distribution (enum value: pfAuxiliaryPFStandard)
  • Optimal proposal distribution (enum value: pfOptimalProposal)
  • Approximate Optimal Sampling – A rejection sampling-based approximation to the optimal proposal when a closed-form expression is not available (enum value: pfAuxiliaryPFOptimal)

Note: So far (Aug 2011), there is no RBPF-SLAM implementation with the APF algorithm (which is in turn useful for Monte Carlo localization).

2.1. pfStandardProposal: SIR with “standard proposal” and any kind of metric map

Description: The pfStandardProposal algorithm can be used with any metric map or combination of several of them simultaneously, provided that an observation likelihood function is implemented for the sensor observations in each map. This algorithm however is not recommendable since the “standard” proposal distribution is the motion model (the “actions“), and most of the particles will end up in areas incompatible with the observations, and thus, resampling will occur quite often. Only use this algorithm if the motion model is known to be very precise. Example config files:

2.2. pfAuxiliaryPFOptimal: Approximate optimal proposal with any kind of metric map

Description: The pfAuxiliaryPFOptimal algorithm (introduced in this and this papers) can be used with any metric map or combination of several of them simultaneously, provided that an observation likelihood function is implemented for the sensor observations in each map. The algorithm will automatically approximate the optimal proposal distribution disregarding the quality of the motion model. However, the worse the motion model, the longer it will take to run each iteration. Example config files:

 

Example of gridmapping with a RBPF (rbpf-slam app).

Example of gridmapping with a RBPF (rbpf-slam app).

2.3. pfOptimalProposal: Optimal proposal for grid maps

Description: The pfOptimalProposal algorithm for grid maps corresponds to the heuristic approximation of the optimal proposal introduced by G. Grisetti et al. in: “Improved Techniques for Grid Mapping With Rao-Blackwellized Particle Filters”, Grisetti, G. Stachniss, C. Burgard, W. IEEE TRANSACTIONS ON ROBOTICS (2007) – PDF The implementation in MRPT relies on a version of ICP for gridmaps. An alternative implementation (independent of MRPT) is the popular gmappingNote: pfOptimalProposal requires setting the parameter pfOptimalProposal_mapSelection (see example config files for details). Example config files:

2.4. pfOptimalProposal: Optimal proposal for point maps

Description: The pfOptimalProposal algorithm for point maps is a version of the Grisetti et al.’s idea, but applied to point clouds (faster to update than grid maps). AFAIK, this method hasn’t been published in the literature, but works quite fine. Note: pfOptimalProposal requires setting the parameter pfOptimalProposal_mapSelection (see example config files for details). Example config files:

  • Pablo Iñigo Blasco

    Good post 🙂

    • jlblanco

      Thanks!! Good to see you around 😉

  • ingkanit

    Hi, thanks for the great work!

    Is the “pfOptimalProposal” RBPF SLAM algorithm equivalent to gmapping? If not, what are the differences? The gmapping algorithm is suggested to work as black box with the standard parameters. Is it possible to map these standard parameters to parameters for MRPT?