Grid-based Submap Joining: An Efficient Algorithm for Simultaneously Optimizing Global Occupancy Map and Local Submap Frames
Organizations: Robotics Institute, Faculty of Engineering and Information Technology, University of Technology Sydney, Australia · School of Informatics, University of Edinburgh, Edinburgh, UK
Abstract
Optimizing robot poses and the map simultaneously has been shown to provide more accurate SLAM results. However, for non-feature based SLAM approaches, directly optimizing all the robot poses and the whole map will greatly increase the computational cost, making SLAM problems difficult to solve in large-scale environments. To solve the 2D non-feature based SLAM problem in large-scale environments more accurately and efficiently, we propose the grid-based submap joining method. Specifically, we first formulate the 2D grid-based submap joining problem as a non-linear least squares (NLLS) form to optimize the global occupancy map and local submap frames simultaneously. We then prove that in solving the NLLS problem using Gauss-Newton (GN) method, the increments of the poses in each iteration are independent of the occupancy values of the global occupancy map. Based on this property, we propose a poseonly GN algorithm equivalent to full GN method to solve the NLLS problem. The proposed submap joining algorithm is very efficient due to the independent property and the pose-only solution. Evaluations using simulations and publicly available practical 2D laser datasets confirm the outperformance of our proposed method compared to the state-of-the-art methods in terms of efficiency and accuracy, as well as the ability to solve the grid-based SLAM problem in very large-scale environments.
Figures & tables
| Dataset | No. Scans | Duration (s) | Map Size (m) | Odometry |
|---|---|---|---|---|
| Simulation 1 | 3640 | 117 | yes | |
| Simulation 2 | 2680 | 83 | yes | |
| Car Park [ 24 ] | 1642 | 164 | yes | |
| C5 [ 14 ] | 3870 | 136 | yes | |
| Museum b0 1G [ 11 ] | 5522 | 152 | no | |
| Museum b2 [ 11 ] | 51833 | 1390 | no |
| Odom | Carto | Toolbox | Occupancy-SLAM* | Ours | |
|---|---|---|---|---|---|
| Simulation 1 | |||||
| MAE (Trans/m) | 0.7827 | 0.2534 | 0.1465 | 0.0238 | 0.0453 |
| MAE (Rot/rad) | 0.0491 | 0.0139 | 0.0134 | 0.0008 | 0.0012 |
| RMSE (Trans/m) | 0.9840 | 0.2992 | 0.1788 | 0.0263 | 0.0609 |
| RMSE (Rot/rad) | 0.0551 | 0.0156 | 0.0152 | 0.0009 | 0.0015 |
| Simulation 2 |
| AUC | Precision | ||
|---|---|---|---|
| Simulation 1 | Cartographer | 0.9088 | 0.9565 |
| SLAM Toolbox | 0.9550 | 0.9749 | |
| Occupancy-SLAM | 0.9997 | 0.9973 | |
| Ours | 0.9751 | 0.9867 | |
| Simulation 2 | Cartographer | 0.9270 | 0.9660 |
| SLAM Toolbox | 0.9726 | 0.9871 |
| Dataset | Carto | Occupancy-SLAM | Ours | ||
|---|---|---|---|---|---|
| Submap | Joining | Total | |||
| Car Park | 168 | 17138 | 133 | 0.8 | 133.8 |
| Museum b0 1G | 152 | 26901 | 113 | 0.6 | 113.6 |
| C5 | 146 | 27452 | 157 | 0.6 | 157.6 |
| Museum b2 | 1424 | - | 1248 | 2.4 | 1250.4 |
| Museum b0 EG | 615 | - | 539 | 1.7 | 540.7 |
| Dataset | Ours | Full GN | Acceleration Rate |
|---|---|---|---|
| Car Park | 0.062 | 0.174 | 281% |
| Museum b0 1G | 0.044 | 0.098 | 223% |
| C5 | 0.036 | 0.058 | 161% |
| Museum b0 EG | 0.157 | 0.419 | 267% |
| Museum b2 | 0.226 | 0.378 | 167% |
| C3 | 0.096 | 0.174 | 181% |
Simultaneous Localization and Mapping
Simultaneous localization and mapping estimates a robot’s motion while building a map of an unknown environment.
See all 210 papers