Coevolution Based Adaptive Monte Carlo Localization (CEAMCL)

Ronghua Luo, Bingrong Hong

Abstract

An adaptive Monte Carlo localization algorithm based on the coevolution mechanism of ecological species is proposed. Samples are clustered into species, each of which represents a hypothesis of the robot's pose. Since the coevolution between the species ensures that the multiple distinct hypotheses can be tracked stably, the problem of premature convergence when using MCL in highly symmetric environments can be solved. And the sample size can be adjusted adaptively over time according to the uncertainty of the robot's pose by using the population growth model. In addition, by using the crossover and mutation operators in evolutionary computation, intra-species evolution can drive the samples move towards the regions where the desired posterior density is large. So a small size of samples can represent the desired density well enough to make precise localization. The new algorithm is termed coevolution based adaptive Monte Carlo localization (CEAMCL). Experiments have been carried out to prove the efficiency of the new localization algorithm.

Introduction

Mobile robot localization—the challenge of determining a robot's position within a map—is a cornerstone of autonomous navigation. While Monte Carlo Localization (MCL) is a popular solution, it often struggles in highly symmetric environments, such as long hallways with identical doors. In these cases, standard MCL can suffer from premature convergence, where the algorithm incorrectly commits to a single pose hypothesis and discards the true location. Furthermore, achieving high precision often requires a large number of particles, leading to significant computational overhead.

The CEAMCL Framework

To address these challenges, the Coevolution Based Adaptive Monte Carlo Localization (CEAMCL) algorithm introduces an ecological perspective to particle filtering.

Species Clustering and Inter-Species Competition

Instead of treating all particles as a single population, CEAMCL clusters samples into distinct "species," each representing a different hypothesis of the robot's pose. These species interact through a competition mechanism based on the Lotka-Volterra model.

Phase-plane analysis of the Lotka-Volterra competition model used to manage multiple pose hypotheses (species) in CEAMCL.

As illustrated in the figure above, the Lotka-Volterra equations define how populations compete for limited resources (in this case, computational capacity). By adjusting competition coefficients, the system can achieve stable coexistence (scenario d), allowing the robot to maintain multiple plausible hypotheses simultaneously. This prevents the "winner-take-all" effect where one hypothesis prematurely dominates the others.

CEAMCL dynamically adjusts the total number of samples based on the uncertainty of the robot's pose. When the robot is uncertain, the population grows to explore the map; as it gains confidence, the population shrinks to improve efficiency.

Additionally, the algorithm applies genetic operators—crossover and mutation—within each species. This intra-species evolution drives particles toward areas of higher likelihood more effectively than random sampling, allowing a small number of particles to represent complex probability densities with high precision.

Experimental Validation

The researchers evaluated CEAMCL using a Pioneer II robot in a laboratory environment specifically designed with high symmetry to confuse standard algorithms.

  • Success Rate: CEAMCL achieved a 100% success rate in multi-hypothesis tracking, compared to 86% for standard MCL and 82% for Genetic MCL (GMCL).
  • Hypothesis Stability: CEAMCL maintained alternative hypotheses indefinitely during tests, whereas other methods saw their secondary hypotheses vanish within 30–36 seconds.
  • Efficiency: While individual iterations are more complex, the adaptive sample size allows CEAMCL to be more efficient over time as the robot's pose becomes certain.

Conclusion

CEAMCL offers a robust solution for robot localization in challenging environments by treating pose hypotheses as coevolving ecological species. By combining the stability of the Lotka-Volterra competition model with the search efficiency of genetic algorithms, it provides a scalable and reliable alternative to traditional Monte Carlo methods. Future work may involve extending this framework to dynamic environments with moving obstacles.

Summary updated

Abstract

An adaptive Monte Carlo localization algorithm based on coevolution mechanism of ecological species is proposed. Samples are clustered into species, each of which represents a hypothesis of the robots pose. Since the coevolution between the species ensures that the multiple distinct hypotheses can be tracked stably, the problem of premature convergence when using MCL in highly symmetric environments can be solved. And the sample size can be adjusted adaptively over time according to the uncertainty of the robots pose by using the population growth model. In addition, by using the crossover and mutation operators in evolutionary computation, intra-species evolution can drive the samples move towards the regions where the desired posterior density is large. So a small size of samples can represent the desired density well enough to make precise localization. The new algorithm is termed coevolution based adaptive Monte Carlo localization (CEAMCL). Experiments have been carried out to prove the efficiency of the new localization algorithm.
BibTeX
@article{luo2004coevolution,
  author = {Ronghua Luo and Bingrong Hong},
  title = {{Coevolution Based Adaptive Monte Carlo Localization (CEAMCL)}},
  journal = {International Journal of Advanced Robotic Systems},
  year = {2004},
  doi = {10.5772/5634},
}
Figure