Streaming Loop-Closure Selection under Memory Constraints in Graph-SLAM
Reza Vafaee, Usman Khan
AI summary
Problem
Resource-constrained robots must online decide which loop-closure measurements to retain under strict memory limits, but prior methods assume offline access to complete pose graphs and ignore the time-varying nature of estimation utility as odometry accumulates.
Approach
The authors cast loop-closure selection as streaming submodular maximization with a time-varying log-determinant objective and introduce a one-pass preemptive greedy policy that maintains exactly k memory slots by evaluating single-edge swaps against a dynamic threshold.
Key results
- Formulated streaming loop-closure selection as submodular maximization with a time-varying log-determinant objective
- Designed a one-pass preemptive greedy algorithm with exactly k memory slots
- Proved a uniform 1/4 approximation guarantee relative to the hindsight-optimal solution
- Demonstrated near-offline greedy performance on benchmarks while outperforming streaming baselines
Why it matters
Enables scalable, memory-efficient SLAM on resource-limited platforms by providing principled, real-time measurement selection without sacrificing estimation accuracy.
Abstract
Graph-based SLAM models robot poses as ver- tices and relative-pose measurements (odometry and loop- closures) as edges. Odometry edges are always kept to preserve connectivity, while loop-closure edges reduce drift but cannot all be stored due to memory or computation limits. Our challenge is to decide online which closures to keep under a strict budget, when the full set of measurements cannot be stored or centralized. Prior work instead addresses an offline problem that assumes access to the complete pose graph and optimizes a log-determinant (D-optimality) surrogate. In the online regime, an additional difficulty arises because the odometry backbone grows over time and the utility of each loop-closure changes as the graph evolves. We formulate this problem as streaming submodular maximization with a time-varying log-determinant objective. We propose a one-pass preemptive greedy policy that operates with exactly k memory slots for loop-closures. We show that, under arbitrary arrival order, it achieves a uniform constant-factor guarantee on the log-determinant improvement beyond an odometry-only baseline, relative to the hindsight- optimal size-k solution. On benchmark data, the proposed method closely matches offline greedy despite the conservative bound, showing that principled streaming selection can recover most of the benefit of loop-closures while respecting resource limits.