- Main
Submodular Maximization for Geometric Robotic Perception
- Thorne, David Paul
- Advisor(s): Lopez, Brett T
Abstract
Modern geometric sensors collect an abundance of data used to generate detailed maps which inform decision-making algorithms in autonomous robots. However, processing high volumes of perception data online is not feasible given the limited computation and memory resources available to most robots. Instead, autonomy algorithms remain tractable by prioritizing smaller subsets of perception data via heuristic downsampling, which lacks generality and requires extensive, environment-specific tuning. Posing this prioritization instead as a combinatorial optimization problem quantifies the value of each observation, so size-constrained, informative subsets can be selected directly. This dissertation develops the theory and algorithms for solving such combinatorial problems online within provable suboptimality bounds. The central tool is submodular maximization, where set functions exhibiting diminishing returns admit polynomial-time algorithms with near-optimal guarantees. Three primary contributions formulate and optimize submodular functions to improve memory, computation, or task performance in LiDAR Simultaneous Localization And Mapping (SLAM), map distillation, and geometric change detection. The first contribution addresses three such problems in LiDAR SLAM, optimizing keyframe selection and usage to reduce memory and computation demands. Two of the problems are solved as optimizations over a set of learned point cloud descriptors, which simplify otherwise expensive point-wise overlap computations. The second contribution extends the use of descriptors to geometric map distillation, the problem of selecting informative submaps from all geometric data collected in a mapping session. A novel submodular function which quantifies map informativeness using descriptors is optimized with a dynamically reordered streaming algorithm to solve geometric map distillation online. The final contribution applies geometric map distillation to online geometric change detection. In this framework, representative submaps are selected for local scenes and used in a submap-to-submap change detection algorithm that is both accurate and computationally efficient. Each contribution is validated on field tests and open-source datasets, with an emphasis on long-duration missions through unstructured environments. Open-source implementations make the contributions widely available for testing and development.