Sage Journals: Discover world-class research

Abstract

This paper analyzes the physical resources necessary and sufficient to tie a knot of given structure. We present the first sufficient bound on the number of fingers required to tie a given knot; the bound is linear in the number of crossings appearing in the knot diagram for a given knot. We also present a lower bound on the required number of fingers, under a particular model of knot tying. We study how many re-grasps are sufficient to tie an arbitrary knot, and present an algorithm that can yield a small sufficient number of re-grasps to tie the given knot. Physical experiments in which different knots are tied and untied by robots, alone and in collaboration with a human, serve as a proof of concept to show the simplicity and correctness of the approach.

Keywords

Manipulation flexible objects knot tying

Get full access to this article

View all access options for this article.

References

Adams

(2004) The knot book: an elementary introduction to the mathematical theory of knots. Providence, RI: American Mathematical Society.

Agarwal

Sharir

(1998) Arrangements and their applications. In: Handbook of Computational Geometry. Amsterdam: Elsevier, pp. 49–119.

Armstrong

(1983) Basic Topology. New York: Springer-Verlag.

Ashton

Cantarella

Piatek

Rawdon

(2011) Knot tightening by constrained gradient descent. Experimental Mathematics 20(1): 57–90.

Attaway

(1999) The mechanics of friction in rope rescue. In International Technical Rescue Symposium.

Balkcom

Trinkle

Gottlieb

(2002) Computing wrench cones for planar contact tasks. In: ICRA. Piscataway, NJ: IEEE, pp. 869–875.

Baranska

Przybyl

Pieranski

(2008) Curvature and torsion of the tight closed trefoil knot. The European Physical Journal B - Condensed Matter and Complex Systems 66(4): 547–556.

Bell

(2010) Flexible object manipulation. Technical Report TR2010-663, Dartmouth College, Computer Science, Hanover, NH. Available at: http://www.cs.dartmouth.edu/reports/TR2010-663.pdf (accessed: 6 January 2018).

Bell

Wang

Kunzika

Balkcom

. Knot-tying with four-piece fixtures. The International Journal of Robotics Research 33: 1481–1489.

10.

Berard

Egan

Trinkle

(2004) Contact modes and complementary cones. In Proceedings of ICRA, pp. 5280–5286.

11.

Biedl

Demaine

et al . (1999) Locked and unlocked polygonal chains in 3D. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17–19 January 1999, Baltimore, MD, pp. 866–867.

12.

Bretl

McCarthy

(2014) Quasi-static manipulation of a Kirchhoff elastic rod based on a geometric analysis of equilibrium configurations. The International Journal of Robotics Research 33: 48–68.

13.

Burde

(1978) Knoten. Jahrbuch Ueberblicke Mathematik 1978: 131–147.

14.

Carlen

Laurie

Maddocks

Smutny

(2005) Biarcs, global radius of curvature, and the computation of ideal knot shapes. Physical and Numerical Models in Knot Theory (Series on Knots and Everything, vol. 36). Singapore: World Scientific, pp. 75–108.

15.

Crowell

Fox

(1977) Introduction to knot theory. Berlin: Springer-Verlag.

16.

Demaine

Hawksley

et al . (2010) Making polygons by simple folds and one straight cut. In: Revised Papers from the China–Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Dalian, China ( Lecture Notes in Computer Science, vol. 7033). Berlin: Springer, pp. 27–43.

17.

Hopcroft

Kearney

Krafft

(1991) A case study of flexible object manipulation. International Journal of Robotics Research 10(1): 41–50.

18.

Huffman

(1971) Impossible objects as nonsense sentences. Machine Intelligence 6(1971): 295–323.

19.

Huffman

(1976) Curvature and Creases: A primer on paper. IEEE Transactions on Computers 25(10): 1010–1019.

20.

Huffman

(1977) Realizable configurations of lines in pictures of polyhedra. Machine Intelligence 8(1971): 493–509.

21.

Inoue

Inaba

(1985) Hand-eye coordination in rope handling. In Robotics Research: The First International Symposium, pp. 163–174.

22.

Kanade

(1980) A theory of origami world. Artificial Intelligence 13(3): 279–311.

23.

Kauffman

(1991) Knots and Physics ( K & E Series on Knots and Everything). Singapore: World Scientific.

24.

Ladd

Kavraki

(2004) Using motion planning for knot untangling. The International Journal of Robotics Research 23(7–8): 797–808.

25.

Livingston

(1993) Knot theory ( The Carus Mathematical Monographs, vol. 24). Washington DC: The Mathematical Association of America.

26.

Lui

Saxena

(2013) Tangled: Learning to untangle ropes with RGB-D perception. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, Tokyo, Japan, 3–7 November 2013, pp. 837–844.

27.

Mason

(2001) Mechanics of Robotic Manipulation. Cambridge, MA: MIT Press.

28.

Manturov

(2004) Knot Theory. Boca Raton, FL: CRC Press.

29.

Matsuno

Fukuda

(2006) Manipulation of flexible rope using topological model based on sensor information. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2006), Beijing, China, 9–15 October 2006, pp. 2638–2643.

30.

Mishra

Schwartz

Sharir

(1987a) On the existence and synthesis of multifinger positive grips. Algorithmica 2(1): 541–558.

31.

Mishra

Schwartz

Sharir

(1987b) On the existence and synthesis of multifinger positive grips. Algorithmica 2: 541–558.

32.

Pai

(2002) Strands: Interactive simulation of thin solids using Cosserat models. Computer Graphics Forum 21(3): 347–352.

33.

Rawdon

(1998) Approximating the thickness of a knot. Ideal knots ( Series on Knots and Everything, vol. 19). Singapore: World Scientific, pp. 143–150.

34.

Reidemeister

(1927) Elementare begründung der knotentheorie. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 5(1): 24–32.

35.

Rimon

Blake

(1999) Caging planar bodies by one-parameter two-fingered gripping systems. The International Journal of Robotics Reseseach 18(3): 299–318.

36.

Rimon

Burdick

(1995) New bounds on the number of frictionless fingers required to immobilize 2D objects. In: IEEE International conference on Robotics and Automation, Nagoya, Aichi, Japan, pp. 751–757.

37.

Rimon

van der Stappen

(2012) Immobilizing 2-d serial chains in form-closure grasps. IEEE Transactions on Robotics 28(1): 32–43.

38.

Saha

Isto

(2006) Motion planning for robotic manipulation of deformable linear objects. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 2478–2484.

39.

Saha

Isto

(2007) Manipulation planning for deformable linear objects. IEEE Transaction on Robotics 23(6): 1141–1150.

40.

Saha

Isto

Latombe

J.-C.

(2006) Motion planning for robotic knot tying. In Proceedings of the International Symposium on Experimental Robotics, July 2006.

41.

Takamatsu

Morita

Ogawara

Kimura

Ikeuchi

(2006) Representation for knot-tying tasks. In: Proceedings IEEE International Conference on Robotics and Automation, vol. 22, pp. 65–78.

42.

Wakamatsu

Arai

Hirai

(2006) Knotting/unknotting manipulation of deformable linear objects. The International Journal of Robotics Research 25: 371–395.

43.

Waltz

(1972) Generating Semantic Descriptions From Drawings of Scenes With Shadows, Massachusetts Institute of Technology, Cambridge, MA, USA. Available at: http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail&id=oai%3Ancstrlh%3Amitai%3AMIT-AILab%2F%2FAITR-271.

44.

Wang

Balkcom

(2016) Grasping and folding knots. In: IEEE International Conference on Intelligent Robots and Systems (ICRA), pp. 3647–3654.

45.

Wang

Bell

Balkcom

. Towards arranging and tightening knots and unknots with fixtures. International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014), pp. 677–694.

46.

Wang

Berenson

Balkcom

DJ.

An online method for tight-tolerance insertion tasks for string and rope. In IEEE International Conference on Robotics and Automation, (ICRA 2015), Seattle, WA, 26–30 May 2015, pp. 2488–2495.

Knot grasping,folding,and re-grasping

Abstract

Keywords

Get full access to this article

References