Track manipulation, locomotion and embodied systems.
Search papers, labs, and topics across Lattice.
The authors formulate Inspection-SPARS, a task-oriented roadmap sparsification algorithm that addresses the combinatorial bottleneck of solving Graph Inspection Planning over dense sampling-based roadmaps. While dense graphs capture superior inspection viewpoints, they exhaust downstream solver budgets; meanwhile, prior sparsifiers fail to jointly guarantee point-of-interest (POI) coverage and path spanner bounds. By incorporating POI coverage directly into the sparsifier's admission criteria, the method reduces roadmap size by 4–8x and enables solvers to compute inspection tours up to 25% shorter within fixed time budgets.
Sparsifying inspection roadmaps by up to 8x without abandoning coverage or spanner guarantees yields downstream robotic inspection tours that are 25% shorter than those planned on unpruned dense graphs.
Inspection planning seeks a minimum-length collision-free robot tour that observes a given set of points of interest (POIs). Sampling-based methods reduce this continuous problem to a graph inspection planning (GIP) problem over a discrete roadmap, which is then solved using combinatorial solvers. Dense roadmaps capture diverse inspection viewpoints and motion shortcuts, and thus admit higher-quality solutions, but they induce large combinatorial search spaces on which state-of-the-art GIP solvers struggle to find good solutions within practical time budgets. Roadmap sparsification---restructuring a dense roadmap into a compact representation that preserves connectivity and path lengths---can alleviate this burden. However, existing sparsification approaches are either agnostic to the underlying inspection task, or strive to ensure coverage of the POIs without accounting for the quality of the resulting inspection plan. We present Inspection-SPARS, which is, to our knowledge, the first inspection-roadmap sparsifier with POI coverage and path-quality guarantees relative to the dense roadmap. To this end, we generalize the SPARS framework, a popular task-agnostic sparsifier, from purely geometric criteria to task-oriented ones, introducing an inspection-aware vertex admission mechanism that treats POI coverage as a first-class sparsification criterion alongside connectivity and path quality. Experiments in realistic 3D environments show that Inspection-SPARS reduces vertex and edge counts by 4-8x while preserving coverage, allowing the GIP solver to compute tours up to 25% shorter than with the dense roadmap or state-of-the-art inspection roadmap. More broadly, Inspection-SPARS shows that sparsification can be made task-aware without sacrificing guarantees on solution quality.