Көлденең Карло локализациясы және KLD-үлгілеу алгоритмі

Monte Carlo localization (MCL), also known as particle filter localization, is an algorithm for robots to localize using a particle filter. Given a map of the environment, the algorithm estimates the position and orientation of a robot as it moves and senses the environment. KLD–sampling is a variant of Monte Carlo Localization where at each iteration, a sample size is calculated. The sample size is calculated such that, with probability , the error between the true posterior and the sample based approximation is less than The variables and are fixed parameters. The main idea is to create a grid (a histogram) overlaid on the state space. Each bin in the histogram is initially empty. At each iteration, a new particle is drawn from the previous (weighted) particle set with probability proportional to its weight. Instead of the resampling done in classic MCL, the KLD–sampling algorithm draws particles from the previous, weighted, particle set and applies the motion and sensor updates before placing the particle into its bin. The algorithm keeps track of the number of non empty bins, If a particle is inserted in a previously empty bin, the value of is recalculated, which increases mostly linear in This is repeated until the sample size is the same as
It is easy to see KLD–sampling culls redundant particles from the particle set, by only increasing when a new location (bin) has been filled. In practice, KLD–sampling consistently outperforms and converges faster than classic MCL.