The Concept of Slam (simultaneous Localization and Mapping)

SLAM is an algorithm which simultaneously localize the robot and create the map of the environment. Basic steps involved in a SLAM problem:

• Given an unknown environment and robot pose
• Move through the environment
• Estimate robot pose
• Generate a map of environmental features
• Use the 3D map to identify the target

Change the robot's state in order to reach the target

Simultaneous localization and mapping (SLAM) is the process by which a mobile robot can construct a map of an unknown environment and simultaneously compute its location using the map . SLAM has been formulated and solved as a theoretical problem in many different forms. It has been implemented in several domains from indoor to outdoor, and the possibility of combining robotic in surgery issues has captured the attention of the medical community. The common point is that the accuracy of the navigation affects the success and the results of a task, independently from application field. Since its beginning, the SLAM problem has been developed and optimized in different ways. There are three main algorithms : Kalman filters (KF), particle filters and graph-based SLAM. The first two are also referred as filtering techniques, where the position and map estimates are augmented and refined by incorporating new measurements when they become available. Due to their incremental nature, these approaches are generally acknowledged as on-line SLAM techniques. Conversely, graph-based SLAM estimates the entire trajectory and the map from the full set of measurements and it is called full SLAM problem.

KF techniques

Smith et al. were the first to present the idea of representing the structure of the navigation area in a discrete-time state-space framework, introducing the concept of stochastic map. As KF original algorithm relies on the assumption of linearity, that is rarely fulfilled, two variations are mainly employed from then: extended KF (EKF) and information filtering (IF). The EKF overcomes the linearity assumption describing the next state probability and the measurement probabilities by nonlinear functions.

The unscented KF (UKF) has been developed in recent years to overcome some main problems of the EKF. It approximates the state distribution with a Gaussian Random Variable, like in EKF, but here it is represented using a minimal set of carefully chosen sample points, called σ-points. When propagated through the nonlinear system, they capture the posterior mean and covariance accurately to the 3rd order of the Taylor series for any nonlinearity. The dual of the KF is the information filter, that relies on the same assumptions but the key difference arises in the way the Gaussian belief is represented. The estimated covariance and estimated state are replaced by the information matrix and information vector respectively. It brings to several advantages over the KF: the data is filtered by simply summing the information matrices and vector, providing more accurate estimates; the information filter tends to be numerically more stable in many applications. The KF is more advantageous in the prediction step because the update step is additive while UKF involves the inversion of two matrices, which means an increase of computational complexity with a high-dimension state space. Anyway, these roles are reversed in the measurement step, illustrating the dual character of Kalman and information filters.

A variant of the EIF, that consists in an approximation which maintains a sparse representation of environmental dependencies to achieve a constant time updating. They were inspired by other works on SLAM filters that represent relative distances but none of them are able to perform a constant time updating. To overcome the difficulties of both EKF and IF, and to be more efficient in terms of computational complexity, a combined kalman-information filter SLAM algorithm (CF-SLAM) has been developed. It is a combination of EKF and EIF that allows to execute highly efficient SLAM in large environments.

Particle filters techniques

Particle filters comprise a large family of sequential Monte Carlo algorithms, the posterior is represented by a set of random state samples, called particles. Almost any probabilistic robot model that presents a Markov chain formulation can be suitable for their application. Their accuracy increases with the available computational resource, so it doesn’t require a fixed computation time. They are also relatively easy to implement: they do not need to linearize non-linear models and do not worry about closed-form solutions of the conditional probability as in KF. The poor performance in higher dimensional spaces is their main limitation. The need of increasing the consistency of estimation, together with the problem of heterogeneity of the trajectory samples, brought to the adoption of different sampling strategies.

iii.FastSLAMdenotes a family of algorithms that integrates particle filters and EKF. It exploits the fact that the features estimates are conditional independent given the observations, the controls, and the robot path. This implies that the mapping problem can be split into separate problems, one for each feature in the map, considering that also the single map errors are independent. FastSLAM uses particle filters for estimating the robot path and, for each particle, uses the EKF for estimating feature locations, offering computational advantages over plain EKF implementations and well coping with non-linear robot motion models. However, the particle approximation doesn’t converge uniformly in time due to the presence of the map in the state space, which is a static parameter.

Expectation maximization (EM) technique and improvement with missing or hidden data

The EM is an efficient iterative procedure to compute parameter estimation in probabilistic models with missing or hidden data. Each iteration consists of two processes: the expectation, or E-step, estimating the missing data given the current model and the observed data; the M-step, which computes parameters maximizing the expected log-likelihood found on the E-step. The estimate of the missing data from the E-step are used in place of the actual missing data. The algorithm guarantees the convergence to a local maximum of the objective function.

Since it requires the whole data being available at each iteration. an online version has been implemented, where there is no need to store the data since they are used sequentially. This algorithm has been used also to relax the assumption that the environment in many SLAM problems is static. Most of the existing methods are robust for mapping environments that are static, structured, and limited in size, while mapping unstructured, dynamic, or large-scale environments remains an open research problem. In literature, there are mainly two directions: partitioning the model into two maps, one holding only the static landmarks and the other holding the dynamic landmarks or trying to track moving objects while mapping the static landmarks.

Graph-based SLAM techniques

Graph-based SLAM addresses the SLAM problem adopting a graphical formulation, which means building a graph whose nodes represent robot poses or landmarks, linked by soft constraints established by sensor measurements this phase is called front-end. The back-end consists in correcting the robot poses with the goal of getting a consistent map of the environment given the constraints. The critical point concerns the configuration of the nodes: to be maximally consistent with the measurements, a large error minimization problem should be solved. GraphSLAMreduces the dimensionality of the optimization problem through a variable elimination technique. The nonlinear constraints are linearized and the resulting least squares problem is solved using standard optimization techniques.

Visual SLAM

A distinct paragraph has been dedicated to visual SLAM, since the optical sensors are always more employed in robotics applications and specifically in medical surgery. Most vision-based systems in SLAM problems are monocular and stereo, although those based on trinocular configurations also exist. Monocular cameras are quite widely used but the types of camera are various. Large-scale direct monocular SLAM uses only RGB images from a monocular camera as information about the environment and sequentially builds topological map. Omnidirectional cameras are gaining popularity: they have a 360° view of the environment and given that the features stay longer in the field of view, it is easier to find and track them. To improve the accuracy of the features, some works rely on a multi-sensor system. Depth estimates, scale propagation problems or can lead to failure modes due to non-observability. Stereo systems are hugely adopted in different environments, for both landmark detection and motion estimation in indoorand outdoor environments.

Most of the visual SLAM systems make use of algorithms from the computer vision, in particular the Structure from Motion (SfM). Nowadays, thanks to high performance computers, techniques such as bundle adjustment are producing a great interest in the robotics community, considering that their sparse representations can enhance performance over the EKF.