Simultaneous Localization and Mapping

SLAM je zkratka z anglikého simultaneous localization and mapping neboli konkurentní lokalizace a mapování. Již umíme sledovat pozici robota v rámci známé mapy. Pokud známe přesnou absolutní pozici robota (například z GPS) je možné mapu sestavit poměrně jednoduše. Problém ovšem je, pokud nemáme ani mapu ani přesnou informaci o pozici. Dnes si ukážeme několik algorimů, které tento problém řeší.

Základní myšlenky

Postupné skládání sbíraných dat

while (true)
{
	predict new position from odometry ;
	correct the position by aligning new sensor data with current map ;
	merge the data into the map ;
}

Vyrovnání polygonu

Pokročilejší algoritmy

Metrické, featureless

A Real-Time Algorithm for Mobile Robot Mapping With Applications to Multi-Robot and 3D Mapping

We present an incremental method for concurrent mapping and localization for mobile robots equipped with 2D laser range finders. The approach uses a fast implementation of scan-matching for mapping, paired with a sample-based probabilistic method for localization. Compact 3D maps are generated using a multi-resolution approach adopted from the computer graphics literature, fed by data from a dual laser system. Our approach build 3D maps of large, cyclic environments in real-time. It is remarkably robust. Experimental results illustrate that accurate maps of large, cyclic environments can be generated even in the absence of any odometric data.

FastSLAM: A Factored Solution to the Simultaneous Localization and Mapping Problem

Michael Montemerlo, Sebastian Thrun, Daphne Koller, Ben Wegbreit, AAAI 2002

An Efficient FastSLAM Algorithm for Generating Maps of Large-scale Cyclic Environments From Raw Laser Range Measurements.

Haehnel D., Burgard W., Fox D., and Thrun S., IROS-03, 2003

FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges.

M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. IROS 2003

Topologické, grafové, featurefull

Learning Globally Consistent Maps by Relaxation

Mobile robots require the ability to build their own maps to operate in unknown environments. A fundamental problem is that odometry-based dead reckoning cannot be used to assign accurate global position information to a map because of drift errors caused by wheel slippage. This paper introduces a fast, on-line method of learning globally consistent maps, using only local metric information. The approach differs from previous work in that it is computationally cheap, easy to implement and is guaranteed to find a globally optimal solution. Experiments are presented in which large, complex environments were successfully mapped by a real robot, and quantitative performance measures are used to assess the quality of the maps obtained.

A Genetic Algorithm for Simultaneous Localization and Mapping

This paper addresses the problem of simultaneous localization and mapping (SLAM) by a mobile robot. The SLAM problem is defined as a global optimization problem in which the objective is to search the space of possible robot maps. A genetic algorithm is described for solving this problem, in which a population of candidate solutions is progressively refined in order to find a globally optimal solution. The fitness values in the genetic algorithm are obtained with a heuristic function that measures the consistency and compactness of the candidate maps. The results show that the maps obtained are very accurate, though the approach is computationally expensive. Directions for future research are also discussed.

Relaxation on a Mesh: a Formalism for Generalized Localization

This paper considers two problems which at first sight appear to be quite distinct: localizing a robot in an unknown environment and calibrating an embedded sensor network. We show that both of these can be formulated as special cases of a generalized localization problem. In the standard localization problem, the aim is to determine the pose of some object (usually a mobile robot) relative to a global coordinate system. In our generalized version, the aim is to determine the pose of all elements in a network (both fixed and mobile) relative to an arbitrary global coordinate system. We have developed a physically inspired ‘meshbased’ formalism for solving such problems. This paper outlines the formalism, and describes its application to the concrete tasks of multi-robot mapping and calibration of a distributed sensor network. The paper presents experimental results for both tasks obtained using a set of Pioneer mobile robots equipped with scanning laser range-finders.

Plánování cesty pro mobilní roboty (Diplomová práce, MFF UK, 2002)

V úvodu práce jsou analyzovány stávající řídící sytémy pro mobilní roboty. Na základě této analýzy je definována architektura G-BAGS — Graph-Based Adaptive Guidance System. Tato architektura definuje obecně využitelný princip pro navigaci mobilního robota založený na manipulaci s informacemi o relativních pozicích pozorovaných objektů. Na základě těchto informací je výpočetně nenáročným, inkrementálním algoritmem sestavena globálně konzistentní mapa prostředí, která je také přímo využívána plánovacími algoritmy. Mapa má tvar grafu a obsahuje jak metrické údaje o vzájemných pozicích prekážek, tak údaje o topologii prostoru. Dále je navržen způsob pro efektivní zavedení pojmu běžně používaných lidmi při zadávání úkolu typu donáška (místnost, chodba, patro) do vniřního řídícího systému robota za účelem dosažení intuitivnějšího a spolehlivějšího chování robota při plnění těchto úloh. Vyšší robustnosti systému je dosaženo zejména definicí cesty nejen jako geometrického útvaru (lomené čáry), ale také pomocí očekávaných orientačních bodů podél této cesty. Tato definice napomáhá průběžné kontrole úspěšnosti postupu po ceste i bez znalosti přesné pozice robota v absolutních souřadnicích. Výsledkem je ucelený návrh kompaktního systému postihující nutné dovednosti robota pro aplikaci typu donáška v administrativní budově.

Odkazy

• Simultaneous localization and mapping
• Simultaneous Localization and Mapping (SLAM): Part I
• Simultaneous Localization and Mapping (SLAM): Part II
• SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping)