Path Planning for Deformable Robots in Complex Environments

Russell Gayle1, William Segars2, Ming C. Lin1, Dinesh Manocha1

1: {rgayle,lin,dm}      2:

Liver chemoembolization

Resulting path for liver chemoembolization. The environment and robot are made up of over 90,000 triangles.

 We present an algorithm for path planning for a flexible robot in complex environments. Our algorithm computes a collision free path by taking into account geometric and physical constraints, including obstacle avoidance, non-penetration, volume preservation, surface tension, and energy minimization. We describe a new algorithm for collision detection between a deformable robot and fixed obstacles using graphics processors. We also present techniques to efficiently handle complex deformable models composed of tens of thousands of polygons and obtain significant performance improvements over previous approaches. Moreover, we demonstrate a practical application of our algorithm in performing path planning of catheters in liver chemoembolization.
Path Planning for Deformable Robots in Complex Environments
Russell Gayle, William Segars, Ming C. Lin, and Dinesh Manocha
Proceedings of  Robotics: Systems and Science, 2005
Paper: pdf (1.3MB)
Poster: ppt (available upon request)

Liver Chemoembolization:
Our benchmark application aids in a medical procedure called liver chemoembolization. In this procedure, a long but thin, flexible catheter must be inserted into the femoral artery. From there, it must be navigated to the hepatic arteries, where it must end up near a tumor in the liver. Once it reaches the tumor, a physician will inject chemotherapy drugs directly to the tumor. Accurate planning is necessary for a couple of reasons. Careful manipulation is required since the procedure can cause spasms which will impede fluid flow through the catheter. Planning can be used as a pre-operation step in order to decide on the best size and properties of the catheter.

Planner Highlights:
  • Improved constraint-based planning. This includes a more optimal set of constraints along with better formulations of other constraints. Angular sprngs have been added to aid in smooth deformations and more robust solvers have been used.
  • Graphics hardware optimiziations. GPU accelerated medial axis computation allows for a better initial trajectory path. In particular, we introduce a novel collision detection algorithm that performs efficient 2.5D overlap tests with GPUs. See below for an overview.
Collision Detection:
We introduce a novel collision detection algorithm for deformable robots in static but complex environments. It is based on 2.5D overlap test, which aid in determining if there is a separating surface of up to unit depth complexity between the robot and any obstacle. We implement this efficiently with graphics hardware rasterization capabilities. To ensure correctlness and scalable performance, we have developed a reliable test via Minkowski sums and perform set-based computations.

This chart describes the performance of our algorithm. Note that even though the complexity of the scene increases, the time for each simulation step does not change greatly.

Additional Media
Walls environment
The walls environment

Results Movie (30MB) - Shows examples of the computational domain, a real-time capture in our walls environment, and several views of the path playback and final path of the catheterizations (Requires divx codec)
Related Work
This work was supported in part by a Department of Energy High-Performance Computer Science Fellowship administered by the Krell Institute, ARO, NSF, AMSO, DARPA, ONR/VIRTE, and Intel Corporation.

Department of Computer Science
Campus Box 3175
UNC-Chapel Hill
Chapel Hill, NC 27599-3175