Abstract: This paper presents an improved algorithm that extends Monte Carlo localization (MCL) to solve the problem of localization failure in symmetric and/or self-similar environments. The algorithm clusters the particles adaptively according to their spatial similarity by using a kernel density (kd)-tree-based cluster algorithm. Each cluster of particles denotes a pose hypothesis and is traced by an individual MCL process so as to form a group of unequally weighted particle filters in general, thus overcoming the over-convergence problem due to lack of the particle sets. The kd-trees are also used for adaptive sampling to improve the algorithm performance. Further improvement to the algorithm makes it possible to solve the kidnapped robot problem as well, and the experimental results show that it has higher efficiency than the standard MCL algorithm.