Toward certifiable optimal motion planning for medical steerable needles.

Medical steerable needles can follow 3D curvilinear trajectories to avoid anatomical obstacles and reach clinically significant targets inside the human body. Automating steerable needle procedures can enable physicians and patients to harness the full potential of steerable needles by maximally leveraging their steerability to safely and accurately reach targets for medical procedures such as biopsies. For the automation of medical procedures to be clinically accepted, it is critical from a patient care, safety, and regulatory perspective to certify the correctness and effectiveness of the planning algorithms involved in procedure automation. In this paper, we take an important step toward creating a certifiable optimal planner for steerable needles. We present an efficient, resolution-complete motion planner for steerable needles based on a novel adaptation of multi-resolution planning. This is the first motion planner for steerable needles that guarantees to compute in finite time an obstacle-avoiding plan (or notify the user that no such plan exists), under clinically appropriate assumptions. Based on this planner, we then develop the first resolution-optimal motion planner for steerable needles that further provides theoretical guarantees on the quality of the computed motion plan, that is, global optimality, in finite time. Compared to state-of-the-art steerable needle motion planners, we demonstrate with clinically realistic simulations that our planners not only provide theoretical guarantees but also have higher success rates, have lower computation times, and result in higher quality plans.

Stochastic Extended LQR for Optimization-based Motion Planning Under Uncertainty.

We introduce a novel optimization-based motion planner, Stochastic Extended LQR (SELQR), which computes a trajectory and associated linear control policy with the objective of minimizing the expected value of a user-defined cost function. SELQR applies to robotic systems that have stochastic non-linear dynamics with motion uncertainty modeled by Gaussian distributions that can be state- and control-dependent. In each iteration, SELQR uses a combination of forward and backward value iteration to estimate the cost-to-come and the cost-to-go for each state along a trajectory. SELQR then locally optimizes each state along the trajectory at each iteration to minimize the expected total cost, which results in smoothed states that are used for dynamics linearization and cost function quadratization. SELQR progressively improves the approximation of the expected total cost, resulting in higher quality plans. For applications with imperfect sensing, we extend SELQR to plan in the robot's belief space. We show that our iterative approach achieves fast and reliable convergence to high-quality plans in multiple simulated scenarios involving a car-like robot, a quadrotor, and a medical steerable needle performing a liver biopsy procedure.

High-Frequency Replanning Under Uncertainty Using Parallel Sampling-Based Motion Planning.

As sampling-based motion planners become faster, they can be re-executed more frequently by a robot during task execution to react to uncertainty in robot motion, obstacle motion, sensing noise, and uncertainty in the robot's kinematic model. We investigate and analyze high-frequency replanning (HFR), where, during each period, fast sampling-based motion planners are executed in parallel as the robot simultaneously executes the first action of the best motion plan from the previous period. We consider discrete-time systems with stochastic nonlinear (but linearizable) dynamics and observation models with noise drawn from zero mean Gaussian distributions. The objective is to maximize the probability of success (i.e., avoid collision with obstacles and reach the goal) or to minimize path length subject to a lower bound on the probability of success. We show that, as parallel computation power increases, HFR offers asymptotic optimality for these objectives during each period for goal-oriented problems. We then demonstrate the effectiveness of HFR for holonomic and nonholonomic robots including car-like vehicles and steerable medical needles.

Asymptotically Optimal Motion Planning for Learned Tasks Using Time-Dependent Cost Maps.

In unstructured environments in people's homes and workspaces, robots executing a task may need to avoid obstacles while satisfying task motion constraints, e.g., keeping a plate of food level to avoid spills or properly orienting a finger to push a button. We introduce a sampling-based method for computing motion plans that are collision-free and minimize a cost metric that encodes task motion constraints. Our time-dependent cost metric, learned from a set of demonstrations, encodes features of a task's motion that are consistent across the demonstrations and, hence, are likely required to successfully execute the task. Our sampling-based motion planner uses the learned cost metric to compute plans that simultaneously avoid obstacles and satisfy task constraints. The motion planner is asymptotically optimal and minimizes the Mahalanobis distance between the planned trajectory and the distribution of demonstrations in a feature space parameterized by the locations of task-relevant objects. The motion planner also leverages the distribution of the demonstrations to significantly reduce plan computation time. We demonstrate the method's effectiveness and speed using a small humanoid robot performing tasks requiring both obstacle avoidance and satisfaction of learned task constraints. NOTE TO PRACTITIONERS: Motivated by the desire to enable robots to autonomously operate in cluttered home and workplace environments, this paper presents an approach for intuitively training a robot in a manner that enables it to repeat the task in novel scenarios and in the presence of unforeseen obstacles in the environment. Based on user-provided demonstrations of the task, our method learns features of the task that are consistent across the demonstrations and that we expect should be repeated by the robot when performing the task. We next present an efficient algorithm for planning robot motions to perform the task based on the learned features while avoiding obstacles. We demonstrate the effectiveness of our motion planner for scenarios requiring transferring a powder and pushing a button in environments with obstacles, and we plan to extend our results to more complex tasks in the future.

Scalable Multicore Motion Planning Using Lock-Free Concurrency.

We present PRRT (Parallel RRT) and PRRT* (Parallel RRT*), sampling-based methods for feasible and optimal motion planning designed for modern multicore CPUs. We parallelize RRT and RRT* such that all threads concurrently build a single motion planning tree. Parallelization in this manner requires that data structures, such as the nearest neighbor search tree and the motion planning tree, are safely shared across multiple threads. Rather than rely on traditional locks which can result in slowdowns due to lock contention, we introduce algorithms based on lock-free concurrency using atomic operations. We further improve scalability by using partition-based sampling (which shrinks each core's working data set to improve cache efficiency) and parallel work-saving (in reducing the number of rewiring steps performed in PRRT*). Because PRRT and PRRT* are CPU-based, they can be directly integrated with existing libraries. We demonstrate that PRRT and PRRT* scale well as core counts increase, in some cases exhibiting superlinear speedup, for scenarios such as the Alpha Puzzle and Cubicles scenarios and the Aldebaran Nao robot performing a 2-handed task.

Needle Steering in 3-D Via Rapid Replanning.

Steerable needles have the potential to improve the effectiveness of needle-based clinical procedures such as biopsy and drug delivery by improving targeting accuracy and reaching previously inaccessible targets that are behind sensitive or impenetrable anatomical regions. We present a new needle steering system capable of automatically reaching targets in 3-D environments while avoiding obstacles and compensating for real-world uncertainties. Given a specification of anatomical obstacles and a clinical target (e.g., from preoperative medical images), our system plans and controls needle motion in a closed-loop fashion under sensory feedback to optimize a clinical metric. We unify planning and control using a new fast algorithm that continuously replans the needle motion. Our rapid replanning approach is enabled by an efficient sampling-based rapidly exploring random tree (RRT) planner that achieves orders-of-magnitude reduction in computation time compared with prior 3-D approaches by incorporating variable curvature kinematics and a novel distance metric for planning. Our system uses an electromagnetic tracking system to sense the state of the needle tip during the procedure. We experimentally evaluate our needle steering system using tissue phantoms and animal tissue ex vivo. We demonstrate that our rapid replanning strategy successfully guides the needle around obstacles to desired 3-D targets with an average error of less than 3 mm.

Needle path planning and steering in a three-dimensional non-static environment using two-dimensional ultrasound images.

Needle insertion is commonly performed in minimally invasive medical procedures such as biopsy and radiation cancer treatment. During such procedures, accurate needle tip placement is critical for correct diagnosis or successful treatment. Accurate placement of the needle tip inside tissue is challenging, especially when the target moves and anatomical obstacles must be avoided. We develop a needle steering system capable of autonomously and accurately guiding a steerable needle using two-dimensional (2D) ultrasound images. The needle is steered to a moving target while avoiding moving obstacles in a three-dimensional (3D) non-static environment. Using a 2D ultrasound imaging device, our system accurately tracks the needle tip motion in 3D space in order to estimate the tip pose. The needle tip pose is used by a rapidly exploring random tree-based motion planner to compute a feasible needle path to the target. The motion planner is sufficiently fast such that replanning can be performed repeatedly in a closed-loop manner. This enables the system to correct for perturbations in needle motion, and movement in obstacle and target locations. Our needle steering experiments in a soft-tissue phantom achieves maximum targeting errors of 0.86 ± 0.35 mm (without obstacles) and 2.16 ± 0.88 mm (with a moving obstacle).

Landmark Based Bronchoscope Localization for Needle Insertion Under Respiratory Deformation.

Bronchoscopy is currently the least invasive method for definitively diagnosing lung cancer, which kills more people in the United States than any other form of cancer. Successfully diagnosing suspicious lung nodules requires accurate localization of the bronchoscope relative to a planned biopsy site in the airways. This task is challenging because the lung deforms intraoperatively due to respiratory motion, the airways lack photometric features, and the anatomy's appearance is repetitive. In this paper, we introduce a real-time camera-based method for accurately localizing a bronchoscope with respect to a planned needle insertion pose. Our approach uses deep learning and accounts for deformations and overcomes limitations of global pose estimation by estimating pose relative to anatomical landmarks. Specifically, our learned model considers airway bifurcations along the airway wall as landmarks because they are distinct geometric features that do not vary significantly with respiratory motion. We evaluate our method in a simulated dataset of lungs undergoing respiratory motion. The results show that our method generalizes across patients and localizes the bronchoscope with accuracy sufficient to access the smallest clinically-relevant nodules across all levels of respiratory deformation, even in challenging distal airways. Our method could enable physicians to perform more accurate biopsies and serve as a key building block toward accurate autonomous robotic bronchoscopy.

Autonomous medical needle steering in vivo.

The use of needles to access sites within organs is fundamental to many interventional medical procedures both for diagnosis and treatment. Safely and accurately navigating a needle through living tissue to a target is currently often challenging or infeasible because of the presence of anatomical obstacles, high levels of uncertainty, and natural tissue motion. Medical robots capable of automating needle-based procedures have the potential to overcome these challenges and enable enhanced patient care and safety. However, autonomous navigation of a needle around obstacles to a predefined target in vivo has not been shown. Here, we introduce a medical robot that autonomously navigates a needle through living tissue around anatomical obstacles to a target in vivo. Our system leverages a laser-patterned highly flexible steerable needle capable of maneuvering along curvilinear trajectories. The autonomous robot accounts for anatomical obstacles, uncertainty in tissue/needle interaction, and respiratory motion using replanning, control, and safe insertion time windows. We applied the system to lung biopsy, which is critical for diagnosing lung cancer, the leading cause of cancer-related deaths in the United States. We demonstrated successful performance of our system in multiple in vivo porcine studies achieving targeting errors less than the radius of clinically relevant lung nodules. We also demonstrated that our approach offers greater accuracy compared with a standard manual bronchoscopy technique. Our results show the feasibility and advantage of deploying autonomous steerable needle robots in living tissue and how these systems can extend the current capabilities of physicians to further improve patient care.

Resolution-Optimal Motion Planning for Steerable Needles.

Medical steerable needles can follow 3D curvilinear trajectories inside body tissue, enabling them to move around critical anatomical structures and precisely reach clinically significant targets in a minimally invasive way. Automating needle steering, with motion planning as a key component, has the potential to maximize the accuracy, precision, speed, and safety of steerable needle procedures. In this paper, we introduce the first resolution-optimal motion planner for steerable needles that offers excellent practical performance in terms of runtime while simultaneously providing strong theoretical guarantees on completeness and the global optimality of the motion plan in finite time. Compared to state-of-the-art steerable needle motion planners, simulation experiments on realistic scenarios of lung biopsy demonstrate that our proposed planner is faster in generating higher-quality plans while incorporating clinically relevant cost functions. This indicates that the theoretical guarantees of the proposed planner have a practical impact on the motion plan quality, which is valuable for computing motion plans that minimize patient trauma.

A Metric for Finding Robust Start Positions for Medical Steerable Needle Automation.

Steerable needles are medical devices with the ability to follow curvilinear paths to reach targets while circumventing obstacles. In the deployment process, a human operator typically places the steerable needle at its start position on a tissue surface and then hands off control to the automation that steers the needle to the target. Due to uncertainty in the placement of the needle by the human operator, choosing a start position that is robust to deviations is crucial since some start positions may make it impossible for the steerable needle to safely reach the target. We introduce a method to efficiently evaluate steerable needle motion plans such that they are safe to variation in the start position. This method can be applied to many steerable needle planners and requires that the needle's orientation angle at insertion can be robotically controlled. Specifically, we introduce a method that builds a funnel around a given plan to determine a safe insertion surface corresponding to insertion points from which it is guaranteed that a collision-free motion plan to the goal can be computed. We use this technique to evaluate multiple feasible plans and select the one that maximizes the size of the safe insertion surface. We evaluate our method through simulation in a lung biopsy scenario and show that the method is able to quickly find needle plans with a large safe insertion surface.

Robot-Assisted Needle Steering.

Needle insertion is a critical aspect of many medical treatments, diagnostic methods, and scientific studies, and is considered to be one of the simplest and most minimally invasive medical procedures. Robot-assisted needle steering has the potential to improve the effectiveness of existing medical procedures and enable new ones by allowing increased accuracy through more dexterous control of the needle tip path and acquisition of targets not accessible by straight-line trajectories. In this article, we describe a robot-assisted needle steering system that uses three integrated controllers: a motion planner concerned with guiding the needle around obstacles to a target in a desired plane, a planar controller that maintains the needle in the desired plane, and a torsion compensator that controls the needle tip orientation about the axis of the needle shaft. Experimental results from steering an asymmetric-tip needle in artificial tissue demonstrate the effectiveness of the system and its sensitivity to various environmental and control parameters. In addition, we show an example of needle steering in ex vivo biological tissue to accomplish a clinically relevant task, and highlight challenges of practical needle steering implementation.

Toward Certifiable Motion Planning for Medical Steerable Needles.

Medical steerable needles can move along 3D curvilinear trajectories to avoid anatomical obstacles and reach clinically significant targets inside the human body. Automating steerable needle procedures can enable physicians and patients to harness the full potential of steerable needles by maximally leveraging their steerability to safely and accurately reach targets for medical procedures such as biopsies and localized therapy delivery for cancer. For the automation of medical procedures to be clinically accepted, it is critical from a patient care, safety, and regulatory perspective to certify the correctness and effectiveness of the motion planning algorithms involved in procedure automation. In this paper, we take an important step toward creating a certifiable motion planner for steerable needles. We introduce the first motion planner for steerable needles that offers a guarantee, under clinically appropriate assumptions, that it will, in finite time, compute an exact, obstacle-avoiding motion plan to a specified target, or notify the user that no such plan exists. We present an efficient, resolution-complete motion planner for steerable needles based on a novel adaptation of multi-resolution planning. Compared to state-of-the-art steerable needle motion planners (none of which provide any completeness guarantees), we demonstrate that our new resolution-complete motion planner computes plans faster and with a higher success rate.

Design Considerations for a Steerable Needle Robot to Maximize Reachable Lung Volume.

Steerable needles that are able to follow curvilinear trajectories and steer around anatomical obstacles are a promising solution for many interventional procedures. In the lung, these needles can be deployed from the tip of a conventional bronchoscope to reach lung lesions for diagnosis. The reach of such a device depends on several design parameters including the bronchoscope diameter, the angle of the piercing device relative to the medial axis of the airway, and the needle's minimum radius of curvature while steering. Assessing the effect of these parameters on the overall system's clinical utility is important in informing future design choices and understanding the capabilities and limitations of the system. In this paper, we analyze the effect of various settings for these three robot parameters on the percentage of the lung that the robot can reach. We combine Monte Carlo random sampling of piercing configurations with a Rapidly-exploring Random Trees based steerable needle motion planner in simulated human lung environments to asymptotically accurately estimate the volume of sites in the lung reachable by the robot. We highlight the importance of each parameter on the overall system's reachable workspace in an effort to motivate future device innovation and highlight design trade-offs.

Backward Planning for a Multi-Stage Steerable Needle Lung Robot.

Lung cancer is one of the deadliest types of cancer, and early diagnosis is crucial for successful treatment. Definitively diagnosing lung cancer typically requires biopsy, but current approaches either carry a high procedural risk for the patient or are incapable of reaching many sites of clinical interest in the lung. We present a new sampling-based planning method for a steerable needle lung robot that has the potential to accurately reach targets in most regions of the lung. The robot comprises three stages: a transorally deployed bronchoscope, a sharpened piercing tube (to pierce into the lung parenchyma from the airways), and a steerable needle able to navigate to the target. Planning for the sequential deployment of all three stages under health safety concerns is a challenging task, as each stage depends on the previous one. We introduce a new backward planning approach that starts at the target and advances backwards toward the airways with the goal of finding a piercing site reachable by the bronchoscope. This new strategy enables faster performance by iteratively building a single search tree during the entire computation period, whereas previous forward approaches have relied on repeating this expensive tree construction process many times. Additionally, our method further reduces runtime by employing biased sampling and sample rejection based on geometric constraints. We evaluate this approach using simulation-based studies in anatomical lung models. We demonstrate in comparison with existing techniques that the new approach (i) is more likely to find a path to a target, (ii) is more efficient by reaching targets more than 5 times faster on average, and (iii) arrives at lower-risk paths in shorter time.

Learning the Complete Shape of Concentric Tube Robots.

Concentric tube robots, composed of nested pre-curved tubes, have the potential to perform minimally invasive surgery at difficult-to-reach sites in the human body. In order to plan motions that safely perform surgeries in constrained spaces that require avoiding sensitive structures, the ability to accurately estimate the entire shape of the robot is needed. Many state-of-the-art physics-based shape models are unable to account for complex physical phenomena and subsequently are less accurate than is required for safe surgery. In this work, we present a learned model that can estimate the entire shape of a concentric tube robot. The learned model is based on a deep neural network that is trained using a mixture of simulated and physical data. We evaluate multiple network architectures and demonstrate the model's ability to compute the full shape of a concentric tube robot with high accuracy.

STEERABLE NEEDLE TRAJECTORY FOLLOWING IN THE LUNG: TORSIONAL DEADBAND COMPENSATION AND FULL POSE ESTIMATION WITH 5DOF FEEDBACK FOR NEEDLES PASSING THROUGH FLEXIBLE ENDOSCOPES.

Bronchoscopic diagnosis and intervention in the lung is a new frontier for steerable needles, where they have the potential to enable minimally invasive, accurate access to small nodules that cannot be reliably accessed today. However, the curved, flexible bronchoscope requires a much longer needle than prior work has considered, with complex interactions between the needle and bronchoscope channel, introducing new challenges in steerable needle control. In particular, friction between the working channel and needle causes torsional windup along the bronchoscope, the effects of which cannot be directly measured at the tip of thin needles embedded with 5 degree-of-freedom magnetic tracking coils. To compensate for these effects, we propose a new torsional deadband-aware Extended Kalman Filter to estimate the full needle tip pose including the axial angle, which defines its steering direction. We use the Kalman Filter estimates with an established sliding mode controller to steer along desired trajectories in lung tissue. We demonstrate that this simple torsional deadband model is sufficient to account for the complex interactions between the needle and endoscope channel for control purposes. We measure mean final targeting error of 1.36 mm in phantom tissue and 1.84 mm in ex-vivo porcine lung, with mean trajectory following error of 1.28 mm and 1.10 mm, respectively.

Decoupling Steerability from Diameter: Helical Dovetail Laser Patterning for Steerable Needles.

The maximum curvature of a steerable needle in soft tissue is highly sensitive to needle shaft stiffness, which has motivated use of small diameter needles in the past. However, desired needle payloads constrain minimum shaft diameters, and shearing along the needle shaft can occur at small diameters and high curvatures. We provide a new way to adjust needle shaft stiffness (thereby enhancing maximum curvature, i.e. "steerability") at diameters selected based on needle payload requirements. We propose helical dovetail laser patterning to increase needle steerability without reducing shaft diameter. Experiments in phantoms and ex vivo animal muscle, brain, liver, and inflated lung tissues demonstrate high steerability in soft tissues. These experiments use needle diameters suitable for various clinical scenarios, and which have been previously limited by steering challenges without helical dovetail patterning. We show that steerable needle targeting remains accurate with established controllers and demonstrate interventional payload delivery (brachytherapy seeds and radiofrequency ablation) through the needle. Helical dovetail patterning decouples steerability from diameter in needle design. It enables diameter to be selected based on clinical requirements rather than being carefully tuned to tissue properties. These results pave the way for new sensors and interventional tools to be integrated into high-curvature steerable needles.

ResBoost: characterizing and predicting catalytic residues in enzymes.

BACKGROUND: Identifying the catalytic residues in enzymes can aid in understanding the molecular basis of an enzyme's function and has significant implications for designing new drugs, identifying genetic disorders, and engineering proteins with novel functions. Since experimentally determining catalytic sites is expensive, better computational methods for identifying catalytic residues are needed. RESULTS: We propose ResBoost, a new computational method to learn characteristics of catalytic residues. The method effectively selects and combines rules of thumb into a simple, easily interpretable logical expression that can be used for prediction. We formally define the rules of thumb that are often used to narrow the list of candidate residues, including residue evolutionary conservation, 3D clustering, solvent accessibility, and hydrophilicity. ResBoost builds on two methods from machine learning, the AdaBoost algorithm and Alternating Decision Trees, and provides precise control over the inherent trade-off between sensitivity and specificity. We evaluated ResBoost using cross-validation on a dataset of 100 enzymes from the hand-curated Catalytic Site Atlas (CSA). CONCLUSION: ResBoost achieved 85% sensitivity for a 9.8% false positive rate and 73% sensitivity for a 5.7% false positive rate. ResBoost reduces the number of false positives by up to 56% compared to the use of evolutionary conservation scoring alone. We also illustrate the ability of ResBoost to identify recently validated catalytic residues not listed in the CSA.

3D Motion Planning Algorithms for Steerable Needles Using Inverse Kinematics.

Steerable needles can be used in medical applications to reach targets behind sensitive or impenetrable areas. The kinematics of a steerable needle are nonholonomic and, in 2D, equivalent to a Dubins car with constant radius of curvature. In 3D, the needle can be interpreted as an airplane with constant speed and pitch rate, zero yaw, and controllable roll angle.We present a constant-time motion planning algorithm for steerable needles based on explicit geometric inverse kinematics similar to the classic Paden-Kahan subproblems. Reachability and path competitivity are analyzed using analytic comparisons with shortest path solutions for the Dubins car (for 2D) and numerical simulations (for 3D). We also present an algorithm for local path adaptation using null-space results from redundant manipulator theory. Finally, we discuss several ways to use and extend the inverse kinematics solution to generate needle paths that avoid obstacles.