Tackling the Premature Convergence Problem in Monte-Carlo Localization

Robot navigation based on Monte Carlo localization suffers from the loss of potential positions if ambiguity is present in the environment. This is the problem of premature convergence. We propose a solution to this problem that is based on the observation that particle filters and genetic algorithms are very similar stochastic search methods. Both methods are based on an iterative process of mutation, selection and reproduction.

Within the field of genetic algorithms, a number of techniques exists that form a solution to the premature convergence problem, the so called niching methods. We implemented a few of these methods on a particle filter for Monte Carlo localization (i.e., crowding, sharing and local selection).

The experiments show a significant improvement in the diversity maintaining performance of the particle filter. The results support our claim that much can be gained from cooperation between the fields of particle filters and genetic algorithms.

Demo

You can experiment with the presented niching methods in this Java applet. Contact me if you are interested in the code.

Publications

• Kootstra, G. & de Boer, B. (2009) Tackling the Premature Convergence Problem in Monte-Carlo Localization. Robotics and Autonomous Systems 57(11): 1107-1118. Excepted manuscript: doi:10.1016/j.robot.2009.07.003. not available