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:
- Virtual Prototyping
- "Purposive" Computer Graphics Animation
- Computational Chemistry
Our approach is composed of three elements:
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.
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
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).
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
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 size of the representation is small. As the number of
parameters increases, the complexity of the path planning
- The representation is powerful enough to closely approximate
true minimal-energy curves (in the variational sense).
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.
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
We have also done some things with planning for deformable
volumes, as seen here
and in a
Figure 1. A minimal-energy path between
Figure 2. A minimal-energy curve passing
control points and tangents
Figure 3. An elastic plate
Figure 4. A flexible pipe
Figure 5. A strip highlighting curvature
and torsion in a spatial curve