Show simple item record

dc.contributor.authorLadd, Andrew M.
Kavraki, Lydia E.
dc.date.accessioned 2017-08-02T22:02:58Z
dc.date.available 2017-08-02T22:02:58Z
dc.date.issued 2004-01-01
dc.identifier.urihttps://hdl.handle.net/1911/96304
dc.description.abstract 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 paper investigates the application of 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 algorithm and some possible applications of our untangling planner in computational topology and in the study of DNA rings.
dc.format.extent 21 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title Motion Planning for Knot Untangling
dc.type Technical report
dc.date.note January 1, 2004
dc.identifier.digital TR02-400
dc.type.dcmi Text
dc.identifier.citation Ladd, Andrew M. and Kavraki, Lydia E.. "Motion Planning for Knot Untangling." (2004) https://hdl.handle.net/1911/96304.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record