Grid-based Submap Joining: An Efficient Algorithm for Simultaneously Optimizing Global Occupancy Map and Local Submap Frames
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "Grid-based Submap Joining".
Dev: Here's the gist of the paper. Optimizing robot poses and the map simultaneously has been shown to provide more accurate SLAM results<ref:2501.12764#pg2> This paper proposes a grid-based submap joining method to solve the 2D non-feature based SLAM problem in large-scale environments more accurately and efficiently<ref:2501.12764#pg2> Problem Formulation The authors formulate the grid-based submap joining problem as a non-linear least squares (NLLS) form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X =
(Xr) T, M T: (3)<ref:2501.12764#pg4> The task of our submap joining problem is to find the optimal poses of local submap coordinate frames and the optimal global grid map<ref:2501.12764#pg4> Key Mathematical Formulation The NLLS problem is formulated as minimizing f(X) = X T (4)<ref:2501.12764#pg4> The objective function involves the difference between the occupancy values of the global occupancy map M and local submaps Li<ref:2501.12764#pg4> The weight ωimj is calculated by ωimj = NLi(pimj) NM(mj) (5)<ref:2501.12764#pg4> Pose-Only Optimization The authors prove that in solving the NLLS problem using GaussNewton (GN) method, the increments of the poses in each iteration are independent of the occupancy values of the global occupancy map<ref:2501.12764#pg3> Based on this property, they propose a pose-only GN algorithm which is equivalent to full GN method to solve the NLLS problem<ref:2501.12764#pg4> This approach is very efficient due to the independent property and the pose-only solution<ref:2501.12764#pg4> Experimental Validation Experiments 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<ref:2501.12764#pg2> The pose-only GN algorithm can easily and quickly obtain the solution of ∆r for each iteration because the dimension of the sparse linear system only depends on the number of poses<ref:2501.12764#pg5> The total time consumption for large-scale datasets is still faster than that of Cartographer on most datasets<ref:2501.12764#pg7> This paper is the first to simultaneously optimize the global occupancy map and local map coordinate frames for the gridbased submap joining problem<ref:2501.12764#pg8> The proposed method demonstrates superior performance in terms of speed and accuracy compared to state-of-the-art algorithms The high efficiency of the proposed map joining method is mainly due to the independent property of our formulation<ref:2501.12764#pg8> The pose-only GN method can be used to solve the NLLS problem efficiently The best number of local maps for map joining and the best way to partition the whole laser dataset require further investigation The authors also plan to extend their approach to 3D cases to perform large-scale 3D grid map based SLAM more accurately and efficiently Pruning redundant reasoning tokens The paper formulates the grid-based submap joining problem as a non-linear least squares problem to simultaneously optimize the global occupancy map and local submap frames, which is different from other submap joining approaches that only optimize poses by constructing a pose graph<ref:2501.12764#pg8> How the training signal is built The authors formulate the grid-based submap joining problem as a non-linear least squares (NLLS) form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X =
(Xr) T, MT: (3)<ref:2501.12764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501.12764#pg4> Where the gains come from The key gain stems from proving that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501.12764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501.12764#pg5> Pruning redundant reasoning tokens The authors formulate the grid-based submap joining problem as a non-linear least squares form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X =
(Xr) T, MT: (3)<ref:2501.12764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501.12764#pg4> How the training signal is built The NLLS problem is formulated as minimizing f(X) = X T (4)<ref:2501.12764#pg4> The objective function involves the difference between the occupancy values of the global occupancy map M and local submaps Li<ref:2501.12764#pg4> The weight ωimj is calculated by ωimj = NLi(pimj) NM(mj) (5)<ref:2501.12764#pg4> Pruning redundant reasoning tokens The authors prove that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501.12764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501.12764#pg5> How the training signal is built The authors formulate the grid-based submap joining problem as a non-linear least squares form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X =
(Xr) T, MT: (3)<ref:2501.12764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501.12764#pg4> Where the gains come from The key gain stems from proving that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501.12764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501.
Paper summary: Rosa: Thinking about this paper, "Grid-based Submap Joining: An Efficient Algorithm for Simultaneously Optimizing Global Occupancy Map and Local Submap Frames," it really captures the core idea of this work. It’s not just about fixing where the robot is; it’s about refining both its location and the underlying map structure at once eight.
Dev: Yeah, I mean that title really tells you what it’s trying to do—simultaneously optimizing those two things. The authors are tackling a problem where you usually have to pick one or the other in SLAM two.
Taro: What they're saying is this new grid-based approach allows for both of them to be optimized together, which they set up as a non-linear least squares problem four.
Rosa: They formulate it this way by defining a state vector that includes both the robot's poses and the global occupancy map itself, trying to find the best combination two.
Dev: And they get clever about how they do that optimization with Gauss-Newton methods; they proved something really neat about how fast those pose updates happen four.
Taro: The main point is this independence property—the updates for each robot pose don't actually depend on the occupancy values of the global map during the process three.
Rosa: That independence lets them propose a pose only Gauss-Newton algorithm, which they say is equivalent to the full method but much more efficient four.
Dev: That's a big deal for real-time control because it means faster iterations when you're running on tight loops and latency matters four.
Taro: It also gives them a closed-form formula for finding the final global map, which simplifies things for calculating the best overall map estimate five.
Rosa: So, to sum this up, this paper shows a way to get better pose estimates and a more accurate global map structure at once using this grid-based method eight.
Dev: It's definitely a step up in terms of efficiency and accuracy compared to the standard ways of doing submap joining two.
Taro: It’s an interesting piece because it shows how you can integrate map optimization directly into the localization loop itself for large-scale environments four.
Rosa: That opens up a lot of possibilities for how we build more robust SLAM systems out there in the field eight.
Conclusion: Rosa: So we're wrapping up on this paper about grid-based submap joining, which is all about figuring out how to optimize both your robot's location and the overall map at the same time.
Dev: Yeah, I mean that title really tells you what it’s trying to do—simultaneously optimizing those two things. The authors are tackling a problem where you usually have to pick one or the other in SLAM.
Taro: What they're saying is this new grid-based approach allows for both of them to be optimized together, which they set up as a non-linear least squares problem.
Rosa: They formulate it this way by defining a state vector that includes both the robot's poses and the global occupancy map itself, trying to find the best combination.
Dev: And they get clever about how they do that optimization with Gauss-Newton methods; they proved something really neat about how fast those pose updates happen.
Taro: The main point is this independence property—the updates for each robot pose don't actually depend on the occupancy values of the global map during the process.
Rosa: That independence lets them propose a pose only Gauss-Newton algorithm, which they say is equivalent to the full method but much more efficient.
Dev: That's a big deal for real-time control because it means faster iterations when you're running on tight loops and latency matters.
Taro: It also gives them a closed-form formula for finding the final global map, which simplifies things for calculating the best overall map estimate.
Rosa: So, to sum it up, this paper shows a way to get better pose estimates and a more accurate global map structure at once using this grid-based method.
Dev: It's definitely a step up in terms of efficiency and accuracy compared to the standard ways of doing submap joining.
Taro: It’s an interesting piece because it shows how you can integrate map optimization directly into the localization loop itself for large-scale environments.
Rosa: That opens up a lot of possibilities for how we build more robust SLAM systems out there in the field.
Dev: And if this approach scales well, it could mean we can handle much bigger and more complex mapping problems than before.
Yingyu Wang, Liang Zhao, Shoudong Huang
University of Technology Sydney · University of Edinburgh
cs.RO
Submitted: 2025-01-22
Updated: 2026-11-13
Comments: Accepted by IROS 2024, the code is made available
DOI: 10.1109/IROS58592.2024.10802536
Code: https://github.com/ceres-solver/ceres-solver
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 88/100
The gist: Optimizing robot poses and the map simultaneously has been shown to provide more accurate SLAM results<ref:2501.12764#pg2> This paper proposes a grid-based submap joining method to solve the 2D…
Key concepts
- Grid-based Submap Joining
- This method treats the problem as optimizing a grid structure where local maps fit together. Instead of just tracking robot positions, it simultaneously optimizes the entire global occupancy map and the relative positions (poses) of local submaps to create a consistent, high-quality representation of the environment.
- Non-linear Least Squares (NLLS)
- The optimization problem is mathematically defined as minimizing a function that measures the difference between what is observed in the global occupancy map and what is predicted by the collection of local submaps. This mathematical framework allows for simultaneous, coupled optimization of both robot poses and map details.
- Pose-Only Gauss-Newton (GN) Algorithm
- The authors proved that during iterative optimization using the Gauss-Newton method, the updates to robot poses do not depend on the specific occupancy values of the global map. This crucial property allows them to develop a simplified, efficient 'pose-only' algorithm that achieves full GN performance without needing complex map information in every step.
Terminology
Summary
Optimizing robot poses and the map simultaneously has been shown to provide more accurate SLAM results<ref:2501. p. 012764#pg2> This paper proposes a grid-based submap joining method to solve the 2D non-feature based SLAM problem in large-scale environments more accurately and efficiently<ref:2501. p. 012764#pg2>
Problem Formulation
The authors formulate the grid-based submap joining problem as a non-linear least squares (NLLS) form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X = [(Xr) T, M T] (3)<ref:2501. p. 112764#pg4> The task of our submap joining problem is to find the optimal poses of local submap coordinate frames and the optimal global grid map<ref:2501. p. 112764#pg4>
Key Mathematical Formulation
The NLLS problem is formulated as minimizing f(X) = X T (4)<ref:2501.12764#pg4> The objective function involves the difference between the occupancy values of the global occupancy map M and local submaps Li<ref:2501. p. 2 p. 212764#pg4> The weight ωimj is calculated by ωimj = NLi(pimj) NM(mj) (5)<ref:2501. p. 2 p. 212764#pg4>
Pose-Only Optimization
The authors prove that in solving the NLLS problem using GaussNewton (GN) method, the increments of the poses in each iteration are independent of the occupancy values of the global occupancy map<ref:2501.12764#pg3> Based on this property, they propose a pose-only GN algorithm which is equivalent to full GN method to solve the NLLS problem<ref:2501. p. 012764#pg4> This approach is very efficient due to the independent property and the pose-only solution<ref:2501. p. 012764#pg4>
Experimental Validation
Experiments 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<ref:2501.12764#pg2> The pose-only GN algorithm can easily and quickly obtain the solution of ∆r for each iteration because the dimension of the sparse linear system only depends on the number of poses<ref:2501. p. 312764#pg5> The total time consumption for large-scale datasets is still faster than that of Cartographer on most datasets<ref:2501. p. 512764#pg7>
Conclusion
This paper is the first to simultaneously optimize the global occupancy map and local map coordinate frames for the gridbased submap joining problem<ref:2501.12764#pg8> The proposed method demonstrates superior performance in terms of speed and accuracy compared to state-of-the-art algorithms The high efficiency of the proposed map joining method is mainly due to the independent property of our formulation<ref:2501. p. 112764#pg8> The pose-only GN method can be used to solve the NLLS problem efficiently The best number of local maps for map joining and the best way to partition the whole laser dataset require further investigation The authors also plan to extend their approach to 3D cases to perform large-scale 3D grid map based SLAM more accurately and efficiently
Pruning redundant reasoning tokens
The paper formulates the grid-based submap joining problem as a non-linear least squares problem to simultaneously optimize the global occupancy map and local submap frames, which is different from other submap joining approaches that only optimize poses by constructing a pose graph<ref:2501.12764#pg8>
How the training signal is built
The authors formulate the grid-based submap joining problem as a non-linear least squares (NLLS) form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X = [(Xr) T, MT] (3)<ref:2501. p. 1 p. 1 p. 112764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501. p. 2 p. 2 p. 212764#pg4>
Where the gains come from
The key gain stems from proving that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501. p. 0 p. 0 p. 012764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501. p. 3 p. 3 p. 312764#pg5>
The authors formulate the grid-based submap joining problem as a non-linear least squares form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X = [(Xr) T, MT] (3)<ref:2501.12764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501.12764#pg4>
The NLLS problem is formulated as minimizing f(X) = X T (4)<ref:2501.12764#pg4> The objective function involves the difference between the occupancy values of the global occupancy map M and local submaps Li<ref:2501.12764#pg4> The weight ωimj is calculated by ωimj = NLi(pimj) NM(mj) (5)<ref:2501.12764#pg4>
The authors prove that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501.12764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501.12764#pg5>
The authors formulate the grid-based submap joining problem as a non-linear least squares form to optimize the global occupancy map and local submap frames simultaneously<ref:2501.12764#pg2> The state vector of the proposed map joining problem is defined as X = [(Xr) T, MT] (3)<ref:2501.12764#pg4> By the global-to-local projection relationship, all cells of global occupancy map M can be projected to corresponding submaps to compute the difference in occupancy values to form the NLLS problem<ref:2501.12764#pg4>
The key gain stems from proving that when solving the formulated NLLS for both poses and the global map using GN method, the increment of poses in each iteration is independent of the occupancy values of the global occupancy map<ref:2501.12764#pg4> This independence allows them to propose a pose-only GN algorithm which is equivalent to full GN method<ref:2501.12764#pg4> The optimal solution of the global occupancy map Mˆ can be calculated by the closed-form formula Mˆ = V-1JM(X T r) (15)<ref:2501.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Pose-only Gauss-Newton algorithm implementation: The proposed pose-only GN method allows for solving a NLLS problem where both global map and local submap frames are optimized together, which is
very efficient due to the independent property
andmuch faster than the full GN method.
This enables high accuracy while overcoming the computational bottleneck of optimizing all robot poses and occupancy values simultaneously in large-scale environments. -
Closed-form formula for global occupancy map calculation: The existence of a closed-form formula for the optimal global occupancy map M hat, given the optimal poses X hat r, allows for its easy calculation via
M hat = V-1 J M H(X hat r),
which is significantly faster than iterating through all cells of a full optimization. -
Enhanced large-scale environment capability: The method can handle large-scale environments effectively because it avoids the
computational complexity
and risk of falling into local minima associated with Occupancy-SLAM, enabling the solution ofvery large-scale environments.
-
Superior map accuracy in challenging scenarios: Experimental results show that for large-scale datasets, the method achieves better performance than Cartographer, especially where
the right wall of our results are clearly closer to the straight line whereas that of the Cartographer’s results are somewhat curved,
leading to clearer object boundaries.
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation