Accelerated needle steering using partitioned value iteration

This paper presents a fast 2D motion planner for steering flexible needles inside relatively rigid tissue. This approach exploits a nonholonomic system approach, which models tissue-needle interaction, and formulates the problem as a Markov Decision Process that is solvable using infinite horizon Dynamic Programming. Starting from any initial condition defined in the workspace, this method calculates a set of control actions that enables the needle to reach the target and avoid collisions with obstacles. Unlike conventional solvers, e.g. the value iterator, which suffers from the curse of dimensionality, partitioned-based solvers show promising numerical performance. Given a segmented image of a workspace including the locations of the obstacles, the target and the entry point, the partitioned-based solver provides a descent solution where high resolution is required. It is shown in this paper how prioritized partitioning increases computational performance of the current DP-based solutions for the purpose of off-line path planning. By default, our planner selects the path with the least number of turning points while maintaining minimum insertion length, which leads to the least damage to tissue. In this paper, more emphasis is given to the control aspects of the problem rather than the corresponding biomedical issues.