Simplifying knots

A knot is a closed curve that does not intersect itself, is embedded in ${\mathbb{R}}^3$, and cannot be untangled to produce a simple loop (such as a circular path). If the knot is allowed to intersect itself, then any knot can be untangled; therefore, a careful definition of what it means to untangle a knot is needed. For a closed curve, $\tau: [0,1] \rightarrow {\mathbb{R}}^3$, embedded in ${\mathbb{R}}^3$ (it cannot intersect itself), let the set ${\mathbb{R}}^3 \setminus \tau([0,1])$ of points not reached by the curve be called the ambient space of $\tau$. In knot theory, an ambient isotopy between two closed curves, $\tau_1$ and $\tau_2$, embedded in ${\mathbb{R}}^3$ is a homeomorphism between their ambient spaces. Intuitively, this means that $\tau_1$ can be warped into $\tau_2$ without allowing any self-intersections. Therefore, determining whether two loops are equivalent seems closely related to motion planning. Such equivalence gives rise to groups that characterize the space of knots and are closely related to the fundamental group described in Section 4.1.3. For more information on knot theory, see [8,451,511].

A motion planning approach was developed in [571] to determine whether a closed curve is equivalent to the unknot, which is completely untangled. This can be expressed as a curve that maps onto ${\mathbb{S}}^1$, embedded in ${\mathbb{R}}^3$. The algorithm takes as input a knot expressed as a circular chain of line segments embedded in ${\mathbb{R}}^3$. In this case, the unknot can be expressed as a triangle in ${\mathbb{R}}^3$. One of the most challenging examples solved by the planner is shown in Figure 7.31. The planner is sampling-based and shares many similarities with the RDT algorithm of Section 5.5 and the Ariadne's clew and expansive space planners described in Section 5.4.4. Since the task is not to produce a collision-free path, there are several unique aspects in comparison to motion planning. An energy function is defined over the collection of segments to try to guide the search toward simpler configurations. There are two kinds of local operations that are made by the planner: 1) Try to move a vertex toward a selected subgoal in the ambient space. This is obtained by using random sampling to grow a search tree. 2) Try to delete a vertex, and connect the neighboring vertices by a straight line. If no collision occurs along the intermediate configurations, then the knot has been simplified. The algorithm terminates when it is unable to further simplify the knot.

Figure 7.31: The planner in [571] untangles the famous Ochiai unknot benchmark in a few minutes on a standard PC.