SLAM-алгоритм

SLAM (от англ. Simultaneous Localization and Mapping — одновременная локализация и построение карты) — это вычислительная задача в области робототехники и компьютерного зрения, заключающаяся в построении карты неизвестного окружения и одновременном определении местоположения подвижного объекта (робота, беспилотного автомобиля, дрона) относительно этой карты. Отличительной особенностью SLAM является отсутствие априорной информации о среде: алгоритм использует только данные с бортовых сенсоров (лазерные дальномеры, камеры, одометры) и последовательно уточняет как карту, так и положение объекта.

История

Задача SLAM была сформулирована в конце 1980-х годов в работах Рэндольфа Смита, Пола Чиза и Питера Чизмана. Они предложили математическую основу для одновременной оценки положения и карты с помощью теории вероятностей. Первые эксперименты проводились на мобильных роботах, оснащенных ультразвуковыми датчиками.

В 1990-е годы были разработаны фильтровальные подходы (расширенный фильтр Калмана, фильтр частиц), которые позволили решать задачу в реальном времени для ограниченных пространств. Значительный прорыв произошел в 2000-е годы с появлением методов на основе графов (GraphSLAM), которые повысили точность и масштабируемость.

С середины 2010-х годов активно развивается визуальный SLAM (visual SLAM), использующий монокулярные, стереоскопические и RGB-D камеры. Это связано с удешевлением камер и ростом производительности встраиваемых процессоров. Сегодня SLAM является одной из базовых технологий в автономной навигации роботов и дополненной реальности.

Математическая постановка

В общем виде задача SLAM сводится к оцениванию совместной апостериорной вероятности:

• Траектории движения объекта \( X_{0:t} = \{x_0, x_1, \dots, x_t\} \),
• Карты окружающей среды \( M = \{m_1, m_2, \dots, m_n\} \)

при известных управляющих воздействиях \( U_{1:t} \) и наблюдениях \( Z_{1:t} \):

\[ P(X_{0:t}, M | Z_{1:t}, U_{1:t}). \]

Решение этой задачи осложняется тем, что ошибки в определении положения накапливаются и вносят неопределенность в карту, а неточности карты — в локализацию. SLAM решает эту проблему циклических зависимостей через итеративное уточнение.

Основные подходы

Фильтровальные методы

• Расширенный фильтр Калмана (EKF-SLAM) — один из первых практических методов. Каждое состояние (положение робота + координаты ориентиров) представляется гауссовским распределением. Недостаток — высокая вычислительная сложность \(O(k^2)\), где \(k\) — число ориентиров.
• Фильтр частиц (FastSLAM) — использует набор взвешенных частиц для аппроксимации распределения. Каждая частица содержит свою карту. Позволяет работать с нелинейными моделями и большим числом ориентиров.

Метод графов (GraphSLAM)

Положение робота в каждый момент времени и координаты точек карты рассматриваются как узлы графа. Ребра графа задают пространственные ограничения между узлами (например, измерения расстояний, смещения из одометрии). Задача сводится к оптимизации графа — минимизации суммы ошибок всех ограничений. Этот подход обеспечивает глобальную ковариацию и применяется в современных SLAM-системах (например, Google Cartographer, ORB-SLAM).

Классификация по сенсорам

Лазерный SLAM (Lidar SLAM)

Использует данные с лазерных дальномеров (Lidar). Позволяет получать точные облака точек на расстояниях до десятков метров. Основное применение — мобильные роботы на складах, беспилотные автомобили. Примеры алгоритмов: Hector SLAM, Gmapping, Cartographer.

Визуальный SLAM (Visual SLAM)

Основан на обработке изображений с камеры (часто монокулярной или стереопары). Может работать без одометрии, но чувствителен к освещению и текстуре сцены. Основные алгоритмы: ORB-SLAM (2, 3), DSO (Direct Sparse Odometry), LSD-SLAM (Large-Scale Direct SLAM).

Визуально-инерциальный SLAM (Visual-Inertial SLAM)

Комбинирует камеру и инерциальный измерительный блок (IMU). IMU сглаживает рывки камеры и улучшает оценку движения в условиях низкой текстуры. Примеры: VINS-Mono, ORB-SLAM3 (поддерживает инерциальный режим).

Ультразвуковой и радарный SLAM

Используются реже — в основном в подводной или запыленной среде, где оптические методы неэффективны.

Основные алгоритмы и реализации

Применение

Робототехника

SLAM является ключевым компонентом для автономных мобильных роботов: складские погрузчики, роботы-пылесосы (например, Xiaomi, iRobot), сервисные роботы (в больницах, отелях). Позволяет роботу планировать маршруты и избегать препятствий без предварительной карты.

Беспилотные автомобили

В сочетании с GPS SLAM применяется для подземных паркингов, крытых парковок, тоннелей, где спутниковый сигнал недоступен. Лидарные алгоритмы обеспечивают сантиметровую точность.

Дополненная и виртуальная реальность

Системы AR (например, ARKit от Apple, ARCore от Google) используют визуальный SLAM для отслеживания положения устройства и привязки виртуальных объектов к реальному миру без маркеров.

Геодезия и строительство

SLAM-сканеры (например, Leica BLK2GO) позволяют быстро создавать трехмерные модели помещений и территорий без установки специальных реперных точек.

Военные и поисково-спасательные операции

Дроны и наземные роботы с SLAM способны строить карты зданий, завалов и пещер в условиях, где нет связи со спутниковой навигацией.

Проблемы и ограничения

• Замыкание циклов (loop closure) — важнейшая стадия, позволяющая исправить накопленную ошибку при возврате в ранее посещенное место. Если не выполнить детекцию цикла, карта может «разъезжаться».
• Динамическая среда — движущиеся объекты (люди, другие роботы) вызывают ошибки в SLAM. Современные алгоритмы используют маски движущихся объектов или фильтрацию выбросов.
• Масштабируемость — при больших картах (более ~10⁶ точек) время оптимизации графа может стать критическим.
• Вычислительная сложность — для работы на мобильных платформах требуются эффективные реализации и аппаратное ускорение (GPU, FPGA).

Интересные факты

• SLAM-алгоритмы часто сравнивают с «проблемой курицы и яйца»: без карты невозможно точно локализоваться, без точной локализации — построить карту. Решение основано на итеративном уточнении.
• Первое успешное применение SLAM на реальном роботе в замкнутом пространстве было продемонстрировано в 1995 году (проект «Rhino» в Университете Бонна).
• В 2019 году команда Нанкинского университета разработала SLAM-систему, работающую на основе только одной камеры и способную строить карты с точностью до сантиметров на расстояниях до 200 метров.
• В России система SLAM используется, в частности, в роботах-уборщиках «Копир» и в автономных тележках для доставки грузов на промышленных предприятиях.

Будущее развитие

Ожидается переход к семантическому SLAM, где строится карта с пониманием типов объектов (стены, двери, столы). Такая карта может использоваться не только для навигации, но и для интеллектуального взаимодействия с окружением. Внедрение глубокого обучения в детекцию циклов и оценку глубины (monocular depth estimation) позволит улучшить SLAM в сложных условиях. Развитие SLAM на основе событийных камер (event cameras) обещает субмиллисекундную реакцию и работу в сценах с быстрыми движениями.

Источники

• Smith, R., Self, M., & Cheeseman, P. (1990). Estimating uncertain spatial relationships in robotics.
• Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics.
• Mur-Artal, R., & Tardós, J. D. (2017). ORB-SLAM2: an Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras.
• Engel, J., Koltun, V., & Cremers, D. (2017). Direct Sparse Odometry.
• Материалы Технического комитета по робототехнике IEEE — раздел SLAM.
• Документация ROS (Robot Operating System) по пакетам gmapping, hector_slam, cartographer.