Inspection-SPARS: Task-Oriented Sparse Roadmaps for Inspection Planning

Adir Morgan; Oren Salzman; Kiril Solovey

cs.ROSep 28, 2026

Inspection-SPARS: Task-Oriented Sparse Roadmaps for Inspection Planning

Authors: Adir Morgan, Oren Salzman, Kiril Solovey

Organizations: The authors are with the Technion–Israel Institute of Technology, Haifa, Israel.

Abstract

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.

Figures & tables

Panel of Figure 1 — Fig. 1: Inspection planning in 3D scenes, comparing dense roadmaps against sparse roadmaps generated by Inspection-SPARS . Discarding redundant spatial detail while preserving geometric and POI-coverage information yields roadmaps on which good inspection plans are easier to find.

Fig. 2: Illustration of the four SPARS admission criteria:

a

is added as a guard,

b

may be added as a bridge or to support an interface connection, and

c

may be added to preserve a dense-roadmap shortcut whose sparse detour violates the prescribed stretch factor.

Panel of Figure 3 — Fig. 3: Examples motivating local inspection-coverage preservation. POIs are in orange, shaded area is visibility range. Dense-graph edges are gray and sparse-graph edges are light blue. (a) Geometric sparsification without POI-coverage enforcement may retain $q$ and omit $q^{\prime}$ , losing inspection on $p$ . (b) Global POI-coverage enforcement may choose $q$ over $q^{\prime}$ , leading to a lower-quality solution.

Panel of Figure 4 — Fig. 4: Roadmap and solution inspection plan on the City scene.

Scene	Robot radius	Sensor range	$\delta\;(=\eta)$	$\Delta\;(=r_{\mathrm{RRG}})$
Water-Tower	0.5	6	10	15
Bridge	0.8	10	3	4.5
City	0.8	10	8	12

TABLE I: Geometric and sensing parameters. The IRIS -based methods use

\eta=\delta

and

r_{\mathrm{RRG}}=\Delta

Fig. 5: Anytime solver performance with respect to inspection plan length. Solid curves show the mean over the six seeds, and shaded regions show one standard deviation. Lower is better.

Fig. 6: Roadmap construction vs. number of sampling iterations

N

for Water-Tower . Curves show means over ten random seeds, shaded regions show standard deviation. Count-based axes use logarithmic scales.

Explore similar work

Aug 6, 2026cs.RO

PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds

Autonomous robot navigation requires rapid construction of obstacle-points-separated convex regions for trajectory planning. When obstacles are represented as point clouds from LiDAR or depth cameras, these regions must be constructed directly from finite obstacle samples while providing suitable constraints for downstream optimization. However, existing corridor-generation methods often struggle to meet real-time, sensor-rate computational requirements. To address this bottleneck, we introduce RISP, a randomized algorithm that constructs convex polytopes from finite point-cloud data, and PathCover, which chains these polytopes along a reference path to form an overlapping corridor. We prove finite termination, sequential intersection, and complete path coverage with respect to the supplied finite point set. Under a probabilistic elimination condition, the sampling-and-elimination stage of RISP has expected O(n) time and unconditional worst-case O(n^2) time. Extensive benchmarks on synthetic and real-world LiDAR datasets demonstrate an order-of-magnitude speedup over state-of-the-art methods in both corridor generation as well as trajectory optimization, while closed-loop quadrotor simulation and a physical quadruped traversal demonstrate integration with downstream motion planners. These results establish corridor separation from the supplied point-cloud representation and practical implementation feasibility. Source code of the entire pipeline is available at https://github.com/kunalnk123690/PathCover.

Kunal S. Narkhede, Abhijeet M. Kulkarni, Guoquan Huang +1

Department of Mechanical Engineering, University of Delaware, Newark, DE 19716, USA · Robotics Institute, Athena Research Center, Marousi, Greece; School of Mechanical Engineering, National Technical University of Athens, Greece; HERON–Center of Excellence in Robotics, Athens, Greece

Path Planning Point Clouds Pathways Quadrotor Partitioning Nonconvex

Ask PDF

Sep 28, 2026cs.RO

CollisionSplatting: Collision-Aware Motion Planning in 3DGS Scenes with Image-Conditioned Objectives and Adjustable Conservatism

Incorporating dense visual information into motion planning remains challenging, as geometric planners rely on abstracted scene representations that discard visual richness, while learned visual models often lack geometric interpretability and computational efficiency. This paper introduces CollisionSplatting, a simple, modular, GPU-accelerated, probability-inspired distance metric with tunable conservatism that operates directly on standard 3D Gaussian Splatting (3DGS) scenes. When combined with learned image-conditioned reward functions, this metric enables joint geometric and visual planning by unifying collision-aware costs with image-space objectives. We integrate the metric into GPU-accelerated Model Predictive Path Integral (MPPI) and Rapidly-Exploring Random Tree (RRT) planners, and show on-par or better collision-classification performance compared to representative baselines while achieving substantially higher collision-checking throughput and significantly lower VRAM usage. Finally, we demonstrate the effectiveness of our metric in real-world vision-guided navigation and manipulation tasks, highlighting 3DGS as a practical bridge between rich perception and real-time motion planning.

R. Khorrambakht, Joaquim Ortiz-Haro, Stephan Weiss +1

Machines in Motion Lab, Tandon School of Engineering, New York University · Department of Smart Systems Technologies, University of Klagenfurt, Austria. · Artificial and Natural Intelligence Toulouse Institute (ANITI)

Collision-Free Trajectories Collision Prediction Motion Planning Model Predictive Path Integral

Ask PDF

Jun 15, 2026cs.RO

PolyMerge: Compressing 3D Gaussian Splats with Polytope Coverings for Provably Safe Resource-Constrained Navigation

Obstacle avoidance is essential for safe navigation and motion planning. Recent radiance field reconstruction methods enable object detection and modeling with high fidelity, but remain too memory- and compute-intensive for on-board perception-based path planning. To address these limitations, we propose PolyMerge to convert a large, photorealistic 3D Gaussian Splatting (3DGS) model of a scene into a lightweight representation of convex polytopes whose union provably over-approximates all obstacles in the original 3DGS model. PolyMerge tunes the polytope count to trade off conservativeness and compute cost, and integrates with control barrier functions (CBFs) to plan collision-free paths. We showcase PolyMerge in simulation and hardware experiments on a Crazyflie drone, which uses PolyMerge to compute and follow safe trajectories in real time under severe onboard compute constraints, outperforming baselines in speed while guaranteeing safety. For our code and videos, visit https://athlon76.github.io/PolyMerge-website/.

Jihoon Hong, Chih-Yuan Chiu, Sara Fridovich-Keil +1

1Georgia Institute of Technology.

Polytopes 3D Generation Object Detection

Ask PDF