Введение

Монте-Карло локализация (MCL), также известная как локализация фильтром частиц, – это алгоритм, позволяющий роботам определять своё местоположение с использованием фильтра частиц. При наличии карты окружающей среды алгоритм оценивает положение и ориентацию робота по мере его движения и восприятия окружающей среды. KLD-sampling – это вариант Монте-Карло локализации, в котором на каждой итерации вычисляется размер выборки. Размер выборки вычисляется таким образом, чтобы с вероятностью погрешность между истинным апостериорным распределением и аппроксимацией на основе выборки была меньше, чем . Переменные и – фиксированные параметры. Основная идея заключается в создании сетки (гистограммы), наложенной на пространство состояний. Каждая ячейка гистограммы изначально пуста. На каждой итерации новая частица извлекается из предыдущего (взвешенного) набора частиц с вероятностью, пропорциональной её весу. Вместо передискретизации, выполняемой в классической MCL, алгоритм KLD-sampling извлекает частицы из предыдущего взвешенного набора частиц и применяет обновления движения и показаний датчиков перед помещением частицы в её ячейку. Алгоритм отслеживает количество незаполненных ячеек. Если частица помещается в ранее пустую ячейку, значение пересчитывается, что в основном увеличивается линейно. Это повторяется до тех пор, пока размер выборки не станет равным . Легко видеть, что KLD-sampling отсекает избыточные частицы из набора частиц, увеличивая только тогда, когда заполнена новая ячейка (позиция). На практике KLD-sampling стабильно превосходит и сходится быстрее, чем классическая MCL.