SLAM — Simultaneous Localization And Mapping — Метод одновременной навигации и построения карты — метод, используемый роботами и автономными транспортными средствами для построения карты в неизвестном пространстве или для обновления карты в заранее известном пространстве с одновременным контролем текущего местоположения и пройденного пути.

Метод одновременной навигации и построения карты (SLAM) — это концепция, которая связывает два независимых процесса в непрерывный цикл последовательных вычислений, при котором результаты одного процесса участвуют в вычислениях другого процесса.

Построение карты — это проблема интеграции информации, собранной с датчиков робота. При этом процессе, робот как бы отвечает на вопрос: «Как выглядит мир?»
Главными аспектами в построении карты являются представление данных об окружающей среде и интерпретация данных датчиков.
Напротив, локализация — это проблема определения местоположения робота на карте. При этом, робот как бы отвечает на вопрос «Где я?»
Локализацию можно разделить на два вида — локальная и глобальная.
Локальная локализация позволяет отследить местоположение робота на карте, когда его начальное местоположение известно, а глобальной локализация — это определение местоположения робота на незнакомом месте (например, при похищении робота).

Т.о. метод одновременной навигации и построения карты (SLAM) — это проблема построения карты и локализации робота на этой карте. На практике, эти две проблемы не могут быть решены независимо друг от друга. Прежде чем робот сможет ответить на вопрос о том, как выглядит окружающая среда (исходя из серии наблюдений), он должен знать, где эти наблюдения были сделаны. В то же время, трудно оценить текущее положение робота без карты.
Вот и выходит, что SLAM является типичной проблемой курицы и яйца: карта необходима для локализации, а локализация необходима для создания карты.

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

В рамках ROS, реализовано несколько алгоритмов SLAM:

GMapping — реализация метода SLAM на основе данных от лазерного дальномера и одометрии робота (подробности на OpenSLAM.org).

Но вместо лазерного дальномера вполне можно использовать и Kinect.
Это уже реализовано и используется на роботе TurtleBot — SLAM Map Building with TurtleBot:

http://www.youtube.com/watch?v=fljcaI4MDfA

Testing ROS with the gmapping package

VSLAM — Visual SLAM — визуальный SLAM — реализация метода SLAM на основе методов компьтерного зрения

стек vslam — экспериментальная попытка реализации визуального SLAM-а.
Визуальный SLAM — направление очень интересное и перспективное, но так как метод основывается на отслеживании ключевых точек (features, keypoints) на изображении, поступающем с камер робота, то когда камера движется быстро (например, при поворотах робота), возникает размытие изображения и возможности для отслеживания ключевых точек теряются и алгоритм перестаёт работать.

презентация VSLAM (PDF)

rgbdslam — пакет, для регистрации облака точек с RGBD датчиков, таких как Kinect или стерео-камеры.

Nikolas Engelhard and Felix Endres and Jürgen Hess and Jürgen Sturm and Wolfram Burgard, «Real-time 3D visual SLAM with a hand-held RGB-D camera», 2011. (PDF)

hector_mapping — SLAM для платформ без одометрии — только на основе данных от LIDAR-ов. Использует высокую скорость обновления современных систем лазерного сканирования, например, Hokuyo UTM-30LX и обеспечивает данные оценки 2D-положения со скоростью сканирования датчиков (40Гц для UTM-30LX).

karto — SLAM на основе одометрии робота и данных лазерного дальномера.

находятся в процессе разработки:
ScaViSLAM — фреймворк для визуального SLAM-а

H. Strasdat, A.J. Davison, J.M.M. Montiel, and K. Konolige, Double Window Optimisation for Constant Time Visual SLAM Accepted for the IEEE International Conference on Computer Vision (ICCV), 2011. (PDF)

mrpt_slam — оболочка для использования методов SLAM из библиотек MRPT (Mobile Robot Programming Toolkit)

Примеры использования SLAM

Робот-пылесос Neato XV-11
Реализация SLAM у социального робота Qbo

Ссылки
http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping
http://openslam.org
MRPT: SLAM algorithms