Path Planning for Deformable Objects

A central issue in our research is the development of physical algorithms, that is algorithms for solving problems in the physical world. Geometry is one important part of the picture; another crucial issue is physics!

We are studying some of the issues arising when the geometry of objects is combined with their physical properties by investigating the problem of planning paths for elastic (deformable) objects). Several application domains motivate our research such as:

Suturing
Virtual Prototyping
Manufacturing
"Purposive" Computer Graphics Animation
Computational Chemistry

Resolution Scheme

Our approach is composed of three elements:

Mechanical Model
A mechanical model specifies how the deformable object behaves when subjected to external actions. The curves shown in figure 1 and 2 are representing wires that do not stretch, but can bend and twist. In figure 3, our object is a plate made of an elastic material. In the fourth figure, the object is a bendable pipe. The fifth figure uses a colored strip to show the curvature (red) and torsion (green) of a spatial curve. The curvature and torsion determine the strain on the curve.
Geometric Representation
The space of deformations of an object is usually infinite dimensional. The goal of the geometric representation is to approximate this huge space by a finite-dimensional sub-space. Below we will describe in more detail the ongoing work on deformable curves. In previous work we investigated two other representations: finite elements and spring models. The pipe above is represented with a mass-spring model, specifically with a lattice of 21x3x3 mass points and several types of springs connecting them.
Path Planning
Once a mechanical model and a geometric representation are chosen, we can specify the deformation of the object by manipulation constraints. For instance, a rope or pipe can be grasped by the endpoints, and a plate can be grasped along two opposite edges. The shape of the object under manipulation constraints is computed by minimizing the strain or elastic energy. Once we know how to generate deformed configurations, we can plan a path using a high-level motion planner. This can be a simple planner like PRM or something more powerful like SRT (Sampling-based Roadmap of Trees).

Minimal-Energy Curves

Our current research efforts focus on `good' representations and path planning techniques for minimal-energy curves. The energy of a curve is defined as the integral of the curvature squared and the torsion squared along the curve. The energy can be thought of as the total strain on a wire.

A good representation for minimal-energy curves has the following desirable properties.

The size of the representation is small. As the number of parameters increases, the complexity of the path planning increases exponentially.
The representation is powerful enough to closely approximate true minimal-energy curves (in the variational sense).

These properties work against each other, so we need to find the right balance. The representation we came up with is described in a 2006 IEEE Trans. Robotics paper. To plan paths for minimal-energy curves we need to be able to solve two problems: (1) find a minimal-energy curve that satisfies given endpoint constraints, and (2) find deformations of one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. For the first problem we use a subdivision-based algorithm. It iteratively divides a curve into smaller and smaller segments of constant curvature and torsion so as to lower the energy while maintaining the endpoint constraints. At each iteration the parameters of the segment being subdivided are optimized to minimize the energy. The subdivision algorithm terminates when an energy minimum is found or when the segment length is below some threshold. The termination depends on the underlying `curve complexity': for a straight line or, say, a helix only very few parameters are necessary. The algorithm automatically finds a compact representation.

The path planning problem for minimal-energy curves is solved as follows. Suppose we have two minimal-energy curves that satisfy the start and goal constraints. We can linearly interpolate the start and goal curve segment parameters to obtain a curve in between them, close to the start curve. This curve is not a minimal-energy-curve, but we can downsample this curve to a coarse resolution and rerun our subdivision algorithm to turn it into a minimal-energy curve. If the resulting curve is still close to the start curve, and we have made progress towards the goal, then we recursively solve the problem of connecting the new minimal-energy curve to the goal.

If a wire collides with some obstacle, then a new constraint is introduced. We model this constraint by inserting an extra control point and tangent. Minimal-energy curves that pass through multiple control points and tangents are computed as follows. First, parts of the curve length are allocated to each consecutive pair of control points (proportional to the distance between them). Based on this initial allocation we find minimal-energy curves for each segment. The last step is then to perform a minimization of the total energy over the curve segment lengths.

In earlier work (see Lamiraux & Kavraki) we used a (more standard) finite element method to represent a deformable object and a heavy duty energy minimization over the finite elements. Using a modified version of standard PRM called f-PRM, we were able to plan motions for a flexible plate and a flexible pipe (see figures 3 and 4).

Other Related Work

Previously, we have also applied motion planning techniques to the untangling of geometric knots. This planner significantly outperformed other untangling implementations. In another project, we worked on the simulation of knot tying.

Movies

As an example, you can see a movie (24kb QuickTime) of a path computed by our planner. The elastic object is a plate subjected to bending. The profile curve of the plate is represented by a Bézier curve or a cubic spline.
Another (100k QuickTime)
And another (176k QuickTime)
We have also done some things with planning for deformable volumes, as seen here and in a movie here.