Mobile robot localization is the problem of determining
a robot's pose from sensor data. Monte Carlo Localization is a family
of algorithms for localization based on particle filters, which are
approximate Bayes filters that use random samples for posterior
estimation. Recently, they have been applied with great success for
robot localization. Unfortunately, regular particle filters perform
poorly in certain situations. Mixture-MCL, the algorithm described
here, overcomes these problems by using a "dual" sampler, integrating
two complimentary ways of generating samples in the estimation. To
apply this algorithm for mobile robot localization, a kd-tree is
learned from data that permits fast dual sampling. Systematic
empirical results obtained using data collected in crowded public
places illustrate superior performance, robustness, and efficiency,
when compared to other state-of-the-art localization algorithms.