Toward Asymptotically-Optimal Inspection Planning via Efficient Near-Optimal Graph Search

Abstract

Inspection planning, the task of planning motions that allow a robot to inspect a set of points of interest, has applications in domains such as industrial, field, and medical robotics. Inspection planning can be computationally challenging, as the search space over motion plans grows exponentially with the number of points of interest to inspect. We propose a novel method, Incremental Random Inspection-roadmap Search (IRIS), that computes inspection plans whose length and set of successfully inspected points asymptotically converge to those of an optimal inspection plan. IRIS incrementally densifies a motion planning roadmap using sampling-based algorithms, and performs efficient near-optimal graph search over the resulting roadmap as it is generated. We demonstrate IRIS's efficacy on a simulated planar 5DOF manipulator inspection task and on a medical endoscopic inspection task for a continuum parallel surgical robot in cluttered anatomy segmented from patient CT data. We show that IRIS computes higher-quality inspection plans orders of magnitudes faster than a prior state-of-the-art method.

Fig. 1:

Inspection planning in human anatomy. Top Left: The Continuum Reconfigurable Incisionless Surgical Parallel (CRISP) robot [2, 38] is composed of needle-diameter tubes assembled into a parallel structure inside the patient’s body (in which a tube uses a snare system to grip a tube with a camera affixed to its tip) and then robotically manipulated outside the body, allowing for smaller incisions and faster recovery times compared to traditional endoscopic tools (which have larger diameters). Top Right: The CRISP robot in simulation inspecting a collapsed lung, a scenario segmented from a CT scan of a real patient with this condition. The visualization shows the robot (orange), the lungs (pink), and the pleural surface visible (green) and not visible (blue) by the robot’s camera sensor in its current configuration. Bottom: Our method, IRIS, constructs a tree representing collision-free configurations (orange nodes) and motions (solid lines) of the robot. For each node, the robot (orange) can see points of interest (yellow) on the segmented anatomy (blue). IRIS then searches over an implicit graph structure (dashed lines) to compute asymptotically-optimal inspection plans.

Fig. 2:

Overview of the IRIS algorithmic framework

Fig. 3:

Computing optimal inspection paths on graphs by casting a graph-inspection problem (bottom) to a graph-search problem (top). Grey layers corresponds to the set of all vertices in ${\mathcal{V}}_{\mathcal{S}}$ that share the same set of points inspected. Edges connecting vertices in the same (different) layer are depicted in dashed (dotted) lines, respectively. The start is (a, ∅) and the goal set ${\mathcal{V}}_{\text{goal}}$ contains all vertices in the top layer. Notice that the optimal path (blue) visits vertex a twice.

Fig. 4:

Visualization of the notion of dominating paths by considering a path P from v_s to some vertex u as a two-dimensional point $(\mathcal{l}(P),\mathcal{S}(P))$. Here ${\mathcal{I}}_{\mathcal{G}}=\{0,1,2,3\}$. and P is depicted using the purple circle with ℓ(P) = ℓ and $\mathcal{S}(P)=\left\{2,3\right\}$. (a) All paths from v_s to u that are dominated by P (solid red), (b) All paths from v_s to u that are ε, p-dominated by P. Paths that are ε, 1-dominated by P and that are 0, p-dominated by P for p = 60% are depicted in solid blue and dashed red, respectively. Dashed blue lines depict paths that are ε, p-dominated by P for ε > 0 and p = 60%.

Fig. 5:

Depiction of operations on path pairs. (a) PP extended by an edge e = (u,v) with $\mathcal{S}(v)=\left\{2\right\}$. (b) PP₁ subsuming PP₂. Note that P₁ is the achievable path of PP₁ ⊕ PP₂ thus only the potentially-achievable path is explicitly marked.

Fig. 6:

Visualization of Alg. 1 initialized with ε = 2/3 and p = 1/2 (only the relevant parts of the inspection graph are depicted). The search starts from (a, ∅) with the trivial PAP of length zero and no points inspected. (a) Two paths (red and blue) are extended from the start node to (b, {0}) and (c, {1}) with path pairs PP₁ and PP₂, respectively (the PAP’s of each path have the same length and coverage as the paths themselves). (b) Blue path extended to (d, {0}) with $\mathcal{l}\left(P_1\right)=\mathcal{l}\left({\tilde{P}}_1\right)=2$ and $\mathcal{S}\left(P_1\right)=S\left({\tilde{P}}_1\right)=\left\{0\right\}$. (c) Red path extended to (d, {1}) with $\mathcal{l}\left(P_2\right)=\mathcal{l}\left({\tilde{P}}_2\right)=3$ and $\mathcal{S}\left(P_2\right)=S\left({\tilde{P}}_2\right)=\left\{1\right\}$. Here, PP₁ ⊕ PP₂ ε, p-dominates PP₂ and the red path is discarded and PAP₁ is updated to have length 2 and coverage {0, 1} (d) Blue path extended to vertex (e, {0, 2}). Here, $\mathcal{l}\left(P_1\right)=\mathcal{l}\left({\tilde{P}}_1\right)=3$ and $\mathcal{S}\left(P_1\right)=\left\{0,2\right\}$, $S\left({\tilde{P}}_1\right)=\{0,1,2\}$. The algorithm terminates with the path a − b − d − e whose length is 3 and has coverage of {0, 2}. Notice that the path a−c−d−e (not computed) is optimal as its length is four and it has complete coverage. The computed path is within the bounds ensured by the approximation factor p and ε.

Fig. 7:

Simulation scenarios. (a) A 5-link planar manipulator (orange) inspects the boundary of a square region (blue) where rectangular obstacles (red) may block the robot and occlude the sensor. The sensor’s field of view (FOV) is represented by the yellow region. $\mathcal{S}(q)$ are the points on the boundary in the sensor’s unobstructed FOV, and are shown in purple. (b) The pleural effusion inspection scenario involves the CRISP robot (orange) inspecting the inner surface of a pleural cavity, including the POI that are covered (green) and non-covered (blue) from the current robot configuration.

Fig. 8:

Quality of inspection paths computed for the planar manipulator. (a) IRIS running with p = 1, f = 0 and varying values of ε. (b) IRIS running with ε = 0, f = 0 and varying values of p. (c) Comparison of IRIS and RRTOT. IRIS running with two input parameter settings, both with f = 0.03.

Fig. 9:

Comparing quality of inspection paths computed for the pleural effusion scenario. IRIS was run with p₀ = 0.8, ε₀ = 10, and f = 0.01.