A multilevel relaxation algorithm for simultaneous localization and mapping

By Udo Frese, Per Larsson, Tom Duckett. IEEE Transactions on robotics, 2005

420 citations recorded by the source corpus.

This paper addresses the problem of simultaneous localization and mapping (SLAM) by a mobile robot. An incremental SLAM algorithm is introduced that is derived from multigrid methods used for solving partial differential equations. The approach improves on the performance of previous relaxation methods for robot mapping, because it optimizes the map at multiple levels of resolution. The resulting algorithm has an update time that is linear in the number of estimated features for typical indoor environments, even when closing very large loops, and offers advantages in handling nonlinearities compared with other SLAM algorithms. Experimental comparisons with alternative algorithms using two well-known data sets and mapping results on a real robot are also presented.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/465a2d29d1c3b2a81e79b816d0ce25f5d6ad9bea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Electrical and Electronic Engineering

Citations in the corpus

Factor Graphs for Robot Perception (2017, neutral): “These then led to a flurry of work between 2000 and 2005 where these ideas were applied in the context of SLAM [56, 71, 70, 187].”
On behalf of: Multimedia Archives (2012, positive): “Frese et al. (2005) employed a multi-scale representation of the graph, a practice borrowed from the partial differential equation literature.”
AUV Navigation and Localization: A Review (2014, methodology): “Different solutions exist for GrpahSLAM, such as relaxation on a mesh [41], multilevel relaxation [42], iterative alignment [43], square root smoothing and mapping (SAM) [7], incremental smoothing and mapping (iSAM) [44] and works by Grisetti et al.”
Visual simultaneous localization and mapping: a survey (2012, positive): “However, it is necessary to perform a global optimization of the map to reduce local error (Frese et al. 2005; Olson et al. 2006).”
Efficient Sparse Pose Adjustment for 2D mapping (2010, background): “[9] propose a variant of Gauss-Seidel relaxation called multi-level relaxation (MLR).”
Exactly Sparse Delayed-State Filters for View-Based SLAM (2006, methodology): “Hence, the ESDF’s results could be even better if we implemented the iterative multilevel state recovery techniques of [51], [54].”
The three-dimensional normal-distributions transform : an efficient representation for registration, surface analysis, and loop detection (2009, methodology): “[33, 34] and the 3D relaxation methods of Grisetti et al.”
Fast iterative alignment of pose graphs with poor initial estimates (2006, methodology): “The robustness and speed of our approach make it compelling as a stand-alone SLAM algorithm, but it could also be used by other non-linear algorithms like GraphSLAM or MLR to improve their convergence on difficult problems by providing a better initial estimate.”
Robust map optimization using dynamic covariance scaling (2013, background): “Since then, many approaches for minimizing the error in the constraint network have been proposed, including relaxation methods [13], [3], stochastic gradient descent and its variants [2], [14], smoothing techniques [4] and hierarchical techniques [15], [1].”
iSAM2: Incremental smoothing and mapping using the Bayes tree (2012, background): “…to probabilistic inference in SLAM has a rich history (Brooks, 1985) and has especially led to several novel and exciting developments in the last years (Paskin, 2003; Folkesson and Christensen, 2004; Frese et al., 2005; Frese, 2006; Folkesson and Christensen, 2007; Ranganathan et al., 2007).”
The Graph SLAM Algorithm with Applications to Large-Scale Mapping of Urban Structures (2006, background): “Frese, Larsson, and Duckett (2005) analyzed the efficiency of SLAM in the information form, and developed highly efficient optimization techniques using multi-grid optimization techniques.”
iSAM: Incremental Smoothing and Mapping (2008, methodology): “A number of improved and numerically more stable algorithms have since been developed, based on well-known iterative techniques such as relaxation [10], [35], [36], gradient descent [37], [38], conjugate gradient [39], and, more recently, multilevel relaxation [40], [41].”
Square Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing (2006, background): “Over the last five years in particular there has been a flurry of work in which these ideas were applied in the context of SLAM (Deans and Hebert 2000; Duckett et al. 2000, 2002; Howard et al. 2001; Frese and Duckett 2003; Frese et al. 2005; Folkesson and Christensen 2004; Folkesson et al. 2005; Fre”