Exploiting the intrinsic structures of simultaneous localization and mapping
- Publication Type:
- Thesis
- Issue Date:
- 2017
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
Imagine a robot which is assigned a complex task that requires it to navigate in an unknown environment. This situation frequently arises in a wide spectrum of applications; e.g., surgical robots used for diagnosis and treatment operate inside the body, domestic robots have to operate in people’s houses, and Mars rovers explore Mars. To navigate safely in such environments, the robot needs to constantly estimate its location and, simultaneously, create a consistent representation of the environment by, e.g., building a map. This problem is known as simultaneous localization and mapping (SLAM). Over the past three decades, SLAM has always been a central topic in mobile robotics. Tremendous progress has been made during these years in efficiently solving SLAM using a variety of sensors in large-scale environments. However, some of the intrinsic structures of SLAM are yet to be fully understood and utilized. This thesis is devoted to the study of some of these structures.
This thesis is comprised of two main parts:
In the first part, we examine the specific structure of the standard measurement models in pose-graph and feature-based SLAM. These standard models are affine with respect to the position of robot and landmarks. Consequently, given the orientation of the robot, the conditionally-optimal estimate for the robot’s and landmarks’ positions can be recovered instantly by solving a sparse linear least squares problem. We propose an algorithm to exploit this intrinsic property of SLAM, by stripping the problem down to its nonlinear core, while maintaining its natural sparsity. By taking advantage of the separable structure of SLAM, we gain a global perspective that guides the conventional local search algorithms towards a potential solution, and hence achieve a fast and stable convergence.
In the second part of this thesis, we investigate the impact of the graphical structure of SLAM and several other estimation-over-graph problems, on the estimation error covariance. We establish several connections between various graph-connectivity measures and estimation-theoretic concepts. For example, we prove that, under certain conditions, the determinant of the estimation error covariance matrix of the maximum likelihood estimator can be estimated by counting the weighted number of spanning trees in the corresponding graph, without solving the optimization problem or using any information about the “geometry” of the scene (e.g., numerical values of the measurements). This surprising result shows that the graphical structure of SLAM provides a compact, but rich representation of the underlying estimation problem, that can be used—e.g., in decision making and active SLAM—to predict and reason about the resulting estimation error covariance. Consequently, we tackle the combinatorial optimization problem of designing sparse graphs with the maximum weighted number of spanning trees. Characterising graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, we establish several new theoretical results, including the monotone log-submodularity of the weighted number of spanning trees in connected graphs. By exploiting these structures, we design a complementary pair of near-optimal efficient approximation algorithms with provable performance guarantees and near-optimality certificates. We discuss several applications of our results and apply our algorithms on the measurement selection problem in SLAM to design sparse near-D-optimal (determinant-optimal) SLAM problems.
Please use this identifier to cite or link to this item: