Weifu Wang
PhD candidate
Dartmouth Computer Science

Welcome! I'm a PhD candidate at Dartmouth Computer Science department studying robotics with Professor Devin Balkcom. I am currently working on my thesis titled "Constraint-based robot knot tying". You can check out some videos of our experiments here.


I am interested in locomotion, motion planning and deformable objects manipulation. I and my collaborators have studied robotic knot tying, string manipulation, memory-efficient motion planning, and exact optimal trajectories for vehicles.

Robotic knot tying and string manipulation

Our goal is to develop techniques that allow more interesting knots to be tied quickly and precisely, using limited sensing and control.

We have designed mechanical devices, fixtures, that guide the string into the correct shape when forces are applied by a motor or pressurized air. Some of these fixtures consist only of a single piece of molded plastic; other fixtures can be separated to allow extraction of more complex knots. We have also designed fixtures that are modular, and can be reconfigured to allow several different knots to be tied.

The first tying of simple knots using these mechanisms was explored in Matthew Bell's thesis; and extended to more complex knots. The most relevant papers are [Wang2016a], [Wang2015c], [Wang2015b], [Wang2014].

Tightening fixtures. Simple knots can be tied by pulling on the ends, but other knots tangle, or like the bow of a shoelace, even untie. Perhaps the best way to tie knots is to separate tying into two phases: arrangement and tightening. We have built some simple fixtures that allow knots to be tightened in a somewhat controlled fashion, and even embedded these tightening fixtures inside of arrangement fixtures to allow easy transition betweeen the phases. Controlling the tightening process allows the shoelace bow to be tied, as shown in the second movie above.

Precise and larger-scale tightening. The behavior of string is unpredictable; if the string is loose, it can become tangled, and if tight, friction with the fixture can cause jamming. We have started to build larger-scale fixtures in which the string is arranged around a tightening fixture made of a set of rods. The rods may themselves move to allow tightening, either passively actuated as taught string pulls on the rods, or using motors to spin the rods and apply forces at different places along the string. This approach allows full control of the string, and allows tightening in particular locations.

Knot folding. Most recently, we have been exploring foundational questions, using a model of knots inspired by the string game cat's cradle. For example, how many fingers are needed to grasp a piece of string in a particular knot shape? How many fingers are needed to tie a knot? Our initial explorations have determined some upper and lower bounds, but these remain open research questions.

String manipulation without simulating deformation. String deformation is difficult to predict and control. Using threading a string through small workspace openings (needle) as an example, we studied how to control string without simulating the deformation. Based on the Diminishing Jacobian developed by Professor Berenson, we designed virtual magnetic field as controller, and use computed approximated Jacobian to translate the desired motion of string into the change of locations for robot arms. Da Vinci surgical robot arm was used to demonstrate the precision and tolerance of the method. The paper [Wang2015b] is presented on ICRA.

Memory-efficient motion planning

As greater and greater computational power is applied to motion planning problems, memory becomes a bottleneck. How can we capture the essential qualities of a configuration space in a small memory-efficient representation that can be stored or transmitted across a network?

Graph spanners. In the algorithms community, graph spanning algorithms have been developed that allow some edges to be removed from a graph while maintaining a constant approximation ratio between paths in the original graph and in the reduced graph (the spanner). Marble, Dobson, and Bekris showed that a spanner algorithm could be applied to filter the output of a Probabilistic Roadmap (PRM) algorithm, reducing the number of edges stored. [Wang2015a] shows how online spanner algorithms can be adapted to PRMs, allowing sparse roadmaps to be generated very quickly (amortized constant time per edge), while maintaining approximation properties. Figures below, from left to right are 5-PRM, k-PRM* and the result of applying our spanner on k-PRM* roadmaps.

Optimal trajectories among obstacles. Early work by Xavier and Donald on kino-dynamic motion planning showed that requiring a robot to keep a certain safe distance from obstacles allows the problem of finding optimal trajectories to be well defined and provably solvable. [Balkcom2015] extends this idea to prove that even for systems with non-holonomic constraints, optimal trajectories that remain a certain distance from obstacles exist and can be approximated, if given a black box that can compute optimal trajectories without obstacles (an optimal steering method). While a fine-grained cell decomposition of the space still requires very much memory, we expect that weaker approximation requirements will lead to much more efficient representations.

Optimal trajectories

There are typically very many feasible paths between a pair of robot configurations. Which ones are the best? We have studied the optimal trajectory problem for simple systems, particularly mobile robots in the plane, and shown that for these simple systems, we can design algorithms that can be much better than more general motion planning approaches, in terms of computational cost, optimality of results, and provable correctness. We are starting to extend these algorithms to more general systems, while retaining some of their best characteristics. The middle figure below is a synthesis of different types of optimal trajectories of from (x, y, pi) to (0, 0, 0).

Generalized Dubins cars. Dubins and Reeds-Shepp steered cars, differential drives, and omni-directional vehicles can each be modeled as simple rigid bodies in the plane, with location and orientation. However, differences in mechanical designs lead to different constraints on velocities, and different optimal trajectories. [Furtuna2010] and Furtuna's Ph.D. thesis unify previous work in this area, by completely characterizing the time-optimal trajectories for a general model of rigid bodies in the plane, and developing general-purpose algorithms that can solve for optimal trajectories for these vehicles and variations. [Wang2012b] shows that the difficult inverse kinematics problems that sometimes arise in solving for optimal trajectories can be solved approximately with arbitrary precision. The right most figure above shows an optimal trajectory found by our algorithm for a non-symmetrical differential drive.

Tech Reports

(pdf) From grasping to folding polygonal knots.


Weifu Wang, Devin Balkcom:
Grasping and folding knots.
(pdf) Conference paper under review. 2016.
Weifu Wang, Devin Balkcom:
Tying knots precisely.
(pdf) Conference paper under review. 2016.
Weifu Wang, Devin Balkcom:
Towards arranging and tightening knots and unknots with fixtures.
IEEE Transactions on Automation Science and Engineering 12(4): (2015)
Devin Balkcom, Ajay Kannan, Yu-Han Lyu, Weifu Wang, Yinan Zhang:
Metric cells: towards complete search for optimal trajectories.
(pdf) IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2015.
Weifu Wang, Dmitry Berenson, Devin Balkcom:
An online method for tight-tolerance insertion tasks for string and rope.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2015.
Weifu Wang, Devin Balkcom, Amit Chakrabarti:
A fast online spanner for roadmap construction.
(pdf) International Journal of Robotics Research (2015)
Yu-Han Lyu, Andrei A. Furtuna, Weifu Wang, Devin Balkcom:
The bench mover's problem: minimum-time trajectories, with cost for switching between controls.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2014.
Matthew P. Bell, Weifu Wang (co-first author), Jordan Kunzika, Devin Balkcom:
Knot-tying with four-piece fixtures.
(pdf) International Journal of Robotics Research 33(11): 1481—1489 (2014)
Weifu Wang, Matthew Bell, Devin Balkcom:
Towards arranging and tightening knots and unknots with fixtures.
Algorithmic Foundations of Robotics (WAFR). 2014.
Weifu Wang, Devin Balkcom, Amit Chakrabarti:
A fast streaming spanner algorithm for incrementally constructing sparse roadmaps.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2013.
Andrei A. Furtuna, Weifu Wang, Yu-Han Lyu, Devin Balkcom:
Structure and geometry of minimum-time trajectories for planar rigid bodies.
Allerton Conference on Communication, Control, and Computing. 2013.
Weifu Wang, Devin Balkcom:
Sampling extremal trajectories for planar rigid bodies.
(pdf) Algorithmic Foundations of Robotics (WAFR). 2012.
Weifu Wang, Devin Balkcom:
Analytical time-optimal trajectories for an omni-directional vehicle.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2012.
Andrei A. Furtuna, Wenyu Lu, Weifu Wang, Devin Balkcom:
Minimum-time trajectories for kinematic mobile robots and other planar rigid bodies with finite control sets.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2011.