Development of the Ordering and Elimination Method in iSAM2 Algorithm and Implementation on a Mobile Robot
The simultaneous localization and mapping asks if it is possible for an autonomous robot to start in an unknown location in an unknown environment and then incrementally build a map of this environment while simultaneously using this map to compute absolute robot location. Finding the optimal and online solution, often called the maximum likelihood, is important and obtained by solving a sequence of least-squares minimization problems. In practice, the initial problem is nonlinear and it is usually addressed by repeatedly solving a sequence of linear systems. In an online SLAM application, updating and solving the nonlinear system in every step may become considerably expensive for large problems. While, iSAM2 is a completely novel approach to providing an efficient and exact solution to a sparse nonlinear optimization problem in an incremental setting. In this thesis, the above mentioned algorithm is studied and implemented in details and the efficiencies of different parts are evaluated. Many papers have indicated that variable elimination, instead of sparse matrix factorization, is the prevailing element in efficiency of this algorithm. Besides, it has been emphasized that delicate variable reordering over the graph, prior to the factorization, is essential for the decrease of implementation time. While herein it is illustrated that the most time-consuming part of this algorithm is to solve the linearized system at each iteration. Experiments demonstrate that reordering and elimination take merely 5.34 percent of implementation time. In addition, development of minimum-degree-based algorithms may not produce significant reduction in fill-in.