OptMap: Geometric Map Distillation via Submodular Maximization

• URL: http://arxiv.org/abs/2512.07775v1
• Date: Mon, 08 Dec 2025 17:56:57 GMT
• Title: OptMap: Geometric Map Distillation via Submodular Maximization
• Abstract summary: Autonomous robots rely on geometric maps to inform a diverse set of perception and decision-making algorithms.<n>As autonomy requires reasoning and planning on multiple scales, each may require a different map for optimal performance.<n>We present OptMap: a geometric map distillation algorithm which achieves real-time, application-specific map generation.
• Score: 1.826848871278733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Autonomous robots rely on geometric maps to inform a diverse set of perception and decision-making algorithms. As autonomy requires reasoning and planning on multiple scales of the environment, each algorithm may require a different map for optimal performance. Light Detection And Ranging (LiDAR) sensors generate an abundance of geometric data to satisfy these diverse requirements, but selecting informative, size-constrained maps is computationally challenging as it requires solving an NP-hard combinatorial optimization. In this work we present OptMap: a geometric map distillation algorithm which achieves real-time, application-specific map generation via multiple theoretical and algorithmic innovations. A central feature is the maximization of set functions that exhibit diminishing returns, i.e., submodularity, using polynomial-time algorithms with provably near-optimal solutions. We formulate a novel submodular reward function which quantifies informativeness, reduces input set sizes, and minimizes bias in sequentially collected datasets. Further, we propose a dynamically reordered streaming submodular algorithm which improves empirical solution quality and addresses input order bias via an online approximation of the value of all scans. Testing was conducted on open-source and custom datasets with an emphasis on long-duration mapping sessions, highlighting OptMap's minimal computation requirements. Open-source ROS1 and ROS2 packages are available and can be used alongside any LiDAR SLAM algorithm.

Related papers

• Flow Priors for Linear Inverse Problems via Iterative Corrupted Trajectory Matching [35.77769905072651]
  We propose an iterative algorithm to approximate the MAP estimator efficiently to solve a variety of linear inverse problems.<n>Our algorithm is mathematically justified by the observation that the MAP objective can be approximated by a sum of $N$ local MAP'' objectives.<n>We validate our approach for various linear inverse problems, such as super-resolution, deblurring, inpainting, and compressed sensing.
  arXiv  Detail & Related papers  (2024-05-29T06:56:12Z)
• UAV-Borne Mapping Algorithms for Low-Altitude and High-Speed Drone Applications [0.4681661603096333]
  This article presents an analysis of current state-of-the-art sensors and how they work with several mapping algorithms for UAV (Unmanned Aerial Vehicle) applications. A new experimental construct is created using highly realistic environments made possible by integrating the AirSim simulator with Google 3D maps models.
  arXiv  Detail & Related papers  (2024-01-12T07:04:44Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems. It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
  arXiv  Detail & Related papers  (2022-11-14T12:32:18Z)
• Spatially scalable recursive estimation of Gaussian process terrain maps using local basis functions [0.8192907805418581]
  Online mapping of nonlinear terrains can be used to improve position estimates when an agent returns to a previously mapped area.<n>GP mapping algorithms have increasing computational demands as the mapped area expands.<n>We show experimentally that our algorithm is faster than existing methods when the mapped area is large.
  arXiv  Detail & Related papers  (2022-10-17T15:13:41Z)
• Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
  A submodular function in the MapReduce (MR) model has received much attention. We show that several sublinearly adaptive algorithms satisfy the consistency property required to work in the MR setting.
  arXiv  Detail & Related papers  (2022-06-20T04:17:32Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Adaptive Sampling for Fast Constrained Maximization of Submodular Function [8.619758302080891]
  We develop an algorithm with poly-logarithmic adaptivity for non-monotone submodular under general side constraints. Our algorithm is suitable to maximize a non-monotone submodular function under a $p$-system side constraint.
  arXiv  Detail & Related papers  (2021-02-12T12:38:03Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.