Premature Convergence in Monte-Carlo LocalizationMonte-Carlo Localization (MCL) is a probabilistic method to estimate the position of a robot based on the robot's sensors readings and its odometry. MCL uses a Particle Filter for the estimation. A particle filter represents the probability distribution by a set of particles. The density of particles represents the probability. In Monte-Carlo Localization, a map of the environment is known. The robot's sensor information is used to determine the most likely position in the map.A Participle Filter shows remarkable similarities with a Genetic Algorithm: The fitness of every participle is determined by the resemblance of the robot's observation and the expected observation, the fittest particles survive and reproduce, and mutation is applied in the form of noise on the transition model. Initially, when nothing is known about the position of the robot, the particles are randomly distributed over the map. Every particle has a x- and y-position and an orientation. The position of the robot is then estimated by iteratively going through three steps:
However, there is a problem with the standard Particle Filter and therefore with Monte-Carlo Localization. This is the problem of premature convergence in the case of ambiguous situation, and thus multiple possible solutions to the estimation problem. Due to genetic or random drift, the particle population will quickly converge to one of the solutions. Since this solution might be the incorrect solution, this premature convergence is not desirable. Within the fields of Theoretical Biology and Genetic Algorithms, this problem has been studied. This has resulted in a number of so-called niching methods to preserve the diversity in the particle population. In (Kootstra et al, 2009), the application of the niching methods to solve the problem of premature convergence in MCL has been studied. This applet gives the possibility to study the effect of the different niching methods. More information about the methods and the results in Monte-Carlo Localization can be found in:
|