FastSLAM (FastSLAM)

FastSlam — один из подходов решения задач SLAM (англ. Simultaneous Localization And Mapping). В основе алгоритма лежит так называемый фильтр частиц и применение Байесовской сети. В FastSLAM одна большая карта рассматривается как совокупность локальных подкарт, что позволяет убрать зависимость ориентиров друг от друга и таким образом значительно сократить время пересчета оценки состояния системы. Метод был разработан в 2002 году студентами Карнеги — Меллона и Стэнфордского университетов.

Описание алгоритма

Предположим, что робот находится в одномерном пространстве, и его положение характеризуется одной переменной x.

Тогда p(x) — распределение вероятности x, имеющим гауссову форму.

Теперь, если x отражает положение робота и ориентиров в многомерном пространстве, то распределение вероятности p(x) будет определять вероятности всех возможных переменных состояния.

Таким образом,

p(x | {u0, u1, … ui}, {z0, z1, … zi}) (1) — распределение вероятности всех величин текущего состояния системы, полученных в момент времени i.

Для упрощения понимания введем обозначения, где

Ui = {u0, u1, … ui} (2) — вектор с показаниями датчиков

Zi = {z0, z1, … zi} (3) — вектор, описывающий информацию о перемещении робота

x в свою очередь включает в себя:

• положение робота v
• положения ориентиров p0, p1, … pm.

Поэтому p(x | Ui,Zi) можно представить в следующем виде:

p(x | Ui,Zi) = p(v, p0,p1,…pm | Ui,Zi). (4)

Воспользуемся основами теории вероятностей для упрощения задачи SLAM.

Предположим, есть две независимые случайные величины A и B. Можно сказать что p(A, B) = p(A) * p(B).

Но это выражение несправедливо для случая, когда A зависит от B. В этом случае оно будет иметь вид p(A, B) = p(A) * p(B|A).

Оценка положения ориентиров зависит от оценки положения робота, а это значит что p(v, p0,p1,…pm | Ui,Zi) можно представить в следующем виде:

p(v, p0,p1,…pm | Ui,Zi) = p(v | Ui,Zi) * p(p0,p1,…pm | Ui,Zi, v). (5)

В силу независимости наблюдений ориентиров друг от друга можно разде-

лить p(p0,p1,…pm | Ui,Zi, v) на m независимых выражений:

p(v | Ui,Zi) * p(p0,p1,…pm | Ui,Zi, v) = p(v | Ui,Zi) * p(p0 | Ui,Zi, v) * p(p1 | Ui,Zi, v) * … p(pm | Ui,Zi, v). (6)

В итоге, результирующее выражение для распределения вероятности имеет вид:

p(x | Ui,Zi) = p(v | Ui,Zi) * Πm p(pm | Ui,Zi, v). (7)

Преимущества алгоритма

В данном алгоритме проблема SLAM разделена на m+1 задач, и ни одна из оценок положения ориентира не зависит от других.

Относительно сложность алгоритма вычисления упрощается. Этот факт, в свою очередь, позволяет решить проблему полиномиальной сложности алгоритма на основе расширенного фильтра Калмана при решении задач SLAM и избежать ее в FastSLAM.

Недостатки

Потенциальное падение точности, связанное с игнорированием корреляции ошибок оценки положений ориентиров.