Unknot

An implementation of the approach described in "Using Motion Planning for Knot Untangling" by Ladd and Kavraki [1] in C++. The main script is implemented in unknot.cc. Once compiled, it provides a few command line options:

./unknot \
  -f <input knot JSON> \
  -o <output trajectory JSON> \
  -s <specific random seed> \
  -v \ # Enable visualization
  -p   # Use the random planner rather than the heuristic search

Some basic unknots are provided in the resources/ folder as a JSON list of points:

• Lebrecht Goeritz's 11 crossing unknot (goeritz.json),
• Morwen Thistlethwaite's 15 crossing unknot (thistlewaite.json),
• Mitsuyuki Ochiai's 16 crossing unknot (ochiai.json)

All of these typically solve in under a second on my M2 Macbook Air. For example:

./build/unknot -f resources/goeritz.json -v

Will find a sequence of moves that untangles Goertitz's unknot using a simple application of heuristics and display them with a simple 3D visualizer. Visualization of the unknotting process is done using a simple implot3d display. The planner of [1] can be run by passing the -p argument to the script.

Compiling

Compile the script with CMake using Ninja (not necessary but recommended):

cmake -Bbuild -GNinja .
cmake --build build

CMake should pull down all dependencies besides Eigen 3. If for some reason visualization is throwing a fit (e.g., something with GLAD, GLFW, etc.), visualization can be disabled in the compilation with the flag UNKNOT_VIZ, e.g.,

cmake -Bbuild -GNinja -DUNKNOT_VIZ=OFF .
cmake --build build

Other Knot Stuff

I highly recommend looking at this post by Peter Prevos for some more information on unknotting. There is also the Wikipedia page on unknots and the unknotting problem. There is also these very helpful articles, [2] and [3] (see also the associated KnotPlot software).

Why?

This paper has been very compelling to me since I first discovered it! I love motion planning for wacky, high-dimensional things - thus, fun hobby project.

Maybe at some point in the future...

• Add more unknots (e.g., Wolfgang Haken's)
• Convert knot diagrams to ball-and-stick JSON
• Compare against other unknotting software
• Parallelism?

References

• [1] A. M. Ladd and L. E. Kavraki, "Using Motion Planning for Knot Untangling," International Journal of Robotics Research, vol. 23, no. 7-8, pp. 797–808, 2004. A preprint is available at this link.
• [2] Ligocki, Terry J., and James A. Sethian. "Recognizing knots using simulated annealing." Journal of Knot Theory and Its Ramifications 3.04 (1994): 477-495. A preprint is available at this link.
• [3] Scharein, Robert Glenn. Interactive topological drawing. Diss. University of British Columbia, 1998..