DATE: | Wednesday, August 7th |
TIME: | 11:00 AM - 12:00 PM |
PLACE: | McConnell 320 |
TITLE: | Motion Planning for Knot Untangling |
SPEAKER: | Andrew Ladd, Rice University |
When given a very tangled but unknotted circular piece of string it is
usually quite easy to move it around and tug on parts of it until it
untangles. However solving this problem by computer, either exactly or
heuristically, is challenging. Various approaches have
been tried, employing ideas from algebra, geometry, topology and
optimization. This talk describes my recent work under Prof. Lydia
Kavraki on
applying motion planning techniques to the untangling of mathematical
knots.
Such an approach brings together robotics and knotting at the intersection
of
these fields: rational manipulation of a physical model. In the past,
simulated annealing and other energy minimization methods have been
used to find knot untangling paths for physical models. Using a
probabilistic planner, we have untangled some standard
benchmarks described by over four hundred variables much more
quickly than has been achieved with minimization. We also show how to
produce candidates with minimal number of segments for a given knot.
We discuss novel motion planning techniques that were used
in our approach and some possible applications of our untangling planner
in
computational topology and in the study of DNA rings.