A. M. Ladd and L. E. Kavraki, “Motion Planning for Knot Untangling,” in Algorithmic Foundations of Robotics V, Springer Tracks in Advanced Robotics, Springer Verlag, STAR 7, 2004, pp. 7–23.
This paper investigates the application of motion planning techniques to the untangling of mathematical knots. Knot untangling can be viewed as a high-dimensional planning problem in reparameterizable configuration spaces. In the past, simulated annealing and other energy minimization methods have been used to find knot untangling paths. We develop a probabilistic planner that is capable of untangling knots described by over four hundred variables and known difficult benchmarks in this area more quickly than has been achieved with minimization in the literature. The use of motion planning techniques was critical for the untangling. Our planner defines local goals and makes combined use of energy minimization and randomized tree-based planning. We also show how to produce candidates with minimal number of segments for a given knot. Finally, we discuss some possible applications of our untangling planner in computational topology, in the study of DNA rings and protein folding and for planning with flexible robots.
Publisher: http://dx.doi.org/10.1007/b80173