{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:00:17Z","timestamp":1777716017704,"version":"3.51.4"},"reference-count":49,"publisher":"SAGE Publications","issue":"7-8","license":[{"start":{"date-parts":[[2004,8,1]],"date-time":"2004-08-01T00:00:00Z","timestamp":1091318400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2004,8]]},"abstract":"<jats:p>In this paper we investigate the application of motion planning techniques to the untangling of mathematical knots. Knot untangling can be viewed as a high-dimensional planning problem in reparametrizable configuration spaces. In the past, simulated annealing and other energy minimization methods have been used to find knot untangling paths. We have developed a probabilistic planner that is capable of untangling knots described by over 400 variables. We have tested on known difficult benchmarks in this area and untangled them more quickly than has been achieved with minimization in the literature. In this work, the use of motion planning techniques is 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 a minimal number of segments for a given knot. The planner developed in this work is novel in that it is used to study issues arising in practical motion planning for high-dimensional and reparametrizable geometry. The use of energy methods, local goals and tree-based expansion is also novel and may suggest solutions in other planning applications. 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.<\/jats:p>","DOI":"10.1177\/0278364904045469","type":"journal-article","created":{"date-parts":[[2004,9,13]],"date-time":"2004-09-13T20:12:22Z","timestamp":1095106342000},"page":"797-808","source":"Crossref","is-referenced-by-count":40,"title":["Using Motion Planning for Knot Untangling"],"prefix":"10.1177","volume":"23","author":[{"given":"Andrew M.","family":"Ladd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lydia E.","family":"Kavraki","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, TX 77005, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2004,8,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Agol, I., Hass, J., and Thurston, W. 2002. 3-manifold knot genus is NP-complete . Annual ACM Symposium on Theory of Computing Proceedings of the 34th Annual ACM Symposium on Theory of Computing, Montreal, Canada, pp. 761\u2013766 .","DOI":"10.1145\/509907.510016"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"Anerizis, C. N. 1999. The Mystery of Knots \u2013 Computer Programming for Knot Tabulation, Series on Knots and Everything, World Scientific, Singapore .","DOI":"10.1142\/9789812796066"},{"key":"atypb3","unstructured":"Apaydin, M. S., Singh, A. P., Brutlag, D. L., and Latombe, J.C. 2001. Capturing molecular energy landscapes with probabilistic conformal roadmaps . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21\u201326."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Apaydin, M. S., Brutlag, D. L., Guestrin, C., Hsu, D., and Latombe, J.C. 2002. Stochastic roadmap simulation: An efficient representation and algorithm for analyzing molecular motion . International Conference on Computational Molecular Biology (RECOMB), Washington, DC, April.","DOI":"10.1145\/565196.565199"},{"key":"atypb5","unstructured":"Bayazit, O. B., Lien, J.M., and Amato, N. M. 2002. Probabilistic roadmap motion planning for deformable objects . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216500000323"},{"key":"atypb7","unstructured":"Bern, M. et al. 1999. Emerging challenges in computational topology. Preprint (math\/cs.CG\/9909001)."},{"key":"atypb8","unstructured":"Birman, J. S., Boldi, P., Rampichini, M., and Vigna, S. 2000. Towards an implementation of the b-h algorithm for recognizing the unknot. KNOTS-2000, Yongpyong Resort, Korea ."},{"key":"atypb9","unstructured":"Butler, Z., Kotay, K., Rus, D., and Tomita, K. 2001. Cellular automata for decentralized control of self-reconfigurable robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21\u201326."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1994.1671"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216501000846"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216500000402"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1101\/gad.872301"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216597000352"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Grzeszczuk, R. P., Huang, M., and Kauffman, L. H. 1996. Untangling knots by stochastic energy optimization. IEEE Visualization 1996, San Francisco, CA , pp. 279\u2013286.","DOI":"10.1109\/VISUAL.1996.568120"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/2945.620492"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-01-00358-7"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Hass, J., Lagarias, J. C., and Pippenger, N. 1997. The computational complexity of knot and link problems . 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, October 20\u201322, pp. 172\u2013181 .","DOI":"10.1109\/SFCS.1997.646106"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF03025227"},{"key":"atypb20","unstructured":"Hsu, D. 2000.\n                      Randomized Single-Query Motion Planning In Expansive Spaces\n                      , PhD thesis, Department of Computer Science, Stanford University."},{"key":"atypb21","unstructured":"Hsu, D., Latombe, J.C., and Motwani, R. 1997. Path planning in expansive spaces . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Albuquerque, NM, pp. 2719\u20132726 ."},{"key":"atypb22","unstructured":"Hsu, D., Kindel, R., Latombe, J.C., and Rock, S. 2001. Control-based randomized motion planning for dynamic environments. Algorithmic and Computational Robotics: New Directions: 4th International Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 247\u2013264."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"atypb24","unstructured":"Jenkins, R. 1989.\n                      A Dynamic Approach to Calculating the Homfly Polynomial for Directed Knots and Links\n                      , Master\u2019s thesis, Carnegie Mellon University."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216594000186"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb27","unstructured":"Kuffner, J. J., and LaValle, S. M. 1999. Randomized kinodynamic planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, pp. 473\u2013479 ."},{"key":"atypb28","unstructured":"Kuffner, J. J., and LaValle, S. M. 2000a. RRT-connect: an efficient approach to single-query path planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24\u201328."},{"key":"atypb29","unstructured":"Kuffner, J. J., and LaValle, S. M. 2000b. Rapidly exploring random trees: progress and prospects. Algorithmic and Computational Robotics: New Directions: 4th International Workshop on the Algorithmic Foundations of Robotics (WAFR), Hanover, NH , pp. 293\u2013308."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"atypb31","unstructured":"Ladd, A., and Kavraki, L. 2002. A measure theoretic analysis of PRM . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067354"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"Lickorish, W.B.R. 1997. An Introduction to Knot Theory, Springer-Verlag, Berlin .","DOI":"10.1007\/978-1-4612-0691-0"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216594000356"},{"key":"atypb35","unstructured":"Phillips, J., Ladd, A., and Kavraki, L. 2002. Simulated knot tying . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90005-X"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1521-1878(199910)21:10<805::AID-BIES1>3.0.CO;2-7"},{"key":"atypb38","unstructured":"S\u00e1nchez, G., and Latombe, J.C. 2001. A single-query bidirectional motion planner with lazy collision checking . Proceedings of International Symposium on Robotics, Seoul, Korea."},{"key":"atypb39","unstructured":"Scharein, R. 1988.\n                      Interactive Topological Drawing\n                      , PhD thesis, University of British Columbia."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1126\/science.8475384"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1142\/S0218216594000228"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1142\/S021821659400023X"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"Song, G., and Amato, N. 2001. Using motion planning to study protein folding pathways . International Conference on Computational Molecular Biology (RECOMB), Montreal, Canada, April, pp. 287\u2013296 .","DOI":"10.1145\/369133.369239"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1038\/384142a0"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/21\/7\/030"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"Teodoro, M., Phillips, G. N., and Kavraki, L. E. 2002. A dimensionality reduction approach to modeling protein flexibility . International Conference on Computational Molecular Biology (RECOMB), Washington, DC, April.","DOI":"10.1145\/565196.565235"},{"key":"atypb47","unstructured":"Vassilvitskii, S., Suh, J., and Yim, M. 2002. A complete, local and parallel reconfiguration algorithm for cube style modular robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315."},{"key":"atypb48","unstructured":"Walter, J., Tsai, B., and Amato, N. 2002. Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315."},{"key":"atypb49","unstructured":"Wu, Y.Q. 1996. Ming User Manual. See http:\/\/www.math.uiowa.edu\/wu\/ming\/ming.pdf."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045469","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:09Z","timestamp":1777457829000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364904045469"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8]]},"references-count":49,"journal-issue":{"issue":"7-8","published-print":{"date-parts":[[2004,8]]}},"alternative-id":["10.1177\/0278364904045469"],"URL":"https:\/\/doi.org\/10.1177\/0278364904045469","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8]]}}}