FastSLAM. 
Обзор современного состояния области компьютерного зрения

В 2002 году Montemerlo, Trun, Koller, и Wegbreit разработали новый подход к решению задачи SLAM. FastSLAM разделяет задачу локализации и картографии на множество подзадач, используя независимость состояния отдельных элементов модели SLAM [22, 49].

Также этот алгоритм можно встретить под названием Particle Filter SLAM, т.к. он использует в своей основе алгоритм Rao-Blackwellized Particle Filter.

Рисунок 14 иллюстрирует проблему SLAM как Байесовскую сеть Байесовская сеть (Bayesian network, belief network) — графическая вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Формально — это направленный ациклический граф, каждой вершине которого соответствует случайная переменная, а дуги графа кодируют отношения условной независимости между этими переменными. :

Рисунок 14 — The SLAM problem as Bayes Network [48, 49].

По отношению к EKF SLAM данный алгоритм имеет над ним два значительных преимущества [49]:

1. Эффективность и быстродействие:

«…by factoring the estimation of the map into in separate landmark estimators conditioned on the robot path posterior, FastSLAM is able to compute the full SLAM posterior in an extremely efficiently manner. The motion update, the landmark updates, and the computation of the importance weights can all be accomplished in constant time per particle. The resampling step, if implemented naively, can be implemented in linear time».

2. Снятие ограничения на количество ориентиров:

«…However, this step can be implemented in logarithmic time by organizing each particle as a binary trees of landmark estimators, instead of an array. The log (N) FastSLAM algorithm can be used to build a map with over a million landmarks using a standard desktop computer».

Робот перемещается из состояния в через ряд управляющих воздействий. В процессе движения робот наблюдает ближайшие ориентиры (landmarks) и (the positions of the landmarks are conditionally independent [49]). Измерения обозначены как. В разные моменты времени он может наблюдать одну из двух ключевых точек (прим.: в том числе и повторно).

«The SLAM problem is concerned with estimating the locations of the landmarks and the robot’s path from the controls and the measurements. The gray shading illustrates a conditional independence relation» [48].

По сути, FastSLAM представляет собой реализацию Rao-Blackwellized Particle Filter (RBPF) [49, 52]. Точки окружения в данной задачи являются частицами для фильтра RBPF.

При каждом обновлении будет построено новое распределение частиц с учетом модели движения робота. Для частиц, у которых прогнозируемое фильтром RBPF значение совпадает (с определённой погрешностью) со значениями, измеренными на сенсорах, будут даны большие весовые коэффициенты. Повторный выбор частиц с созданием нового распределения основывается на весовых коэффициентах предыдущей выборки. Оценки ориентиров представлены 2×2 EKF (т.е., по сути fastSLAM базируется на EFK), но каждая частица в некоторой мере независима от других. Т. е., вместо определения относительного положения всех частиц сцены друг от друга, используется определение положения каждой частицы (из числа частиц M) относительно некоторого числа N определённых ориентиров.

Рисунок 15 показывает, как частицы (particles), обнаруженные методом будут привязаны к ориентирам (landmarks).

Рисунок 15 — There are M particles in the particle filter. Each particle contains N independent EKF’s. No explicit cross-correlations are maintained between the landmark estimates [49].

Рисунок 16 показывает разницу в использовании больших (16.а) и малых (16.b) полей восприятия.

Рисунок 16 — Maps and estimated robot path, generated using sensors with (a) large and (b) small perceptual fields. The correct landmark locations are shown as dots, and the estimates as ellipses, whose sizes correspond to the residual uncertainty [48].

Среди проблем данной реализации SLAM можно отметить, что на больших расстояниях от начала координат карты серьезно возрастают ошибки (технически, решением этой проблемы может быть разбитие карты на несколько подкарт). Работа [55] иллюстрирует решение задачи ориентации робота в средах, имеющих большой масштаб (outdoor navigation): «self-localization of mobile robots in large-scale environments can be efficiently realized if a hybrid representation of the environment is used. The probabilistic approach presented here matches an incremental generalization of the traveled route with an integrated topological metric map, the route graph».