Author name cluster

Ron Alterovitz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

47 papers

2 author rows

ICRA Conference 2025 Conference Paper

A System for Endoscopic Submucosal Dissection Featuring Concentric Push-Pull Manipulators

Peter Connor
Carter Hatch
Khoa T. Dang
Tony Qin
Ron Alterovitz
D. Caleb Rucker
Robert J. Webster III

Endoscopic Submucosal Dissection (ESD) is an effective minimally invasive approach to removing colon cancer, yet it is underutilized, since it is challenging to learn and perform. To promote the adoption of ESD by making it easier, we propose a system in which two small, flexible robotic manipulators are delivered through a colonoscope. Our system differs from prior robotic systems aimed at this application in that our manipulators are small enough to fit through a clinically used colonoscope. By not re-engineering the colonoscope, we maintain overall system diameter at the current clinical gold standard, and streamline the path to eventual clinical deployment. Our concentric push-pull robot (CPPR) manipulators offer dexterity and simultaneously provide a conduit for grasper or cutting tool deployment. Each manipulator in our system consists of two push-pull tube pairs, and we describe how they are actuated. We describe for the first time our approach to compensating for undesirable CPPR tip motion induced by differences in the tubes' transmission stiffness. We also evaluate the workspace of the manipulators and demonstrate teleoperation in a point-touching experiment. Lastly, we demonstrate the ability of the system to resect tissue via ex vivo animal experiments.

ICRA Conference 2025 Conference Paper

On the Necessity of Real-Time Principles in GPU-Driven Autonomous Robots

Syed W. Ali
Angelos Angelopoulos
Denver Massey
Sarah Haddix
Alexander Georgiev
Joseph Goh
Rohan Wagle
Prakash Sarathy

Robot autonomy is driving an ever-increasing demand for computational power, including on-board multi-core CPUs and accelerators such as GPUs, to enable fast perception, planning, control, and more. Careful scheduling of these computational tasks on the CPU cores and GPUs is important to prevent locking up the finite computational capacity in ways that hinder other critical workloads; delays in computing time-critical tasks like obstacle detection and control can have huge negative consequences for autonomous robots, potentially resulting in damage, substantial financial loss, or even loss of life. In this paper, we leverage recent advances from real-time systems research. We apply TimeWall, a component-based real-time framework, to the computational components of an autonomous drone and experimentally show that the timeliness and safe operation properties of a drone are preserved even in the presence of increasing interfering computational processes.

ICRA Conference 2025 Conference Paper

Resolution Optimal Motion Planning for Medical Needle Steering from Airway Walls in the Lung

Janine Hoelscher
Inbar Fried
Oren Salzman
Ron Alterovitz

Steerable needles are novel medical devices capa-ble of following curved paths through tissue, enabling them to avoid anatomical obstacles and steer to hard-to-reach sites in tissue, including targets in the lung for lung cancer diagnosis. Steerable needles are typically deployed into tissue from an insertion surface, and selecting the insertion site is critical for procedure success as it determines which paths the needle can take to its target. Prior motion planners for steerable needles typically only plan from a specific start pose to the target. We introduce a new resolution-optimal steerable needle motion planner that efficiently finds plans from an insertion surface to a target position, handling additional degrees of freedom at both the start and the target. Our algorithm systematically builds a search tree consisting of needle motion primitives backward from the target towards the insertion surface, which allows it to provide an optimality guarantee up to the resolution of the primitives. The algorithm finds higher-quality plans faster than prior state-of-the-art motion planners, as demonstrated in anatomical scenario simulations in the lung.

ICRA Conference 2025 Conference Paper

The Experiment Orchestration System (EOS): Comprehensive Foundation for Laboratory Automation

Angelos Angelopoulos
Cem Baykal
Jade Kandel
Matthew Verber
James Cahoon
Ron Alterovitz

As scientific research in chemistry, materials science, and applied sciences becomes increasingly complex and data-driven, there is a growing need for efficient, scalable, and flexible automation to accelerate discoveries and reduce human burden and error in laboratories. We introduce the Experiment Orchestration System (EOS), an open-source software framework and runtime offering a comprehensive foundation for laboratory automation. EOS offers an extensible framework allowing users to define labs, devices, tasks, experiments, and optimization criteria using YAML and Python plugins, and also offers a distributed runtime for managing and executing automation. EOS has a central orchestrator that communicates with and controls laboratory equipment to execute tasks. EOS implements autonomous experiment campaigns, parameter optimization, task scheduling, result aggregation, and more. By providing a common infrastructure for laboratory automation, EOS aims to reduce automation implementation barriers and accelerate discoveries in science laboratories.

IROS Conference 2023 Conference Paper

High-Accuracy Injection Using a Mobile Manipulation Robot for Chemistry Lab Automation

Angelos Angelopoulos
Matthew Verber
Collin McKinney
James Cahoon
Ron Alterovitz

Lab automation has the potential to accelerate scientific progress in the natural sciences, allowing tedious experiments that would require many hours of human time to be automated, enabling higher accuracy, efficiency, and repeatability. Mobile manipulation robots have the potential to work in chemistry labs designed for humans to complete tasks for which setting up customized factory-scale automation is premature or infeasible. We present a new method to enable a mobile manipulation robot to automate injections, a common task in chemistry labs when using equipment such as gas chromatographs (GCs) for analyzing the contents of a sample mixture. This task is challenging for a mobile manipulation robot due to the need to navigate to the equipment in the lab and then achieve millimeter-scale accuracy required for the syringe positioning. Our approach leverages deep learning to create a model capable of localizing the syringe with high accuracy using cameras mounted on the chemistry equipment, and then uses a visual servoing approach based on the syringe's needle localization to achieve the injection. We demonstrate that our approach is robust to uncertainty in navigation as well as uncertainty in the grasping position and orientation of the syringe, achieving errors sufficiently small to enable the mobile manipulation robot to automate injections in real chemistry equipment.

IROS Conference 2023 Conference Paper

Landmark Based Bronchoscope Localization for Needle Insertion Under Respiratory Deformation

Inbar Fried
Janine Hoelscher
Jason A. Akulian
Stephen M. Pizer
Ron Alterovitz

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.

IROS Conference 2022 Conference Paper

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

Janine Hoelscher
Inbar Fried
Mengyu Fu
Mihir Patwardhan
Max Christman
Jason A. Akulian
Robert J. Webster III
Ron Alterovitz

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.

ICRA Conference 2022 Conference Paper

Resolution-Optimal Motion Planning for Steerable Needles

Mengyu Fu
Kiril Solovey
Oren Salzman
Ron Alterovitz

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.

ICRA Conference 2021 Conference Paper

Computationally-Efficient Roadmap-based Inspection Planning via Incremental Lazy Search

Mengyu Fu
Oren Salzman
Ron Alterovitz

The inspection-planning problem calls for computing motions for a robot that allow it to inspect a set of points of interest (POIs) while considering plan quality (e. g. , plan length). This problem has applications across many domains where robots can help with inspection, including infrastructure maintenance, construction, and surgery. Incremental Random Inspection-roadmap Search (IRIS) is an asymptotically-optimal inspection planner that was shown to compute higher-quality inspection plans orders of magnitudes faster than the prior state-of-the-art method. In this paper, we significantly accelerate the performance of IRIS to broaden its applicability to more challenging real-world applications. A key computational challenge that IRIS faces is effectively searching roadmaps for inspection plans—a procedure that dominates its running time. In this work, we show how to incorporate lazy edge-evaluation techniques into IRIS’s search algorithm and how to reuse search efforts when a roadmap undergoes local changes. These enhancements, which do not compromise IRIS’s asymptotic optimality, enable us to compute inspection plans much faster than the original IRIS. We apply IRIS with the enhancements to simulated bridge inspection and surgical inspection tasks and show that our new algorithm for some scenarios can compute similar-quality inspection plans 570× faster than prior work.

ICRA Conference 2021 Conference Paper

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

Inbar Fried
Janine Hoelscher
Mengyu Fu
Maxwell Emerson
Tayfun Efe Ertop
Margaret Rox
Josephine Granna
Alan Kuntz

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.

ICRA Conference 2020 Conference Paper

Enabling Robots to Understand Incomplete Natural Language Instructions Using Commonsense Reasoning

Haonan Chen
Hao Tan 0002
Alan Kuntz
Mohit Bansal
Ron Alterovitz

Enabling robots to understand instructions provided via spoken natural language would facilitate interaction between robots and people in a variety of settings in homes and workplaces. However, natural language instructions are often missing information that would be obvious to a human based on environmental context and common sense, and hence does not need to be explicitly stated. In this paper, we introduce Language-Model-based Commonsense Reasoning (LMCR), a new method which enables a robot to listen to a natural language instruction from a human, observe the environment around it, and automatically fill in information missing from the instruction using environmental context and a new commonsense reasoning approach. Our approach first converts an instruction provided as unconstrained natural language into a form that a robot can understand by parsing it into verb frames. Our approach then fills in missing information in the instruction by observing objects in its vicinity and leveraging commonsense reasoning. To learn commonsense reasoning automatically, our approach distills knowledge from large unstructured textual corpora by training a language model. Our results show the feasibility of a robot learning commonsense knowledge automatically from web-based textual corpora, and the power of learned commonsense reasoning models in enabling a robot to autonomously perform tasks based on incomplete natural language instructions.

ICRA Conference 2020 Conference Paper

Fog Robotics Algorithms for Distributed Motion Planning Using Lambda Serverless Computing

Jeffrey Ichnowski
William Lee
Victor Murta
Samuel Paradis
Ron Alterovitz
Joseph E. Gonzalez
Ion Stoica
Ken Goldberg

For robots using motion planning algorithms such as RRT and RRT*, the computational load can vary by orders of magnitude as the complexity of the local environment changes. To adaptively provide such computation, we propose Fog Robotics algorithms in which cloud-based serverless lambda computing provides parallel computation on demand. To use this parallelism, we propose novel motion planning algorithms that scale effectively with an increasing number of serverless computers. However, given that the allocation of computing is typically bounded by both monetary and time constraints, we show how prior learning can be used to efficiently allocate resources at runtime. We demonstrate the algorithms and application of learned parallel allocation in both simulation and with the Fetch commercial mobile manipulator using Amazon Lambda to complete a sequence of sporadically computationally intensive motion planning tasks.

ICRA Conference 2019 Conference Paper

Motion Planning Templates: A Motion Planning Framework for Robots with Low-power CPUs

Jeffrey Ichnowski
Ron Alterovitz

Motion Planning Templates (MPT) is a C++ template-based library that uses compile-time polymorphism to generate robot-specific motion planning code and is geared towards eking out as much performance as possible when running on the low-power CPU of a battery-powered small robot. To use MPT, developers of robot software write or leverage code specific to their robot platform and motion planning problem, and then have MPT generate a robot-specific motion planner and its associated data-structures. The resulting motion planner implementation is faster and uses less memory than general motion planning implementations based upon runtime polymorphism. While MPT loses runtime flexibility, it gains advantages associated with compile-time polymorphism- including the ability to change scalar precision, generate tightly-packed data structures, and store robot-specific data in the motion planning graph. MPT also uses compile-time algorithms to resolve the algorithm implementation, and select the best nearest neighbor algorithm to integrate into it. We demonstrate MPT's performance, lower memory footprint, and ability to adapt to varying robots in motion planning scenarios on a small humanoid robot and on 3D rigid-body motions.

IROS Conference 2019 Conference Paper

Multilevel Incremental Roadmap Spanners for Reactive Motion Planning

Jeffrey Ichnowski
Ron Alterovitz

Generating robot motions from a precomputed graph has proven to be an effective approach to solving many motion planning problems. After their generation, roadmaps reduce complex motion planning problems to that of solving a graph-based shortest path. However, generating the graph can involve tradeoffs, such as how sparse or dense to make the graph. Sparse graphs may not provide enough options to navigate around a new obstacle or may result in grossly suboptimal motions. Dense graphs may take too long to search and result in an unresponsive robot. In this paper we present an algorithm that generates a graph with multiple sparse levels– the sparsest level can be searched quickly, while the densest level allows for asymptotically optimal motions. With the paired multilevel shortest path algorithm, after the robot computes an initial solution, it can then incrementally refine the shortest-path as time allows. We demonstrate the algorithms on an articulated robot with 8 degrees of freedom, having them compute an initial solution in a fraction of the time required for a full graph search, and subsequently, incrementally refine the solution to the optimal shortest path from the densest level of the graph.

IROS Conference 2019 Conference Paper

optimizing Motion-Planning Problem Setup via Bounded Evaluation with Application to Following Surgical Trajectories

Sherdil Niyaz
Alan Kuntz
Oren Salzman
Ron Alterovitz
Siddhartha S. Srinivasa

A motion-planning problem’s setup can drastically affect the quality of solutions returned by the planner. In this work we consider optimizing these setups, with a focus on doing so in a computationally-efficient fashion. Our approach interleaves optimization with motion planning, which allows us to consider the actual motions required of the robot. Similar prior work has treated the planner as a black box: our key insight is that opening this box in a simple-yet-effective manner enables a more efficient approach, by allowing us to bound the work done by the planner to optimizer-relevant computations. Finally, we apply our approach to a surgically-relevant motion-planning task, where our experiments validate our approach by more-efficiently optimizing the fixed insertion pose of a surgical robot.

IROS Conference 2019 Conference Paper

Planning High-Quality Motions for Concentric Tube Robots in Point Clouds via Parallel Sampling and optimization

Alan Kuntz
Mengyu Fu
Ron Alterovitz

We present a method that plans motions for a concentric tube robot to automatically reach surgical targets inside the body while avoiding obstacles, where the patient’s anatomy is represented by point clouds. Point clouds can be generated intra-operatively via endoscopic instruments, enabling the system to update obstacle representations over time as the patient anatomy changes during surgery. Our new motion planning method uses a combination of sampling-based motion planning methods and local optimization to efficiently handle point cloud data and quickly compute high quality plans. The local optimization step uses an interior point optimization method, ensuring that the computed plan is feasible and avoids obstacles at every iteration. This enables the motion planner to run in an anytime fashion, i. e. , the method can be stopped at any time and the best solution found up until that point is returned. We demonstrate the method’s efficacy in three anatomical scenarios, including two generated from endoscopic videos of real patient anatomy.

ICRA Conference 2018 Conference Paper

Kinematic Design Optimization of a Parallel Surgical Robot to Maximize Anatomical Visibility via Motion Planning

Alan Kuntz
Chris Bowen
Cenk Baykal
Arthur W. Mahoney
Patrick L. Anderson
Fabien Maldonado
Robert J. Webster III
Ron Alterovitz

We introduce a method to optimize on a patient-specific basis the kinematic design of the Continuum Reconfigurable Incisionless Surgical Parallel (CRISP) robot, a needle-diameter medical robot based on a parallel structure that is capable of performing minimally invasive procedures. Our objective is to maximize the ability of the robot's tip camera to view tissue surfaces in constrained spaces. The kinematic design of the CRISP robot, which greatly influences its ability to perform a task, includes parameters that are fixed before the procedure begins, such as entry points into the body and parallel structure connection points. We combine a global stochastic optimization algorithm, Adaptive Simulated Annealing (ASA), with a motion planner designed specifically for the CRISP robot. ASA facilitates exploration of the robot's design space while the motion planner enables evaluation of candidate designs based on their ability to successfully view target regions on a tissue surface. By leveraging motion planning, we ensure that the evaluation of a design only considers motions which do not collide with the patient's anatomy. We analytically show that the method asymptotically converges to a globally optimal solution and demonstrate our algorithm's ability to optimize kinematic designs of the CRISP robot on a patient-specific basis.

IROS Conference 2018 Conference Paper

Safe Motion Planning for Steerable Needles Using Cost Maps Automatically Extracted from Pulmonary Images

Mengyu Fu
Alan Kuntz
Robert J. Webster III
Ron Alterovitz

Lung cancer is the deadliest form of cancer, and early diagnosis is critical to favorable survival rates. Definitive diagnosis of lung cancer typically requires needle biopsy. Common lung nodule biopsy approaches either carry significant risk or are incapable of accessing large regions of the lung, such as in the periphery. Deploying a steerable needle from a bronchoscope and steering through the lung allows for safe biopsy while improving the accessibility of lung nodules in the lung periphery. In this work, we present a method for extracting a cost map automatically from pulmonary CT images, and utilizing the cost map to efficiently plan safe motions for a steerable needle through the lung. The cost map encodes obstacles that should be avoided, such as the lung pleura, bronchial tubes, and large blood vessels, and additionally formulates a cost for the rest of the lung which corresponds to an approximate likelihood that a blood vessel exists at each location in the anatomy. We then present a motion planning approach that utilizes the cost map to generate paths that minimize accumulated cost while safely reaching a goal location in the lung.

IROS Conference 2017 Conference Paper

Motion planning for continuum reconfigurable incisionless surgical parallel robots

Alan Kuntz
Arthur W. Mahoney
Nicolas E. Peckman
Patrick L. Anderson
Fabien Maldonado
Robert J. Webster III
Ron Alterovitz

Continuum Reconfigurable Incisionless Surgical Parallel (CRISP) robots consist of multiple needle-diameter flexible instruments that are assembled into a parallel structure inside the human body. With a camera placed at the tip of one of the instruments, the CRISP robot can be used to inspect anatomical sites in constrained body cavities in a minimally invasive manner. We introduce a motion planner for CRISP robots that computes manipulations of the flexible instruments outside the body such that the camera can visually inspect a user-specified site of clinical interest inside the body. Our sampling-based motion planner ensures avoidance of collisions with anatomical obstacles inside the body, enforces remote-center-of-motion constraints on the instrument's entry points into the body, and efficiently handles the expensive computation of CRISP robot kinematics. We also extend the motion planner to estimate the set of points inside a body cavity that can be visually inspected by the camera of a CRISP robot for a given setup. We demonstrate our method in a simulated endoscopic medical procedure in the pleural space around a lung.

ICRA Conference 2015 Conference Paper

A motion planning approach to automatic obstacle avoidance during concentric tube robot teleoperation

Luis G. Torres
Alan Kuntz
Hunter B. Gilbert
Philip J. Swaney
Richard J. Hendrick
Robert J. Webster III
Ron Alterovitz

Concentric tube robots are thin, tentacle-like devices that can move along curved paths and can potentially enable new, less invasive surgical procedures. Safe and effective operation of this type of robot requires that the robot's shaft avoid sensitive anatomical structures (e. g. , critical vessels and organs) while the surgeon teleoperates the robot's tip. However, the robot's unintuitive kinematics makes it difficult for a human user to manually ensure obstacle avoidance along the entire tentacle-like shape of the robot's shaft. We present a motion planning approach for concentric tube robot teleoperation that enables the robot to interactively maneuver its tip to points selected by a user while automatically avoiding obstacles along its shaft. We achieve automatic collision avoidance by precomputing a roadmap of collision-free robot configurations based on a description of the anatomical obstacles, which are attainable via volumetric medical imaging. We also mitigate the effects of kinematic modeling error in reaching the goal positions by adjusting motions based on robot tip position sensing. We evaluate our motion planner on a teleoperated concentric tube robot and demonstrate its obstacle avoidance and accuracy in environments with tubular obstacles.

IROS Conference 2015 Conference Paper

Motion planning for a three-stage multilumen transoral lung access system

Alan Kuntz
Luis G. Torres
Richard H. Feins
Robert J. Webster III
Ron Alterovitz

Lung cancer is the leading cause of cancer-related death, and early-stage diagnosis is critical to survival. Biopsy is typically required for a definitive diagnosis, but current low-risk clinical options for lung biopsy cannot access all biopsy sites. We introduce a motion planner for a multilumen transoral lung access system, a new system that has the potential to perform safe biopsies anywhere in the lung, which could enable more effective early-stage diagnosis of lung cancer. The system consists of three stages in which a bronchoscope is deployed transorally to the lung, a concentric tube robot pierces through the bronchial tubes into the lung parenchyma, and a steerable needle deploys through a properly oriented concentric tube and steers through the lung parenchyma to the target site while avoiding anatomical obstacles such as significant blood vessels. A sampling-based motion planner computes actions for each stage of the system and considers the coupling of the stages in an efficient manner. We demonstrate the motion planner's fast performance and ability to compute plans with high clearance from obstacles in simulated anatomical scenarios.

IROS Conference 2015 Conference Paper

Optimizing design parameters for sets of concentric tube robots using sampling-based motion planning

Cenk Baykal
Luis G. Torres
Ron Alterovitz

Concentric tube robots are tentacle-like medical robots that can bend around anatomical obstacles to access hard-to-reach clinical targets. The component tubes of these robots can be swapped prior to performing a task in order to customize the robot's behavior and reachable workspace. Optimizing a robot's design by appropriately selecting tube parameters can improve the robot's effectiveness on a procedure- and patient-specific basis. In this paper, we present an algorithm that generates sets of concentric tube robot designs that can collectively maximize the reachable percentage of a given goal region in the human body. Our algorithm combines a search in the design space of a concentric tube robot using a global optimization method with a sampling-based motion planner in the robot's configuration space in order to find sets of designs that enable motions to goal regions while avoiding contact with anatomical obstacles. We demonstrate the effectiveness of our algorithm in a simulated scenario based on lung anatomy.

ICRA Conference 2015 Conference Paper

Tendons, concentric tubes, and a bevel tip: Three steerable robots in one transoral lung access system

Philip J. Swaney
Arthur W. Mahoney
Andria A. Remirez
Erik Lamers
Bryan I. Hartley
Richard H. Feins
Ron Alterovitz
Robert J. Webster III

Lung cancer is the most deadly form of cancer, and survival depends on early-stage diagnosis and treatment. Transoral access is preferable to traditional between-the-ribs needle insertion because it is less invasive and reduces risk of lung collapse. Yet many sites in the peripheral zones of the lung or distant from the bronchi cannot currently be accessed transorally, due to the relatively large diameter and lack of sufficient steerablity of current instrumentation. To remedy this, we propose a new robotic system that uses a tendon-actuated device (bronchoscope) as a first stage for deploying a concentric tube robot, which itself is a vehicle through which a bevel steered needle can be introduced into the soft tissue of the lung outside the bronchi. In this paper we present the various components of the system and the workflow we envision for deploying the robot to a target using image guidance. We describe initial validation experiments in which we puncture ex vivo bronchial wall tissue and also target a nodule in a phantom with an average final tip error of 0. 72 mm.

ICRA Conference 2014 Conference Paper

Cache-aware asymptotically-optimal sampling-based motion planning

Jeffrey Ichnowski
Jan F. Prins
Ron Alterovitz

We present CARRT* (Cache-Aware Rapidly Exploring Random Tree*), an asymptotically optimal sampling-based motion planner that significantly reduces motion planning computation time by effectively utilizing the cache memory hierarchy of modern central processing units (CPUs). CARRT* can account for the CPU's cache size in a manner that keeps its working dataset in the cache. The motion planner progressively subdivides the robot's configuration space into smaller regions as the number of configuration samples rises. By focusing configuration exploration in a region for periods of time, nearest neighbor searching is accelerated since the working dataset is small enough to fit in the cache. CARRT* also rewires the motion planning graph in a manner that complements the cache-aware subdivision strategy to more quickly refine the motion planning graph toward optimality. We demonstrate the performance benefit of our cache-aware motion planning approach for scenarios involving a point robot as well as the Rethink Robotics Baxter robot.

IROS Conference 2014 Conference Paper

Closed-loop global motion planning for reactive execution of learned tasks

Chris Bowen
Ron Alterovitz

We present a motion planning approach for performing a learned task while avoiding obstacles and reacting to the movement of task-relevant objects. We employ a closed-loop sampling-based motion planner that acquires new sensor information, generates new collision-free plans that are based on a learned task model, and replans at an average rate of more than 10 times per second for a 7-DOF manipulator. The task model is learned from expert demonstrations prior to task execution and is represented as a hidden Markov model. During task execution, our motion planner quickly searches in the Cartesian product of the task model and a probabilistic roadmap for a plan with features most similar to the demonstrations given the locations of the task-relevant objects. We improve the replan rate by using a fast bidirectional search and by biasing the sampling distribution using information from the learned task model to construct high-quality roadmaps. We illustrate the efficacy of our approach by performing a simulated navigation task with a 2D point robot and a physical powder transfer task with the Baxter robot.

ICRA Conference 2014 Conference Paper

Interactive-rate motion planning for concentric tube robots

Luis G. Torres
Cenk Baykal
Ron Alterovitz

Concentric tube robots may enable new, safer minimally invasive surgical procedures by moving along curved paths to reach difficult-to-reach sites in a patient's anatomy. Operating these devices is challenging due to their complex, unintuitive kinematics and the need to avoid sensitive structures in the anatomy. In this paper, we present a motion planning method that computes collision-free motion plans for concentric tube robots at interactive rates. Our method's high speed enables a user to continuously and freely move the robot's tip while the motion planner ensures that the robot's shaft does not collide with any anatomical obstacles. Our approach uses a highly accurate mechanical model of tube interactions, which is important since small movements of the tip position may require large changes in the shape of the device's shaft. Our motion planner achieves its high speed and accuracy by combining offline precomputation of a collision-free roadmap with online position control. We demonstrate our interactive planner in a simulated neurosurgical scenario where a user guides the robot's tip through the environment while the robot automatically avoids collisions with the anatomical obstacles.

ICRA Conference 2014 Conference Paper

Motion planning for paramagnetic microparticles under motion and sensing uncertainty

Wen Sun 0002
Islam S. M. Khalil
Sarthak Misra
Ron Alterovitz

Paramagnetic microparticles moving through fluids have the potential to be used in many applications, including microassembly, micromanipulation, and highly localized delivery of therapeutic agents inside the human body. Paramagnetic microparticles with diameters of approximately 100 μm can be wirelessly controlled by externally applying magnetic field gradients using electromagnets. In this paper, we introduce a motion planner to guide a spherical paramagnetic microparticle to a target while avoiding obstacles. The motion planner explicitly considers uncertainty in the microparticle's motion and maximizes the probability that the microparticle avoids obstacle collisions and reaches the target. To enable effective consideration of uncertainty, we use an Expectation Maximization (EM) algorithm to learn a stochastic model of the uncertainty in microparticle motion and state sensing from experiments conducted in a 3D 8-electromagnet microparticle testbed. We apply the motion planner in a simulated 3D environment with static obstacles and demonstrate that the computed plans are more likely to result in task success than plans based on traditional metrics such as shortest path or maximum clearance.

IROS Conference 2014 Conference Paper

Motion planning under uncertainty for medical needle steering using optimization in belief space

Wen Sun 0002
Ron Alterovitz

We present an optimization-based motion planner for medical steerable needles that explicitly considers motion and sensing uncertainty while guiding the needle to a target in 3D anatomy. Motion planning for needle steering is challenging because the needle is a nonholonomic and underactuated system, the needle's motion may be perturbed during insertion due to unmodeled needle/tissue interactions, and medical sensing modalities such as ultrasound imaging and x-ray projection imaging typically provide only noisy and partial state information. To account for these uncertainties, we introduce a motion planner that computes a trajectory and corresponding linear controller in the belief space - the space of distributions over the state space. We formulate the needle steering motion planning problem as a partially observable Markov decision process (POMDP) that approximates belief states as Gaussians. We then compute a locally optimal trajectory and corresponding controller that minimize in belief space a cost function that considers avoidance of obstacles, penalties for unsafe control inputs, and target acquisition accuracy. We apply the motion planner to simulated scenarios and show that local optimization in belief space enables us to compute higher quality plans compared to planning solely in the needle's state space.

ICRA Conference 2014 Conference Paper

Needle steering in biological tissue using ultrasound-based online curvature estimation

Pedro Moreira
Sachin Patil
Ron Alterovitz
Sarthak Misra

Percutaneous needle insertions are commonly performed for diagnostic and therapeutic purposes. Accurate placement of the needle tip is important to the success of many needle procedures. The current needle steering systems depend on needle-tissue-specific data, such as maximum curvature, that is unavailable prior to an interventional procedure. In this paper, we present a novel three-dimensional adaptive steering method for flexible bevel-tipped needles that is capable of performing accurate tip placement without previous knowledge about needle curvature. The method steers the needle by integrating duty-cycled needle steering, online curvature estimation, ultrasound-based needle tracking, and sampling-based motion planning. The needle curvature estimation is performed online and used to adapt the path and duty cycling. We evaluated the method using experiments in a homogenous gelatin phantom, a two-layer gelatin phantom, and a biological tissue phantom composed of a gelatin layer and in vitro chicken tissue. In all experiments, virtual obstacles and targets move in order to represent the disturbances that might occur due to tissue deformation and physiological processes. The average targeting error using our new adaptive method is 40% lower than using the conventional non-adaptive duty-cycled needle steering method.

ICRA Conference 2013 Conference Paper

Continuous shape estimation of continuum robots using X-ray images

Edgar J. Lobaton
Jinghua Fu
Luis G. Torres
Ron Alterovitz

We present a new method for continuously and accurately estimating the shape of a continuum robot during a medical procedure using a small number of X-ray projection images (e. g. , radiographs or fluoroscopy images). Continuum robots have curvilinear structure, enabling them to maneuver through constrained spaces by bending around obstacles. Accurately estimating the robot's shape continuously over time is crucial for the success of procedures that require avoidance of anatomical obstacles and sensitive tissues. Online shape estimation of a continuum robot is complicated by uncertainty in its kinematic model, movement of the robot during the procedure, noise in X-ray images, and the clinical need to minimize the number of X-ray images acquired. Our new method integrates kinematics models of the robot with data extracted from an optimally selected set of X-ray projection images. Our method represents the shape of the continuum robot over time as a deformable surface which can be described as a linear combination of time and space basis functions. We take advantage of probabilistic priors and numeric optimization to select optimal camera configurations, thus minimizing the expected shape estimation error. We evaluate our method using simulated concentric tube robot procedures and demonstrate that obtaining between 3 and 10 images from viewpoints selected by our method enables online shape estimation with errors significantly lower than using the kinematic model alone or using randomly spaced viewpoints.

AAAI Conference 2012 Conference Paper

Efficient Approximate Value Iteration for Continuous Gaussian POMDPs

Jur van den Berg
Sachin Patil
Ron Alterovitz

We introduce a highly efficient method for solving continuous partially-observable Markov decision processes (POMDPs) in which beliefs can be modeled using Gaussian distributions over the state space. Our method enables fast solutions to sequential decision making under uncertainty for a variety of problems involving noisy or incomplete observations and stochastic actions. We present an efficient approach to compute locally-valid approximations to the value function over continuous spaces in time polynomial (O[n4 ]) in the dimension n of the state space. To directly tackle the intractability of solving general POMDPs, we leverage the assumption that beliefs are Gaussian distributions over the state space, approximate the belief update using an extended Kalman filter (EKF), and represent the value function by a function that is quadratic in the mean and linear in the variance of the belief. Our approach iterates towards a linear control policy over the state space that is locally-optimal with respect to a user defined cost function, and is approximately valid in the vicinity of a nominal trajectory through belief space. We demonstrate the scalability and potential of our approach on problems inspired by robot navigation under uncertainty for state spaces of up to 128 dimensions.

ICRA Conference 2012 Conference Paper

Estimating probability of collision for safe motion planning under Gaussian motion and sensing uncertainty

Sachin Patil
Jur van den Berg
Ron Alterovitz

We present a fast, analytical method for estimating the probability of collision of a motion plan for a mobile robot operating under the assumptions of Gaussian motion and sensing uncertainty. Estimating the probability of collision is an integral step in many algorithms for motion planning under uncertainty and is crucial for characterizing the safety of motion plans. Our method is computationally fast, enabling its use in online motion planning, and provides conservative estimates to promote safety. To improve accuracy, we use a novel method to truncate estimated a priori state distributions to account for the fact that the probability of collision at each stage along a plan is conditioned on the previous stages being collision free. Our method can be directly applied within a variety of existing motion planners to improve their performance and the quality of computed plans. We apply our method to a car-like mobile robot with second order dynamics and to a steerable medical needle in 3D and demonstrate that our method for estimating the probability of collision is orders of magnitude faster than naïve Monte Carlo sampling methods and reduces estimation error by more than 25% compared to prior methods.

IROS Conference 2012 Conference Paper

Parallel sampling-based motion planning with superlinear speedup

Jeffrey Ichnowski
Ron Alterovitz

We present PRRT (Parallel RRT) and PRRT* (Parallel RRT*), sampling-based methods for feasible and optimal motion planning that are tailored to execute on modern multi-core CPUs. Our algorithmic improvements enable PRRT and PRRT* to achieve a superlinear speedup: when p processor cores are used instead of 1 processor core, computation time is sped up by a factor greater than p. To achieve this superlinear speedup, our algorithms utilize three key features: (1) lock-free parallelism using atomic operations to eliminate slowdowns caused by lock overhead and contention, (2) partition-based sampling to reduce the size of each processor core's working data set to improve cache efficiency, and (3) parallel backtracking to reduce the number of rewiring steps performed in PRRT*. Our parallel algorithms retain the ability to integrate with existing CPU-based libraries and algorithms. We demonstrate fast performance and superlinear speedups in two scenarios: (1) a holonomic disc-shaped robot moving in a planar environment and (2) an Aldebaran Nao small humanoid robot performing a 2-handed manipulation task using 10 DOF.

IROS Conference 2012 Conference Paper

Task-oriented design of concentric tube robots using mechanics-based models

Luis G. Torres
Robert J. Webster III
Ron Alterovitz

We introduce a method for task-oriented design of concentric tube robots, which are tentacle-like robots with the potential to enable new minimally invasive surgical procedures. Our objective is to create a robot design on a patient-specific and surgery-specific basis to enable the robot to reach multiple clinically relevant sites while avoiding anatomical obstacles. Our method uses a mechanically accurate model of concentric tube robot kinematics that considers a robot's time-varying shape throughout the performance of a task. Our method combines a search over a robot's design space with sampling-based motion planning over its configuration space to compute a design under which the robot can feasibly perform a specified task without damaging surrounding tissues. To accelerate the algorithm, we leverage design coherence, the observation that collision-free configuration spaces of robots of similar designs are similar. If a solution exists, our method is guaranteed, as time is allowed to increase, to find a design and corresponding feasible motion plan. We provide examples illustrating the importance of using mechanically accurate models during design and motion planning and demonstrating our method's effectiveness in a medically motivated simulated scenario involving navigation through the lung.

IROS Conference 2011 Conference Paper

Motion planning for concentric tube robots using mechanics-based models

Luis G. Torres
Ron Alterovitz

Concentric tube robots have the potential to enable new minimally invasive surgical procedures by curving around anatomical obstacles to reach difficult-to-reach sites in body cavities. Planning motions for these devices is challenging in part due to their complex kinematics; concentric tube robots are composed of thin, pre-curved, telescoping tubes that can achieve a variety of shapes via extension and rotation of each of their constituent tubes. We introduce a new motion planner to maneuver these devices to clinical targets while minimizing the probability of colliding with anatomical obstacles. Unlike prior planners for these devices, we more accurately model device shape using mechanics-based models that consider torsional interaction between the tubes. We also account for the effects of uncertainty in actuation and predicted device shape. We integrate these models with a sampling-based approach based on the Rapidly-Exploring Roadmap to guarantee finding optimal plans as computation time is allowed to increase. We demonstrate our motion planner in simulation using a variety of evaluation scenarios including an anatomy-based neurosurgery case that requires maneuvering to a di#cult-to-reach brain tumor at the skull base.

ICRA Conference 2011 Conference Paper

Planning curvature-constrained paths to multiple goals using circle sampling

Edgar J. Lobaton
Jinghe Zhang
Sachin Patil
Ron Alterovitz

We present a new sampling-based method for planning optimal, collision-free, curvature-constrained paths for nonholonomic robots to visit multiple goals in any order. Rather than sampling configurations as in standard sampling based planners, we construct a roadmap by sampling circles of constant curvature and then generating feasible transitions between the sampled circles. We provide a closed-form formula for connecting the sampled circles in 2D and generalize the approach to 3D workspaces. We then formulate the multi goal planning problem as finding a minimum directed Steiner tree over the roadmap. Since optimally solving the multi-goal planning problem requires exponential time, we propose greedy heuristics to efficiently compute a path that visits multiple goals. We apply the planner in the context of medical needle steering where the needle tip must reach multiple goals in soft tissue, a common requirement for clinical procedures such as biopsies, drug delivery, and brachytherapy cancer treatment. We demonstrate that our multi-goal planner significantly decreases tissue that must be cut when compared to sequential execution of single-goal plans.

ICRA Conference 2011 Conference Paper

Rapidly-exploring roadmaps: Weighing exploration vs. refinement in optimal motion planning

Ron Alterovitz
Sachin Patil
Anna Derbakova

Computing globally optimal motion plans requires exploring the configuration space to identify reachable free space regions as well as refining understanding of already explored regions to find better paths. We present the rapidly-exploring roadmap (RRM), a new method for single-query optimal motion planning that allows the user to explicitly consider the trade-off between exploration and refinement. RRM initially explores the configuration space like a rapidly exploring random tree (RRT). Once a path is found, RRM uses a user-specified parameter to weigh whether to explore further or to refine the explored space by adding edges to the current roadmap to find higher quality paths in the explored space. Unlike prior methods, RRM does not focus solely on exploration or refine prematurely. We demonstrate the performance of RRM and the trade-off between exploration and refinement using two examples, a point robot moving in a plane and a concentric tube robot capable of following curved trajectories inside patient anatomy for minimally invasive medical procedures.

ICRA Conference 2010 Conference Paper

Planning active cannula configurations through tubular anatomy

Lisa A. Lyons
Robert J. Webster III
Ron Alterovitz

Medical procedures such as lung biopsy and brachytherapy require maneuvering through tubular structures such as the trachea and bronchi to reach clinical targets. We introduce a new method to plan configurations for active cannulas, medical devices composed of thin, pre-curved, telescoping lumens that are capable of following controlled, curved paths through open or liquid-filled cavities. Planning optimal configurations for these devices is challenging due to their complex kinematics, which involve both beam mechanics and space curves. In this paper, we propose an optimization-based planning algorithm that computes active cannula configurations through tubular structures that reach specified targets. Given the target location, the start position and orientation, and a geometric representation of the physical environment extracted from pre-procedure medical images, the planner optimizes insertion length and orientation angle of each lumen of the active cannula. The planner models active cannula kinematics using a physically-based simulation that incorporates beam mechanics and minimizes energy. The algorithm typically computes plans in less than 2 minutes on a standard PC. We apply the method in simulation to anatomy extracted from a human CT scan and demonstrate configurations for a 5-lumen active cannula that maneuver it through the bronchi to targets in the lung.

ICRA Conference 2010 Conference Paper

Toward automated tissue retraction in robot-assisted surgery

Sachin Patil
Ron Alterovitz

Robotic surgical assistants are enhancing physician performance, enabling physicians to perform more delicate and precise minimally invasive surgery. However, these devices are currently tele-operated and lack autonomy. In this paper, we present initial steps toward automating a commonly performed surgical task, tissue retraction, which involves grasping and lifting a thin layer of tissue to expose an underlying area. Given a model of tissues in the vicinity, our method computes a motion plan for a 6-DOF gripper that grasps a tissue flap at an optimal location and retracts it such that an underlying target is fully visible. The planner considers three optimization objectives relevant to medical applications: minimizing the maximum deformation energy, minimizing maximum stress, and minimizing the control effort in lifting the tissue flap. The planner can be used to locally improve physician specified retraction trajectories based on the optimization criteria or to compute a de novo plan. We use a physically-based simulation to compute equilibrium configurations of the tissue flap subject to manipulation constraints. These configurations are used with a sampling-based planner to explore the space of deformations and compute an optimal plan subject to discretization and modeling error. Our experimental results illustrate the ability of the method to compute retractions for heterogeneous tissues while avoiding obstacles and minimizing tissue damage.

ICRA Conference 2009 Conference Paper

Guiding medical needles using single-point tissue manipulation

Meysam Torabi
Kris Hauser
Ron Alterovitz
Vincent Duindam
Ken Goldberg

This paper addresses the use of robotic tissue manipulation in medical needle insertion procedures to improve targeting accuracy and to help avoid damaging sensitive tissues. To control these multiple, potentially competing objectives, we present a phased controller that operates one manipulator at a time using closed-loop imaging feedback. We present an automated procedure planning technique that uses tissue geometry to select the needle insertion location, manipulation locations, and controller parameters. The planner uses a stochastic optimization of a cost function that includes tissue stress and robustness to disturbances. We demonstrate the system on 2D tissues simulated with a mass-spring model, including a simulation of a prostate brachytherapy procedure. It can reduce targeting errors from more than 2 cm to less than 1 mm, and can also shift obstacles by over 1 cm to clear them away from the needle path.

IROS Conference 2009 Conference Paper

Motion planning for active cannulas

Lisa A. Lyons
Robert J. Webster III
Ron Alterovitz

An active cannula is a medical device composed of thin, pre-curved, telescoping tubes that may enable many new surgical procedures. Planning optimal motions for these devices is challenging due to their kinematics, which involve both beam mechanics and space curves. In this paper, we propose an optimization-based motion planning algorithm that computes actions to guide the device to a target point while avoiding obstacles in the environment. The planner uses a simplified active cannula kinematic model that neglects beam mechanics, and focuses on planning for the (piecewise circular) space curves. The method is intended for use in image-guided procedures where the target and obstacles can be segmented from pre-procedure images. Given the target location, the start position and orientation, and a geometric representation of obstacles, the algorithm computes the insertion length and orientation angle for each tube of the active cannula such that the device follows a collision-free path to the target. We formulate the planning problem as a constrained nonlinear optimization problem and use a penalty method to convert this formulation into a sequence of more easily solvable unconstrained optimization problems. Simulations demonstrate optimal paths for a 3-tube active cannula with spherical obstacles. The algorithm typically computes plans in less than 1 minute on a standard PC.

IROS Conference 2009 Conference Paper

Planning fireworks trajectories for steerable medical needles to reduce patient trauma

Jijie Xu
Vincent Duindam
Ron Alterovitz
Jean Pouliot
J. Adam M. Cunha
I-Chow Hsu
Ken Goldberg

Accurate insertion of needles to targets in 3D anatomy is required for numerous medical procedures. To reduce patient trauma, a ¿fireworks¿ needle insertion approach can be used in which multiple needles are inserted from a single small region on the patient's skin to multiple targets in the tissue. In this paper, we explore motion planning for ¿fireworks¿ needle insertion in 3D environments by developing an algorithm based on Rapidly-exploring Random Trees (RRTs). Given a set of targets, we propose an algorithm to quickly explore the configuration space by building a forest of RRTs and to find feasible plans for multiple steerable needles from a single entry region. We present two path selection algorithms with different optimality considerations to optimize the final plan among all feasible outputs. Finally, we demonstrate the performance of the proposed algorithm with a simulation based on a prostate cancer treatment environment.

ICRA Conference 2008 Conference Paper

Screw-based motion planning for bevel-tip flexible needles in 3D environments with obstacles

Vincent Duindam
Ron Alterovitz
S. Shankar Sastry
Ken Goldberg

Bevel-tip flexible needles have greater mobility than straight rigid needles, and can be used to reach targets behind sensitive or impenetrable areas. Accurately planning and executing the optimal motions for such steerable needles is difficult, however, and requires solving inverse kinematics for a nonholonomic system. This paper presents an approach to 3D motion planning for bevel-tip needles in an environment with obstacles. Instead of discretizing the configuration space as in earlier work, we discretize the control space, such that the trajectory of the needle can be expressed analytically without the need for approximate numerical simulation. This results in a fast optimization routine that finds a locally optimal path in a 3D environment with obstacles, requiring just a few seconds of computation time on a standard PC. We introduce two different discretization strategies that lead to differently structured paths and show that both produce valid trajectories from start to goal. To our knowledge, the presented method is the first to address motion planning for bevel-tip needles in a 3D environment with obstacles.

ICRA Conference 2005 Conference Paper

Planning for Steerable Bevel-tip Needle Insertion Through 2D Soft Tissue with Obstacles

Ron Alterovitz
Ken Goldberg
Allison M. Okamura

We explore motion planning for a new class of highly flexible bevel-tip medical needles that can be steered to previously unreachable targets in soft tissue. Planning for these procedures is difficult because the needles bend during insertion and cause the surrounding soft tissues to displace and deform. In this paper, we develop a planning algorithm for insertion of highly flexible bevel-tip needles into soft tissues with obstacles in a 2D imaging plane. Given an initial needle insertion plan specifying location, orientation, bevel rotation, and insertion distance, the planner combines soft tissue modeling and numerical optimization to generate a needle insertion plan that compensates for simulated tissue de formations, locally avoids polygonal obstacles, and minimizes needle insertion distance. The simulator computes soft tissue deformations using a finite element model that incorporates the effects of needle tip and frictional forces using a 2D mesh. We formulate the planning problem as a constrained nonlinear optimization problem that is locally minimized using a penalty method that converts the formulation to a sequence of unconstrained optimization problems. We apply the planner to bevel-right and bevel-left needles and generate plans for targets that are unreachable by rigid needles.

IROS Conference 2005 Conference Paper

Steering flexible needles under Markov motion uncertainty

Ron Alterovitz
Andrew E. B. Lim
Ken Goldberg
Gregory S. Chirikjian
Allison M. Okamura

When inserted into soft tissues, flexible needles with bevel tips have been shown experimentally to follow a path of constant curvature in the direction of the bevel. By controlling 2 degrees of freedom at the needle base (bevel direction and insertion distance), these needles can be steered around obstacles to reach targets inaccessible to rigid needles. Motion planning for needle steering is a type of nonholonomic planning for a Dubins car with no reversal. We develop a motion planning algorithm based on dynamic programming where the path of the needle is uncertain due to uncertainty in tissue properties, needle mechanics, and interaction forces. The algorithm computes a discrete control sequence of insertions and direction changes so the needle reaches a target in an imaging plane while minimizing expected cost due to insertion distance, direction changes, and obstacle collisions. We efficiently sample the state space of needle tip positions and orientations and define bounds on the errors due to discretization. We formulate the motion planning problem as a Markov decision process (MDP) and use infinite horizon dynamic programming to compute an optimal control sequence. We first apply the method to the deterministic motion case where the needle precisely follows a path of constant curvature and then to the uncertain motion case where state transitions are defined by a probability distribution. Our implementation generates motion plans for bevel-tip needles that reach targets inaccessible to rigid needles and demonstrates that accounting for uncertainty can lead to significantly different motion plans.

ICRA Conference 2003 Conference Paper

Needle insertion and radioactive seed implantation in human tissues: simulation and sensitivity analysis

Ron Alterovitz
Ken Goldberg
Jean Pouliot
Richard Tascherau
I-Chow Hsu

To facilitate training and planning for medical procedures such as prostate brachytherapy, we are developing an interactive simulation of needle insertion and radioactive seed implantation in soft tissues. We describe a new 2D dynamic FEM model based on a reduced set of scalar parameters such as needle friction, sharpness, and velocity, where the mesh is updated to maintain element boundaries along the needle shaft and the effects of needle tip and frictional forces are simulated. The computational complexity of our model grows linearly with the number of elements in the mesh and achieves 24 frames per second for 1250 triangular elements on a 750 MHz PC. We use the simulator to characterize the sensitivity of seed placement error to physician-controlled and biological parameters. Results indicate that seed placement error is highly sensitive to physician-controlled parameters such as needle position, sharpness, and friction, and less sensitive to patient-specific parameters such as tissue stiffness and compressibility.

IROS Conference 2003 Conference Paper

Sensorless planning for medical needle insertion procedures

Ron Alterovitz
Ken Goldberg
Jean Pouliot
Richard Tascherau
I-Chow Hsu

Medical procedures such as seed implantation, biopsies, and treatment injections require inserting a needle tip to a specific target location inside the human body. This is difficult because (1) needle insertion causes soft tissues to displace and deform, and (2) it is often difficult or impossible to obtain precise imaging data during insertion. We are developing a sensorless planning system for needle insertion that incorporates numerical optimization with a soft tissue simulation based on a dynamic FEM formulation that models the effects of needle tip and frictional forces using a 2D mesh. In this paper we describe a sensorless planning algorithm for radioactive seed implantation that computes needle insertion offsets that compensate for tissue deformations. We apply the method to seed implantation during permanent seed prostate brachytherapy to minimize seed placement error in simulation without relying on real-time imaging.