SLAM (метод)

SLAM (англ. simultaneous localization and mapping — одновременная локализация и построение карты) — метод, используемый в мобильных автономных средствах для построения карты в неизвестном пространстве или для обновления карты в заранее известном пространстве с одновременным контролем текущего местоположения и пройденного пути. Популярные методы приближённого решения данной задачи — фильтр частиц и расширенный фильтр Калмана. Некоторые реализации метода используются в беспилотных автомобилях, летательных аппаратах, автономных подводных аппаратах, планетоходах, и даже внутри человеческого тела.

Насущность проблемы связана с тем, что карты, обычно используемые для навигации агентов, в основном отражают вид пространства, зафиксированный в момент их построения, и совсем не обязательно, что вид пространства будет тем же в момент использования карт. При этом сложность технического процесса определения текущего местоположения с одновременным построением точной карты обусловлена низкой точностью приборов, участвующих в процессе вычисления текущего местоположения. Метод одновременной навигации и построения карты увязывает два независимых процесса в непрерывный цикл последовательных вычислений, при этом результаты одного процесса участвуют в вычислениях другого процесса.

Основные подходы, используемые для реализации задачи — EKF-SLAM, FastSLAM, DP-SLAM. При относительно больших исследуемых площадях применяются многоагентные системы (такой подход был применён при исследовании картографии Марса группой роботов-марсоходов и соединении исследуемых карт в одну).

Формальная постановка

Задача SLAM заключается в вычислении оценки местоположения $x_{t}$ агента и карты окружающей среды $m_{t}$ из ряда наблюдений $o_{t}$ над дискретным временем с шагом дискретизации $t$ . Все перечисленные величины являются вероятностными. Цель задачи состоит в том, чтобы вычислить $P(m_{t},x_{t}|o_{1:t})$ . Применение правила Байеса является основой для последовательного обновления апостериорного местоположения, учитывая карту и функцию перехода $P(x_{t}|x_{t-1})$ :

P(x_{t}|o_{1:t},m_{t})=\sum _{m_{t-1}}P(o_{t}|x_{t},m_{t})\sum _{x_{t-1}}P(x_{t}|x_{t-1})P(x_{t-1}|m_{t},o_{1:t-1})/Z

.

Точно так же карта может обновляться последовательно:

P(m_{t}|x_{t},o_{1:t})=\sum _{x_{t}}\sum _{m_{t}}P(m_{t}|x_{t},m_{t-1},o_{t})P(m_{t-1},x_{t}|o_{1:t-1},m_{t-1})

.

Как и во многих других проблемах логического вывода, оперируя двумя вероятностными переменными, можно прийти к локальному оптимальному решению, применяя EM-алгоритм.

Построение карты

Структурное представление карты местности зависит от среды функционирования.

Для выбора наилучшей реализации задач SLAM вводится условная классификация сред функционирования:

с многочисленными ярко выраженными ориентирами (например, поле с отдельно стоящими кустами)
с отсутствием ярко выраженных ориентиров (например, коридоры, комнаты, где в качестве ориентиров могут выступать углы)

Если в исследуемой среде нет возможности найти ориентиры, то её рационально представить в виде массива, где элементы, отражающие положение препятствий, имеют значение 1, а все остальные — 0. (Такое представление карты применяется, например, в алгоритме DP-SLAM)

В случае, когда в исследуемой местности есть многочисленные ориентиры, карта представляет собой массив оценок их местоположения. Размерность массива $R\cdot m$ , где $R$ — размерность пространства, $m$ — количество ориентиров.

Для хранения структуры такой карты проще всего использовать картографическую базу данных, которая отражает положение ориентиров, их уникальные свойства и взаимосвязи. Матрица оценок состояния динамической системы на основе расширенного Фильтра Кальмана использует именно этот вариант представления карты.

В качестве дальномеров используются лазерные дальномеры, гидролокаторы, стереосистемы. Для определения перемещения и поворотов робота могут использоваться одометры.

Ссылки

Cоставление 2D-карты методом SLAM по стерео изображению в режиме реального времени Архивная копия от 18 апреля 2016 на Wayback Machine
3d-картирование в виртуальной эндохирургии с использованием SLAM-алгоритма Архивная копия от 26 марта 2020 на Wayback Machine
DP-SLAM для участия в соревнованиях Eurobot Архивная копия от 13 февраля 2012 на Wayback Machine
[1]
курс лекций SLAM Архивная копия от 5 февраля 2021 на Wayback Machine