Kavraki Lab

Some of the current challenges at the frontiers of modern motion planning applications stem from high dimensional or even non-parametric configuration spaces, complex but `soft’ constraints on allowable motions imposed by the energetics of an underlying physical system and the possibility of innovative uses of planners for discovery. Recent problems of interest are daunting but may have a great deal of structure that can be exploited to sidestep the inherent complexity of high dimensional planning in constrained spaces. Motivating examples can be found in recent work on planning schemes for modular and reconfigurable robots planning for deformable robots, abstractions of random planning analysis to non-parametric, non-manifold spaces, approximate dimensionality reduction of configuration space, determining protein folding pathways, planning in the energy landscapes of molecules, and computing stationary distributions of Markov chains defined over roadmaps for analysis of Monte Carlo simulations of protein folding phenomena.

Untangling Ochiai and Results

This work deals with the knot untangling problem. A knot is a simple, closed piecewise linear curve and is called an unknot if there exists an ambient isotopy (piecewise linear homeomorphism of the space around the knot) transforming the knot to a triangle. Otherwise the knot is a non-trivial. The induced equivalence relation separate the knots into different classes that are called knot types. Our approach applies techniques from motion planning to find a sequence of motions and transformations that reduces the number of segments in a knot to the minimal number possible for that knot type. During these motions and transformations the topological type of the knot is preserved. When cast as a robotics problem, untangling is about manipulation of a high-dimensional, reparametrizable, deformable object possibly requiring many parameters to describe important configurations. The above figure illustrates some intermediate steps in the untangling of a tricky 133 segment knot.

Minimizing Stick Number for 16 Crossing Knot

We describe the design and implementation of a novel motion planner for knot untangling. We take the novel approach of decomposing the global untangling into sequence of local goals and reparametrization operations that, when taken together, determine a solution. Planning towards the local goals is achieved by combining energy minimization and randomized tree-based planning in the spirit of those employed by the RRT framework and expansive spaces framework. Our approach is minimalistic and we show that a simple planner suffices for solving this problem. We demonstrate the effectiveness of this planner by applying it to some standard benchmarks used in other implementations, some random knots and by finding minimal segment candidate for a sixteen crossing knot. Our experimental results are significantly better than comparable implementations in the literature. We also discuss how the techniques employed might be applied to other high dimensional motion planning problems such as those found in robotics approaches to molecular biology or in problems with deformable robots.