Что такое система slam
Система навигации и построения карт vSLAM
В современных роботах-пылесосах используются новейшие технологии, позволяющие строить и прокладывать наиболее оптимальный маршрут во время уборки. С этой целью используется метод одновременной навигации и построения карты, известный как SLAM (Simultaneous Localization And Mapping). Часто встречается обозначение VSLAM, где символ V означает «визуальный». Данный метод помогает выстроить карту в совершенно незнакомом пространстве или обновить уже существующий маршрут. Одновременно контролируется текущее положение пылесоса и его пройденный путь.
История развития интеллекта роботов
У самых первых роботов-пылесосов отсутствовала картография, режимы движения vslam, поэтому их перемещение по квартире было беспорядочным и хаотичным. В наиболее продвинутых моделях к этому режиму добавлялось движение по спирали и вдоль стен. В дальнейшем, навигация несколько улучшилась и стала способна оценивать примерную квадратуру по некоторым явным признакам. В основном, использовалось количество ударов при столкновении робота с препятствиями. Если это происходило слишком часто, значит у этого помещения небольшие размеры.
Позднее умные пылесосы были оборудованы дополнительным приспособлением – маячком-координатором, закрывающим устройство в ограниченном пространстве на определенное время. Эти маяки устанавливались в дверных проемах и запирали агрегат в той или иной комнате на заданное время. Таким образом, зоны и режим уборки распределялись равномерно, однако, оставалась проблема пропусков мест, остающихся неубранными.
Через некоторое время система навигации устройств дополнилась камерой. В результате, пылесос охватывал все доступные площади и не оставлял загрязненных мест. Одновременно, он запоминал место, где находится база для зарядки. Постепенно модели роботов еще более совершенствовались и значительно «поумнели» с появлением слэма – метода SLAM.
Что такое SLAM
Метод SLAM состоит из двух независимых процессов, одновременно включающих в себя навигацию и построение карты маршрута. Во время его действия выполняются последовательные вычисления, проводимые в непрерывном цикле. Полученные результаты оказываются взаимосвязаны, уточняя и дополняя друг друга.
Отвечая на вопрос, что такое slam следует отметить, что для построения карты требуется сбор информации, поступающей от датчиков, ее последующая интеграция и обработка. По итогам анализа полученных данных, составляется представление об окружающем пространстве.
В то же самое время выполняется локализация, определяющая расположение пылесоса на полученной карте. Условно она разделяется на два типа – локальную и глобальную. В первом случае положение робота известно заранее, а во втором – локализация осуществляется для незнакомого места. Последний вариант, помимо основной задачи, дает возможность найти похищенный пылесос.
Таким образом, метод SLAM заключается в одновременном построении карты и локализации объекта на этой карте. Эти задачи решаются в комплексе не могут выполняться вне зависимости между собой. То есть, карта нужна для локализации, а локализация требуется для того, чтобы создать карту. Определенные трудности в этом процессе создает относительно низкая точность приборов, принимающих участие в вычислениях.
Построение карт SLAM
Карты помещений строятся двумя методами – камерами (рис. 1) и лазерным дальномером (рис. 2). В первом варианте используется навигация vslam – выполняется фотографирование поверхностей и дверных проемов. Полученные данные сохраняются в памяти устройства и применяются в дальнейшей работе.
Некоторые модели для обработки информации пользуются технологией NST, которая делает сравнение фотографий, полученных с камеры. Эти данные необходимы в дальнейшем для корректировки маршрута. Таким образом, камерная технология обеспечивает более качественное построение карт помещений, сокращает количество ошибок и захватывает большие площади для уборки.
Второй метод – лазерный был впервые использован американской компанией Neato. В каждой модели был установлен лазерный дальномер, расположенный в специальной башенке сверху корпуса. Основная задача данного устройства заключается в измерениях расстояний от пылесоса до предметов, встречающихся на его пути.
Карты SLAM в роботах-пылесосах
Современные пылесосы оборудованы обеими технологиями – камерной и лазерной. Наиболее популярными моделями считаются следующие:
SLAM – принципы и ссылки на open source
Что такое SLAM?
SLAM – акроним для Simultaneous Location and Mapping
Эта заметка – небольшая памятка на тему что такое SLAM. Здесь описаны основные принципы наиболее популярных методов SLAM (EKF, iSam, TORO и др). В отдельном разделе интересующиеся могут найти ссылки на свободные(!) реализации различных методов SLAM в виде готовых библиотек. А также перечислены блоги и проекты посвященные задаче SLAM. Если вы ищите готовую реализацию SLAM – собрал->запустил->получил карту => листайте к последнему разделу.
Одним из важнейших компонентов систем компьютерного зрения, связанных с ориентацией в пространстве (такие как Kintinious и ей подобные) является SLAM-модуль. Именно он выполняет глобальную оптимизацию полученных измерений. Фактически, основная задача SLAM – минимизации ошибок определения сдвига камеры – за счет этого выравнивается траектория движения робота (камеры) и обозреваемое пространство, на основе которого формируется карта мира.
Представьте себе робота, оснащенного некоторым набором сенсоров (например обычной и дальномерной камерой) находящегося в некоторой неизвестной среде – например лабиринте Минотавра. Робот не обладает информацией об окружающем его пространстве равно как и своем положением в нем. Все что у него есть – показания сенсоров и возможность сохранять информацию о предыдущих измерениях. Его задача – слоняясь по лабиринту построить полную карту, дабы будущие Тесеи не теряли времени зазря в поисках супостата. На практике это означает что робот ищет ответы на вопросы “Где я?!” и “Как выглядит мир вокруг?!”.
В каждый момент времени в мозг робота передаются показания с сенсоров. С помощью методов визуальной одометрии или на основе анализа дальномерных данных – робот может определять свое смещение относительно предыдущего положения. В идеальном случае – когда его вычисления точны и безукоризнены – по одним этим данным возможно воссоздать карту местности, где он уже побывал и полностью описать траекторию его движения. В печальной реальности – на каждом шаге возникает небольшая погрешность вычислений (ошибка замеров/помехи/ограничения, накладываемые алгоритмами и т.п.). С течением времени общая, аккумулятивная ошибка продолжает нарастать таким образом, что не смотря на приемлимую точность определения локального смещения – общая глобальная карта положений робота будет полна искажений. И вот тут-то на помощь роботу и приходят методы Simultaneous Localization And Mapping или просто SLAM.
SLAM – это не какой-то определенный алгоритм или набор ПО – это концепция, общая методология для решения двух задач:
1) построение карты исследованного пространства
2) построение траектории движения робота на карте.
Надо отметить что полностью данная задача по прежнему не решена и до сих пор ведутся ожесточенные исследования.
Первый принципиальный момент – SLAM не предполагает каких-либо знаний о среде – ни меток на местности/ни предварительной карты нет – все решения строятся только на результатах измерений датчиков (обычно это rgb- и дальномерная камеры, но, бывает, и дополнительное оборудование навроде гироскопа-IMU/gps-датчика и т.д.).
Второй не менее принципиальный момент – среда считается статичной. Это значит, что если робот проехал мимо фикуса, никто за его спиной этот же самый фикус двигать не станет. В кадре – в обозреваемом сенсорами пространстве – никакого постороннего движения нету – флюгера не крутятся, никто в кадре не прогуливается. Освещение радикально не изменяется – т.е. тени по стенам не скачут. Такие условия сложно гарантировать в естественной среде – приятно шелестящая листва или любопытная кошка запросто может дезориентировать робота в пространстве (ну, не то чтобы прям запросто – и отсекать динамическую часть можно, и делать поправку на нее). Однако, если пофантазировать на тему марсоходов – то даже в настоящем виде методы SLAM могут найти свое применение. В частности, робот-пылесос – яркий пример применения данной методики в 2D-пространстве. Существуют экспериментальные реализации данной задачи в 3D (квадроптер шныряющий по коридорам и беспилотный батискаф).
SLAM – карта мира и траектория движения робота в нем
В общем случае SLAM можно описать как повторяющая последовательность шагов:
1) сканирование окружающего пространства
2) определение смещение на основе сравнения текущего кадра с предыдущим
3) выделение на текущем кадре особенностей-меток
4) сопоставление меток текущего кадра с метками полученными за всю историю наблюдений
5.1) обновление на основе этой информации положение робота за всю историю наблюдений
5.2) проверка на петли – не проходим ли мы повторно по одной и той же местности
5.3) выравнивание общей карты мира (отталкиваясь от положения меток и робота за всю историю наблюдений)
На каждом шаге алгоритма мы располагаем предположениями о структуре мира (у нас есть карта) и историей движения робота в нем (траектория движения относительно карты с разбивкой по времени).
Представленные реализации разделяются на две большие группы – SLAM frontend и SLAM backend.
Задача SLAM-fronted‘а сводится к оценке пространственных отношений между особенностями сцены и позами робота с некоторым значением вероятности. SLAM-fronted – набор методов для преобразования полученных данных от сенсоров к унифицированному представлению (структуре специального вида – см. далее) подаваемому на вход непосредственно SLAM-ядру. В настоящее время, для этих целей используются графы специального вида (варьируются от взвешенного, основанного на результатах измерений, до динамической сети Байеса, вовсю отталкивающейся от вероятностной модели положения робота в мире). Данный компонент специфичен для робота (какие там у него сенсоры, как организовано преобразование входной информации и т.п.), а потому какой-то универсальной библиотеки, реализующей весь функционал я не встречал. Хотя список поддерживаемых сенсоров того же ROS – robot operaring systems впечатляет. Принципы выбора особенностей на каждом кадре здесь описаны не будут – интересующимся гуглить по SIFT, SURF, NARF, FAST и т.д.
SLAM-backend – SLAM-ядро – непосредственная реализация решения задачи SLAM – оптимизация полученных от фронтенда пространственных отношений с целью максимизации вероятности. Данная задача абстрагированна от того, каким образом получены входные данные – главное, чтобы формат представления (граф, сеть, матрица, список и т.д.) информации о среде и положении робота в нем совпадали. Например, в каких-то случаях необходима высокая точность и не принципиально время вычислений, в других случаях критичен быстрый результат. Если мы храним все наши перемещения и замеры в виде специального графа то мы в первом случае скормим этот граф на оптимизацию iSam’у, а во втором отдадим TORO’у.
SLAM в деталях
Задачу SLAM можно подразбить на несколько связных частей:
SLAM frontend:
1) Анализ и интеграция новых данных (data association). На этом этапе производится выделение особенностей (Feature/landmarks extraction) на вновь полученных данных (на основе RGB-информации, карты глубины, их комбинации, показаний дополнительных датчиков – гироскопа, GPS-приемника и др.) Особенности – это такие характеристики, которые легко могут быть выделены в среде и использоваться в дальнейшем для ориентации в пространстве. Желательно чтобы их можно было распознать под разным “углом зрения” с точки зрения используемых сенсоров. Критично чтобы они были стационарны. Желательно чтобы их можно было различать друг от друга – для того чтобы понять – не встречали ли мы их ранее. Самый простой пример особенностей – геометрические – углы, прямые.
2) Вычисление сдвига (Local Motion Estimation). На основе сопоставления нового набора особенностей с особенностями, полученными на предыдущем шаге можно определить как изменилось их расположение на сцене. Так как особенности сами по себе стационарны – очевидно что этот сдвиг – результат изменения положения камеры (робота). На основе этой информации можно выразить координаты камеры через систему линейных уравнений для решения которой используются различные методы и их комбинации (ICP, visual odometry – FOVIS, RGB-D, etc).
3) Обновление структуры (Features Integration) хранящей историю перемещений, где каждое состояние представляет собой глобальное положение робота и взаимо-расположение обозреваемых особенностей на определенном промежутке времени. В последнее время кроме непосредственно данных о положении, хранятся также и вероятностные оценки для каждого значения. На данном этапе производится анализ и добавление полученных ранее данных в общую структуру для хранения информации о мире за все время исследования. Как правило, данные добавляются не на каждом шаге а при условии, что позиции робота(камеры) существенно изменилась – например, сдвиг или поворот по сравнению с предыдущей запомненной позицией составил более некоего граничного значения.
SLAM backend:
1) Сравнение данных локального сдвига и особенностей
Теперь у нас с одной стороны есть результаты локального сдвига, на основе которого мы можем вычислить новое положение робота. С другой стороны – мы так же можем определить позицию робота относительно особенностей сцены. В силу погрешностей сенсоров и используемых алгоритмов данные позиции не будут совпадать между собой (и, скорее всего, также и с реальным местоположением робота). Полученная разница должна быть отражена во всех предыдущих замерах особенностей как корректирующий коэффициент – вероятность.
2) Обновление общего представления о карте мира и траектории робота (Global Optimisation)
На основе вновь полученных данных производится уточнение текущих представлений о мире – пересчет позиций робота (state estimation), особенностей и их вероятностей. Дополнительно производится поиск замыканий (loop closure – ситуаций, когда робот возвращается в те места где уже побывал). После всех вычислений обновляется общее представление мира – позы робота (state update) и координаты особенностей (landmark update).
На основе глобальной структуры, хранящей все перемещения робота и представление мира в любой момент времени возможно воссоздать карту миру с траекторией движения робота. Для визуализации (Reconstructing world map) используются сторонние средства к методам SLAM особого отношения не имеющие.
Методы SLAM
Популярнейшим методом для решения был EKM – Extended Kalman Filter.
На каждом шаге у нас есть набор ранее полученных особенностей (landmark) и только что поступившие данные (дальномерные и RGB). На основании новых и предыдущих кадров мы можем определить смещение робота (используя методы визуальной одометрии) и предсказать новую позицию робота. С другой стороны, из нового кадра, мы можем выделить местоположение особенностей и вычислить положение робота относительно их. На основе разницы между двумя этими оценками позиций робота обновляются вероятности/веса для всех особенностей и корректируются позы-траектория движения робота. Детальное описание – по ссылкам ниже. В качестве структуры для хранения информации о мире и траектории движения робота – используется разрастающаяся со временем матрица ковариации, содержащая на каждом шаге исчерпывающую информацию о нашем текущем представлении мира. В случае большего числа поз – лучше подойдет particle filter, видео – отличный пример из курса ai-class от Sebastian Thrun.
Loop closure – обнаружение петлей. Обособлено от задач SLAM стоит вопрос как отслеживать ситуации когда робот возвращается туда, где уже побывал (в литературе это называется loop closure – замыкание, петля). Одно из решений – так называемая корзина “слов” (англ. Bags of Binary Words). Каждому кадру ставится в соответствие дескриптор (BRIEF descriptor), вычисляемый на основе визуальных особенностей изображения. Для хранения информации о изображениях, на основе данных для обучения, формируется словарь в виде дерева, содержащий “слова” для представления дескрипторов и их веса (отражающих насколько часто они встречались в наборе изображений для обучения). Для формирования “слова” производится поиск визуальных особенностей на основе данных для тренинга и их последующая группировка (с помощью метода k-среднего). Каждый последующий уровень дерева получается путем повторения данной операции с дескриптором родительского узла. В результате, при анализе ново-поступивших данных производится быстрое (см дистанция Хэмминга) разложение идентификатора текущего кадра в линейную комбинацию узлов дерева, где в роли коэффициентов выступают их веса – вероятности.
Как уже упоминалось выше, в настоящее время наиболее популярно представление проблемы SLAM в виде графа, где вершины и ребра представляют позицию робота и месторасположение особенностей сцены. iSam – одна из открытых реализаций, построенная по этому принципу. В iSam используется двудольный граф состоящий из узлов-поз, содержащих результаты вычислений координат робота и узлов-факторов, содержащих результаты оценок визуальной одометрии, отражающей сдвиг между двумя последовательными позами. Дополнительно используется множество узлов-особенностей, содержащей вычисленные координаты особенностей представленных на сцене. Узлы-позы и узлы-особенности не могут быть связаны друг с другом напрямую, а только через узлы-факторы. В качестве расширения могут быть использованы узлы-якоря – особенности наблюдаемые разными роботами (одновременно) или особенности которые видит один и тот же робот в течении нескольких независимых путешествий. Ядро системы производит оптимизацию данного графа выравнивая все узлы на основе новых данных. Возможна работа и без особенностей и без узлов-якорей – только на основе результатов визуальной одометрии.
В настоящее время наиболее быстрые результаты дает TORO (ценою точности вычисления).
Данный метод определяет конфигурация графа при которой вероятность наблюдаемых особенностей будет максимальна. Подходов к решению подобных задач – видимо не видимо (гуглить по “Sparse Bundle Adjustments”, “Structure from motion”, “Visual SLAM”), в основу TORO лег метод стохастического градиентного спуска – (SGD – stochastic gradient descent). Суть данного метода в последовательной оптимизации всего графа для каждого ограничения (взаимного расположения особенностей и робота). Для объединения данных оптимизации с нескольких ограничений используются специальные коэффициенты для корректировки значений остатка. Ключевое достижение данного метода – представление данных для SGD – в TORO используется дерево параметров в качестве индексов для линейного уравнения поз робота.
Хочу попробовать поиграться со SLAM – есть ли что-нибудь готовое?
Если вкратце – нет я не встречал. Свободно доступны различные реализации отдельных компонентов из которых при остром желании (и навыке) можно самостоятельно собрать готовые системы.
Желающим попытать счастья настоятельно рекомендую ознакомиться:
Возможный результат можно посмотреть тут.
Еще есть интересная библиотека Phovo. Скачать ее можно оттуда – http://code.google.com/p/photoconsistency-visual-odometry/. В своем составе, кроме всего прочего имеет приложения использующее SLAM-реализацию из mrpt, и реализованные автором алгоритмы визуальной одометрии (на основе http://vision.in.tum.de/_media/spezial/bib/steinbruecker_sturm_cremers_iccv11.pdf)
Из минусов – солидный список зависимостей, не все из которых собираются простым make install (одна unstable версия PCL чего стоит – внимательнее смотрите в cmake, какие компоненты вам действительно нужны).
Также учтите что для того чтобы завести NVidea toolkit под линуксом – придется немного попотеть: как установить cuda toolkit под ubuntu – http://sn0v.wordpress.com/2012/05/11/installing-cuda-on-ubuntu-12-04/
Ссылки на реализацию SLAM и связанных с ними компонент
DBow: Hierarchical bag-of-word library for C++ – описание
последняя версия DBoW – http://webdiis.unizar.es/
Еще одна из вариаций SLAM-backend (на этапе оптимизации позволяет изменять структуру графа, ускоряя процес оптимизации)
http://www.tu-chemnitz.de/etit/proaut/forschung/robustSLAM.html.en
Список api связанных со SLAM имплементированных в библиотеке MRPT – Mobile Robot Programming Toolkit:
http://www.mrpt.org/List_of_SLAM_algorithms
UPDATE от 11.01.2012
Наткнулся в запасниках еще на некоторые материалы. Добавляю.
Вопрос новичка – что такое SLAM – и развернутые ответы “для начинающих”:
http://www.mrpt.org/node/441
Описание свеженькой (от 2012 года) книжки про SLAM
Оглавление интересное.
http://www.mrpt.org/SLAM_book_2012
Karto – коммерческая версия SLAM (есть триалка и опенсурсный вариант с последним коммитом от 2010 года)
в описании проскальзывали утверждения о том что работает лучше чем iSam
http://www.kartorobotics.com
http://www.willowgarage.com/blog/2010/04/19/karto-mapping-now-open-source-and-coderosorg
Описание еще одного метода loop closing:
http://jochen.sprickerhof.de/software/elch/
по ссылке на странице можно зайти на сайт опенсурсного продукта – The 3D Toolkit – в котором кроме SLAM есть средства для просмотра облака точек, определения поверхностей и т.п.
update 03102013
Презентация с roboconf.ru:
“SLAM – путеводные крошки в мире людей” SLAM – Intro with algo and libs
зы уточнения/поправки рьяно приветствуются
2 pings
[…] (recognition) объектов, 3d-реконструкция и навигация (SLAM и loop-closure). Используя характерные точки можно […]
SLAM (метод)
Из Википедии — свободной энциклопедии
SLAM (англ. simultaneous localization and mapping — одновременная локализация и построение карты) — метод, используемый в мобильных автономных средствах для построения карты в неизвестном пространстве или для обновления карты в заранее известном пространстве с одновременным контролем текущего местоположения и пройденного пути. Популярные методы приближённого решения данной задачи — фильтр частиц и расширенный фильтр Калмана. Некоторые реализации метода используются в беспилотных автомобилях, летательных аппаратах, автономных подводных аппаратах, планетоходах, и даже внутри человеческого тела.
Насущность проблемы связана с тем, что карты, обычно используемые для навигации агентов, в основном отражают вид пространства, зафиксированный в момент их построения, и совсем не обязательно, что вид пространства будет тем же в момент использования карт. При этом сложность технического процесса определения текущего местоположения с одновременным построением точной карты обусловлена низкой точностью приборов, участвующих в процессе вычисления текущего местоположения. Метод одновременной навигации и построения карты увязывает два независимых процесса в непрерывный цикл последовательных вычислений, при этом результаты одного процесса участвуют в вычислениях другого процесса.
Основные подходы, используемые для реализации задачи — EKF-SLAM, FastSLAM, DP-SLAM. При относительно больших исследуемых площадях применяются многоагентные системы (такой подход был применён при исследовании картографии Марса группой роботов-марсоходов и соединении исследуемых карт в одну).
SLAM, VSLAM, LDS: разбираемся, какой тип навигации для робота-пылесоса лучше?
SLAM, VSLAM, LDS: разбираемся, какой тип навигации для робота-пылесоса лучше?
PROJECT OVERVIEW
Практически все интернет ресурсы, бесчисленное множество обзоров и статей сообщат вам, что тип навигации – важнейший фактор, на который первоочередно стоит обратить свое внимание, приобретая робот-пылесос. Запутаться в этой тематике просто, ведь рынок ежегодно расширяется, пополняясь усовершенствованными девайсами. Спешим на помощь и подробно разбираем три самых популярных типа навигации, существующих на сегодняшний день.
SLAM-навигация
Несколько лет назад такой тип навигации считался наиболее «продвинутым», сейчас же практически все премиальные модели ориентируются в пространстве с помощью камеры или лидара. Несмотря на это, модели, оснащенные SLAM-навигацией, все еще выпускаются и активно продаются.
Почему SLAM-навигация остается популярной при существовании двух других более совершенных типов?
Как работает SLAM-навигация?
SLAM-навигация позволяет девайсу строить карту в незнакомом месте и проецировать ее повторно на уже известной территории. В начале работы прибор запоминает точку старта и обрисовывает в своей памяти проложенный путь, что позволяет ему не повторяться и оперативно справляться с поставленной задачей. Сведения об окружающей среде робот-пылесос получает благодаря инфракрасным сенсорам, обычно установленным на бампере устройства. Современные роботы-пылесосы дают возможность просматривать карту помещения в приложении на мобильных гаджетах.
Яркий представитель: Panda Evo
VSLAM + камера
Доработанная версия навигационной системы, описанной пунктом ранее. Оснащение девайсов камерой позволяет за считанные секунды анализировать пространство, запоминая расположение предметов по территории и используя потолок для ориентирования. Такой формат выстраивает более точный план очистки помещения, который можно просмотреть в мобильном приложении. Отличие от первого типа: пользователь может взаимодействовать с картой. Приложение открывает доступ к выстраиванию виртуальных стен и обозначению конкретных мест для локальной очистки.
Яркий представитель: Okami U90
Лазерная навигация на базе лидара
Переходим к самому совершенному типу навигации, фигурирующему практически во всех премиальных моделях роботов-пылесосов. Лидар – конструкция в виде башенки, установленная на корпусе устройства и оснащенная высокоточным лазером. Именно он собирает информацию из внешней среды о предметах и расстояниях до них.
Лидар позволяет наиболее точным и быстрым образом анализировать пространство. Вдобавок процесс сканирования теперь возможен даже при темном освещении, что несвойственно для навигации на базе камеры.
Яркий представитель: Okami U100
Что же лучше?
Однозначный ответ на данный вопрос отсутствует. Все три типа навигации обладают своими достоинствами и правильно соотносятся со стоимостью устройства. Конечно, самыми прорывными и технологичными являются модели, оснащенные лидаром. Они способны убирать габаритные помещения, функционировать ночью и быстрее всех справляться с обязанностями.
Однако и более бюджетные модели эффективно приберут вашу жилплощадь. При выборе устройства опирайтесь на метраж помещения, особенности планировки и доступный вам бюджет. Современный рынок предлагает сотню вариантов, среди них обязательно найдется нужный робот-пылесос.