Subgraph-preconditioned Conjugate Gradients for Large Scale SLAM

Frank Dellaert, Justin David Carlson, Viorela Ila, Kai Ni, and Chuck Thorpe
2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010), November, 2010.


Download
  • Adobe portable document format (pdf) (1MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
In this paper we propose an efficient preconditioned conjugate gradients (PCG) approach to solving large scale SLAM problems. While direct methods, popular in the literature, exhibit quadratic convergence and can be quite efficient for sparse problems, they typically require a lot of storage as well as efficient elimination orderings to be found. In contrast, iterative optimization methods only require access to the gradient and have a small memory footprint, but can suffer from poor convergence. Our new method, subgraph preconditioning, is obtained by re-interpreting the method of conjugate gradients in terms of the graphical model representation of the SLAM problem. The main idea is to combine the advantages of direct and iterative methods, by identifying a sub-problem that can be easily solved using direct methods, and solving for the remaining part using PCG. The easy sub-problems correspond to a spanning tree, a planar subgraph, or any other substructure that can be efficiently solved. As such, our approach provides new insights into the performance of state of the art iterative SLAM methods based on re-parameterized stochastic gradient descent. The efficiency of our new algorithm is illustrated on large datasets, both simulated and real.

Notes
Number of pages: 6

Text Reference
Frank Dellaert, Justin David Carlson, Viorela Ila, Kai Ni, and Chuck Thorpe, "Subgraph-preconditioned Conjugate Gradients for Large Scale SLAM," 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010), November, 2010.

BibTeX Reference
@inproceedings{Dellaert_2010_6753,
   author = "Frank Dellaert and Justin David Carlson and Viorela Ila and Kai Ni and Chuck Thorpe",
   title = "Subgraph-preconditioned Conjugate Gradients for Large Scale SLAM",
   booktitle = "2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2010)",
   month = "November",
   year = "2010",
}