中文摘要：

针对移动机器人蒙特卡罗定们（Monte Carlo localization, MCL）算法在含有对称和自相似结构的环境中容易失败的问题，提出了一种基于多假设跟踪的自适应蒙特卡罗定位改进算法，该算法根据粒子间空间相似性采用核密度树聚类算法对粒子群进行聚类，每簇粒子代表一个位姿假设并用一个独立的MCL算法进行跟踪，总体上形成了一组非等权的粒子滤波器，很好地克服了普通粒子滤波器由于粒子分管而引起的过度收敛问题，同时运用该核试试树实现了自适应采样，提高了算法的性能，针对机器人“绑架”问题对该算法作了进一步的改进，实验结果证明了该算法的有效性。

英文摘要：

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.