Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

A Local-Global Planner for 3D Steerable Needle Insertion Based on the Stochastic Motion Roadmap and Screw-Based Motion Planning

View Current Project Information

Jijie Xu, Vincent Duindam, Ron Alterovitz and Ken Goldberg

Steerable needles are a new class of flexible medical needles that can be controlled from outside the human body to follow curved paths through human tissues, enabling them to reach targets inaccessible to traditional rigid needles. This project aims to explore motion planning for steerable needles to assist physicians inserting such needles into a 3D environment of tissues and reach a target without colliding with obstacles. We develop a local-global motion planner based on the Stochastic Motion Roadmap (SMR) framework and a screw-based geometric model of the needle. Given the initial entry configuration of the needle and the goal location, we randomly sample states in the 3D configuration space to select a set of nodes. To connect neighboring nodes and construct a roadmap, we apply a local planner that uses a twist representation of the needle tip's kinematics and an efficient control space discretization to quickly compute optimal local paths. Using the SMR framework, we explicitly consider uncertainty in the motion of the needle to generate a global planner that computes an optimal sequence of actions to steer the needle from the initial configuration to the goal configuration while minimizing the probability of colliding with an obstacle. With this local-global sampling-based motion planner, roadmap construction is computationally fast due to the control space discretization local planner. There is no need for an explicit model of the structure of the complex high-dimensional configuration space, and the method will compute needle steering actions that converge to the global optimum as the number of sampled states increases.

Figure 1
Figure 1: Finding the optimal path using a combination of local and global planning

V. Duindam, R. Alterovitz, S. Sastry, and K. Goldberg, "Screw-Based Motion Planning for Bevel-Tip Flexible Needles in 3D Environments with Obstacles," IEEE International Conference on Robotics and Automation, 2008 (submitted).
R. Alterovitz, T. Simeon, and K. Goldberg, "The Stochastic Motion Roadmap: A Sampling Framework for Planning with Markov Motion Uncertainty," Robotics: Science and Systems, June 2007.