Simultaneous Localization and Mapping

from Wikipedia, the free encyclopedia

As SLAM ( English Simultaneous Localization and Mapping ; German  Simultaneous Position Determination and Map Creation ) is a robotics process in which a mobile robot must simultaneously create a map of its surroundings and estimate its spatial position within this map. It is used to recognize obstacles and thus supports autonomous navigation .

Task

One of the fundamental problems of a mobile robot is to orient itself, i.e. to know what its environment looks like and where it is (absolutely). For this purpose, the robot is equipped with various sensors, such as ultrasound , cameras or lidar , with the help of which its surroundings are recorded in three dimensions. This enables a robot to move locally, to recognize obstacles in good time and to avoid them. In addition, if the absolute position of the robot is known, e.g. B. from additional GPS sensors, a map can be built. The robot measures the position of possible obstacles relative to it and can then use its known position to determine the absolute position of the obstacles, which are then entered on the map.

The challenge at SLAM

The exploration of an unknown environment and the orientation in this is done intuitively by us humans. Via our sensory organs: eyes, skin, ears and nose, we receive information in the form of stimuli from our immediate environment. This information is combined in our brain and processed to determine the position and characterize our surroundings. Consciously or unconsciously, we recognize distinctive features that we link to a spatial relationship in order to obtain an abstract idea of ​​a site plan, which can be used to navigate, depending on the task and destination.

Similar to humans, this should also be achieved with mobile systems. Without any prior knowledge, conclusions can be drawn about the position and orientation from the data from sensors that are integrated in a mobile system unit with simultaneous mapping of the environment using simple three-dimensional points or more complex constructs. The process of creating a map is referred to as mapping and the recognition of the position of a mobile system unit as self-localization .

A major challenge of such systems is that a correspondingly detailed map is required for an exact position determination and that the exact position of the mobile system unit must be known in order to generate a detailed map. From this it becomes clear that these two requirements, mapping and self-localization, cannot be solved independently of each other. SLAM is therefore a chicken and egg problem , as neither the map nor the position is known, but rather these should be estimated at the same time.

application

For many locations where mobile robots are used, there are no maps and also no possibility of determining the absolute position, e.g. B. via GPS . Without SLAM, a card would have to be created before deployment, which can delay deployment and make it more expensive. Therefore, depending on the area of ​​application, it is important that a robot is able to autonomously explore a new environment and create a map that it can then use later for navigation.

The SLAM method is an active research area within robotics and computer vision , which is being worked on by numerous research groups worldwide. For example, the Mars landing vehicles of NASA's Mars Exploration Rover " Spirit " and " Opportunity " mission are operated with such methods.

approaches

There are many different approaches, with some fundamental similarities. Since a robot can normally only see part of the environment, the map is built up incrementally : initially there is no map and the position of the robot defines the origin of its coordinate system. This means that the absolute position of the robot is trivially known and the first measurement of the environment can be entered directly on the map. Then the robot moves and measures its surroundings again. If the robot has not moved too far, it will again measure part of the already known environment, but also a previously unknown area for the first time. The movement of the robot can be calculated from the overlap of the new measurement with the previous map, so that the absolute position is known again and the new measurement can therefore also be integrated into the map. In this procedure, the map is expanded incrementally until the entire area has been surveyed.

Since the determination of the robot's movement between two measurements is never exact, the calculated position of the robot will continue to deviate from the real one, which will also reduce the quality of the map. In order for the map to remain consistent, the algorithm must be able to recognize when an already known part of the environment is measured again ( loop closing ).

SLAM procedure

Solving SLAM implies solving the data association problem, i. This means that it must be determined which (environmental) features correspond. This problem is particularly difficult because features cannot be extracted with absolute certainty. Scan matching processes do not require any features, as they take entire scans or point clouds into account and then use graph-based techniques.

literature

  • Andreas Nüchter: 3D Robotic Mapping . Springer-Verlag GmbH, Berlin 2009, ISBN 978-3-540-89883-2 (Springer Tracts in Advanced Robotics).
  • Cyrill Stachniss: Robotic Mapping and Exploration . Springer-Verlag GmbH, Berlin 2009, ISBN 978-3-642-01096-5 (Springer Tracts in Advanced Robotics).
  • Sebastian Thrun , Wolfram Burgard , Dieter Fox: Probabilistic Robotics . The Mit Press, 2005, ISBN 978-0-262-20162-9 .
  • Michael Montemerlo, Sebastian Thrun : FastSLAM: A Scalable Method for the Simultaneous Localization and Mapping Problem in Robotics . Springer Verlag, 2007, ISBN 3-540-46399-2 .
  • Austin Eliazar, Ronald Parr: DP-SLAM: Fast, Robust Simultainous Localization and Mapping Without Predetermined Landmarks . 2003.
  • F. Lu, E. Milios: Globally consistent range scan alignment for environment mapping . In: Autonomous Robots . 1997.
  • Dorit Borrmann, Jan Elseberg, Kai Lingemann, Andreas Nüchter, Joachim Hertzberg .: Globally consistent 3D mapping with scan matching . In: Journal of Robotics and Autonomous Systems (JRAS) . Elsevier Science, 2008 ( PDF ).
  • Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard: Improved Techniques for Grid Mapping with Rao-Blackwellized Particle Filters . In: IEEE Transactions on Robotics . 2007 ( PDF ).
  • Giorgio Grisetti, Cyrill Stachniss, Wolfram Burgard: Non-linear Constraint Network Optimization for Efficient Map Learning . In: IEEE Transactions on Intelligent Transportation Systems . 2009 ( PDF ).
  • Udo Frese, Per Larsson, Tom Duckett: A Multilevel Relaxation Algorithm for Simultaneous Localization and Mapping . In: IEEE Transactions on Robotics . 2005.
  • Frank Dellaert: Square Root SAM (Smoothing and Mapping) . In: Robotics: Science and Systems . 2005.

Web links