FastSLAM
FastSlam — один из подходов решения задач SLAM (англ. Simultaneous Localization And Mapping). В основе алгоритма лежит так называемый фильтр частиц и применение Байесовской сети. В FastSLAM одна большая карта рассматривается как совокупность локальных подкарт, что позволяет убрать зависимость ориентиров друг от друга и таким образом значительно сократить время пересчета оценки состояния системы[1]. Метод был разработан в 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.
Недостатки[править | править код]
Потенциальное падение точности, связанное с игнорированием корреляции ошибок оценки положений ориентиров[2].
Примечания[править | править код]
- ↑ Алгоритмы локальной навигации и картографии для бортовой системы управления автономного мобильного робота. CyberLeninka. Дата обращения: 23 марта 2016. Архивировано 3 апреля 2016 года.
- ↑ Montemerlo M., Thrun S., Koller D., Wegbreit B. Fastslam: A factored solution to the simultaneous localization and mapping problem. (англ.). — С. 6. Архивировано 19 апреля 2016 года.