Technical Summary: OptMap - Geometric Map Distillation via Submodular Maximization

Problem Statement

Autonomous robots rely on geometric maps for perception and decision-making, but different algorithms require maps with varying characteristics (e.g., dense for change detection vs. summarized for multi-robot sharing). Modern LiDAR sensors generate massive amounts of data (up to 50 MB/s), making the storage and processing of full point clouds computationally prohibitive for online applications. While learned representations (descriptors) can encode similarity to bypass expensive point-based operations, selecting an informative, size-constrained subset of scans remains an NP-hard combinatorial problem. Existing approaches, such as keyframe selection or occupancy grids, often suffer from high memory costs, slow updates, or a lack of adaptability to diverse downstream tasks.

The paper defines Geometric Map Distillation as the process of extracting key information from perception sensors to create an application-specific map with maximum utility, constrained by size and computational efficiency.

Methodology

OptMap addresses this problem by formulating map distillation as a submodular maximization problem. The pipeline consists of four stages: LiDAR mapping, descriptor generation, dynamically ordered streaming submodular maximization, and map loading.

1. Continuous Exemplar-Based Clustering (CEBC)

The core innovation is a novel submodular reward function, CEBC, designed to quantify map informativeness without bias toward over-sampled regions (e.g., when a robot is stationary).

• Descriptor Space: LiDAR scans are converted into unit-length descriptors on an $n$-hypersphere ($S_n$).
• Clustering vs. Coverage: The authors argue that clustering functions (maximizing mutual information between the solution and the input set) are superior to coverage functions (minimizing mutual information within the solution) because they reward both representativeness and diversity.
• Continuous Trajectory Assumption: To handle redundant scans, CEBC treats the mapping session as a continuous trajectory. It integrates the distance between the solution and the trajectory over time, weighting sequential elements by their geometric distance. This ensures that densely sampled, identical scans contribute less to the reward than distinct, informative scans.
• Reduced Input Sets: To mitigate the computational cost of evaluating clustering functions over large input sets, the authors propose a method to generate a "reduced set" of descriptors. By omitting sequentially redundant elements (those within a threshold distance $\mathcal{E}$), the input size is significantly reduced while maintaining theoretical bounds on solution quality.

2. Dynamically Reordered Streaming Submodular Maximization

To solve the optimization problem online with limited information, OptMap employs a streaming submodular algorithm enhanced with Dynamic Reordering (DR).

• Input Order Bias: Standard streaming algorithms suffer from bias where elements appearing earlier in the stream are selected more often due to relaxed admission thresholds (Opportunity Cost Bias) or threshold saturation (Threshold Saturation Bias).
• Dynamic Reordering: Instead of processing the stream in its raw order, OptMap dynamically reorders elements based on approximate marginal values. It uses two $O(1)$ approximation functions to estimate the value of unchecked elements:
  1. Pose-based Approximation: Uses spatial distance between scan poses.
  2. Descriptor-based Approximation: Uses pairwise information and spherical cap coverage to estimate mutual information.
• Process: The algorithm maintains sorted and unsorted sets of elements. At each step, it selects the element with the highest estimated marginal value to process next, thereby prioritizing high-value scans and mitigating order bias.

3. Tight A Priori Solution Bounds

The algorithm utilizes heuristic solutions (e.g., selecting scans at equal intervals along the descriptor trajectory) to establish tight lower bounds on the optimal solution value. These bounds allow the streaming algorithm to maintain fewer parallel solution candidates, significantly reducing computation time.

Key Contributions

1. Continuous Exemplar-Based Clustering (CEBC): A novel submodular function that quantifies informativeness while correcting for oversampling bias via a continuous trajectory assumption. It allows for the use of reduced input sets without significant loss in solution quality.
2. Dynamic Reordering: A method to address input order bias in streaming submodular maximization by approximating marginal values and reordering the stream to prioritize high-value elements.
3. Tight A Priori Bounds: A heuristic approach to derive initial solution bounds, reducing the number of maintained solutions and improving computational efficiency.
4. Open-Source Implementation: Release of ROS1 and ROS2 packages compatible with any LiDAR odometry algorithm, facilitating practical deployment.

Results

The authors evaluated OptMap on open-source datasets (Newer College, Oxford Spires, Semantic KITTI) and custom datasets (UCLA campus, Army Research Laboratory).

• Reward Function Evaluation: CEBC consistently outperformed or matched standard Exemplar-Based Clustering (EBC) and coverage functions across diverse environments. Using a reduced input set with a threshold of $\mathcal{E}=0.25$, CEBC achieved an 84% reduction in evaluation time and a 65% reduction in input set size compared to EBC, while maintaining near-optimal overlap with dense comparison maps.
• Dynamic Reordering Ablation: In datasets with high redundancy (e.g., a robot patrolling a loop), dynamic reordering significantly improved map quality and consistency compared to standard Sieve-Streaming, random selection, or evenly spaced heuristics. The combined descriptor and pose approximation method proved most robust, achieving high overlap percentages (e.g., 99.0% normalized overlap on KITTI 05) and low standard deviation.
• Computational Performance: OptMap demonstrated real-time capabilities. For a dataset with 34,158 scans, the total time to generate a 500-scan distilled map was approximately 3.2 seconds (including loading). The use of a priori bounds reduced optimization time by up to 49% on larger datasets.
• Application (Change Detection): The paper demonstrates an online geometric change detection application. OptMap generated dense submaps (60 scans) in 196 ms, enabling the detection of objects (e.g., a 20 cm backpack) that would be missed by standard downsampling or voxelization methods due to memory constraints.

Significance and Claims

The paper claims that OptMap provides a practical solution for generating size-constrained, informative geometric maps for online autonomy. Its significance lies in:

• Efficiency: It bypasses the need for storing entire point clouds or performing expensive point-to-point computations by leveraging learned descriptors and submodular optimization.
• Adaptability: It can generate maps tailored to specific downstream needs (e.g., dense maps for change detection, summarized maps for multi-robot sharing) on demand.
• Robustness: By addressing input order bias and oversampling, it produces high-quality distilled maps even in challenging, redundant mapping scenarios.
• Practicality: The open-source nature and compatibility with existing LiDAR odometry stacks allow for immediate integration into robotic systems, supporting applications like online change detection and multi-robot coordination.

The authors position OptMap as a necessary evolution for long-duration missions where memory and computation constraints prevent the use of dense global maps, offering a bridge between raw sensor data and application-specific autonomy algorithms.