SLAM algorithms (Simultaneous Localization and Mapping)

Positioning and mapping of a robot

  The positioning of a robot in its environment is an important issue in the field of mobile robotics in order to allow the autonomous navigation of the robot and the taking of geolocalized measurements. In constrained environments, the use of absolute positioning systems (beacons, GPS...) is impossible. Only relative positioning methods are possible, but they generally produce a drift in positioning due to the accumulation of small errors as the robot investigates. For this purpose, algorithms based on different sensors allow robots to map their environments while locating themselves in the established map.

Simultaneous localization and mapping

SLAM (simultaneous localization and mapping) algorithms are the subject of much research because they offer many advantages in terms of functionality and robustness. However, they depend on a multitude of factors that make them difficult to implement and must therefore be specific to the system to be designed. The implementation of such an algorithm must take into account the characteristics of the system model, the noise acting on it, the accuracy of the desired results, the speed of execution and the memory demand.

Innovation for our sensors-robots

At INNOWTECH, we are developing an algorithm of this type to make our robots autonomous and allow the localization of measurements made in hostile environments.

Two methods

An in-depth research allows us to identify two main principles. The first is based on the matching of point clouds which does not require any odometry information. This method is based on the analysis of segments constructed by acquiring a multitude of points with a LIDAR (LIght Detection And Ranging) mounted on a mobile robot at a given height. The result of the detection operation is therefore a set of points expressed in polar coordinates to be transcribed into a set of segments. As the method does not use odometry information, it relies exclusively on the geometry of the scans and the detection of « geometric landmarks » on which the matching process is based. The method can work correctly provided that the scans have an overlap containing at least one geometric landmark that is common to all scans.

  The second consists in merging odometry sensor data (encoders, inertial control unit or other ...) for the reconstruction of the robot's trajectory in an absolute reference frame using the various existing trajectory reconstruction methods, then repositioning the LIDAR data on this trajectory to produce the map.

Trajectory reconstruction methods

  Among the existing trajectory reconstruction methods are the Kalman filter and its derivatives as well as the particle filter. These methods differ in terms of the assumptions and principles on which they are based as well as in terms of accuracy, speed and memory demand. In the table below, we compare four recognized methods used in robotics :

The choice of such a method is based on the nature of the system’s evolution model, the level of knowledge of the nature of the noise affecting the system, the volume of data processed, the desired processing speed as well as the accuracy of the positioning information provided by the SLAM algorithm, taking into account the inverse proportionality between all these characteristics.