I'm an associate professor (tenured 2010) in the Computer Science department at Dartmouth college. You can reach me at firstname.lastname@dartmouth.edu, and my office is 206 Sudikoff.

I graduated with a Ph.D. in robotics from Carnegie Mellon University in 2004; my research advisor was Matt Mason. I was awarded an NSF CAREER grant in 2006, the Dartmouth McLane Family Fellowship in 2010, and the Dartmouth John M. Manley Huntington Award in 2010.

At Dartmouth, I have taught classes including Introduction to Computer Science, Software Design and Implementation, Artificial Intelligence, and Robotics. I led the design of our new Computer Science 1 course, which teaches problem-solving with Python programming, basic algorithms, and data structures. For several years, I offered a summer robotics camp for local middle-school and high-school students.

Khan Academy now has algorithms tutorials for which Tom Cormen and I produced content.

Research

I am interested in the mechanics of locomotion and manipulation -- the interface between robots and the physical world. I and my collaborators have studied robotic knot tying, memory-efficient motion planning, exact optimal trajectories for vehicles, and laundry and origami folding.

My research has been supported by NSF grants IIS 1217447, IIS 1451632 , IIS 0643476, and CNS 0708209, and by the Institute for Security Technology Studies and the Neukom Institute. Current and former graduate students include Yinan Zhang, Weifu Wang, Yu-Han Lyu, Zhong Li, Dr. Andrei Furtuna, Dr. Paritosh Kavathekar, Dr. Matthew Bell, Wenyu Lu, Govind Krishnan, Wei Zhang, Anne Loomis Thompson.

Robotic knot tying and string manipulation

Sewing and weaving machines revolutionized the clothing industry in the 18th and 19th centuries, but the state of the art in general robotic manipulation of string suggests that there is still much to be learned. Much of the existing work focuses on tying faily simple knots using one or two robot hands. 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; most of the recent work on extending these ideas to more complex knots was by Weifu Wang. The most relevant papers are [Wang2015d], [Wang2015c], [Wang2015b], [Bell2014], [Wang2014], [Li2013].

One-piece fixtures. It is easy to build a fixture that will tie a simple overhand knot. Make a tube in the shape of the tied knot, and feed the string through the tube. The challenge is how to extract the knot from the fixture -- when the string is pulled from the tube, the knot is untied. One solution is to exploit the difference between pushing and pulling. When string or wire is pulled, it tightens, and slides along a particular section of the tube. When pushed, string or wire slides along a different part of the tube. By cutting and removing the section of tube where the string touches when pulled, Bell was able to build a fixture that allows wire to be tied into a knot during insertion, and extracted from the fixture without unknotting.

Four-piece arrangement fixtures. To tie more complex knots, we have also built fixtures that can be taken apart to extract the knot. We have formally proven that no matter how complicated the knot, and no matter how many pieces of string are involved, there exists a fixture that can be taken apart into four pieces, using simple translations, to expose the knot. The key idea of the proof is the realization that any knot can be loosely laid-out on a planar surface, in the shape of a mathematical knot diagram. (Thanks to Yuliy Baryshnikov for the important observation that pieces of the fixture could be pulled from the sides to allow for transitions from over- to under- crossings.) We have also shown that you can arrange knots around any set of vertical cylindrical rods, and with some weak conditions on the placements of the rods, can remove a six-piece fixture from the rods and string using simple translations.

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.

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.

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.

Diversity and survival. We expect that even approximately representing all shortest paths in a space will require significant memory, since every point in the configuration space is on the shortest path to somewhere. What if we only wanted to represent the general shape of the space? Promising recent work in the community (for example, by Bhattacharya) has developed algorithms for computing paths based on homotopy or homology of paths. However, topology is not a perfect tool for studying diversity, since it ignores some geometric consideration (such as the size of obstacles) entirely. We have started to study the problem of survival of several robots traversing an unknown minefield, and early work by Lyu has shown that optimizing the probability that at least one robot survives can force the robots to take interestingly diverse paths.

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.

Differential drives and omni-directional vehicles. [Balkcom2002a] describes analytically the time-optimal trajectories for two-wheeled differential drive vehicles, analogously to work by Dubins that describes shortest paths for steered cars. [Balkcom2006a] characterizes the time-optimal trajectories for a common type of omnidirectional vehicle, and shows that in fact, it can be faster to parallel park an omnidirectional vehicle, if the vehicle moves more quickly in some directions than others. [Wang2012a] extends this work to show an analytical method for solving for an optimal trajectory given a particular start and goal. This movie shows a sequence of motions for an omni-directional robot; short subsections of this trajectory are time-optimal between their start and end configurations.

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.

Optimal trajectories with switching costs. A fundamental difficulty in optimal control is that for some systems, optimal trajectories may not even exist. Consider the problem of moving a heavy park bench. Imagine that we can lift the bench at either end, and rotate around the side that is still on the ground. We can move from one end of the bench to the other, rotating successively around either end. What's the fastest way to move the bench forwards? If there is no cost for switching between sides of the bench, the mover should run back and forth between the two ends infinitely many times, rotating the bench through infinitessimal angles with each move. Similar problems arise for the Reeds-Shepp car among obstacles. Chattering behavior exposes a weakness in the mathematical model of a system. [Lyu2015] shows that if a simple fixed cost is be associated with switches between controls, optimal trajectories can still be characterized and computed, while avoiding chattering, even among obstacles.

Robotic folding of cloth and paper

We have built and programmed devices to fold cloth and paper, and proven results about how many hands are needed to completely immobilize a section of cloth so that it can be folded.

In fact, it is quite easy for a robot to fold laundry. The video below shows an industrial robot folding a t-shirt; the idea for the device is based on the very fun Japanese t-shirt folding video (second video), and the entire demo was put together and programmed in less than a week by student Matthew Bell. Even simpler hinged structures could fold the t-shirt just as well. The real challenge lies in understanding how to manipulate and flatten cloth that is intially crumpled.

Grasping cloth. Folding a flag usually requires two soldiers, since rectangular flags have four corners, all of which must be grasped to hold the flag rigid. But what if the flag (like the flag of Nepal) is not rectangular? Using ideas inspired by the proof of the art gallery theorem, [Bell2010] shows that a planar, unstretchable cloth polygon can always be immobilized by grasping all of the convex corners, and no more than one third of the concave vertices. Shapes like the one to the right in fact require this many grasp locations.

Robot origami folding. My Ph.D. thesis explored robot origami folding; my most recent work on this problem is described in [Balkcom2008]. The most interesting part of the work is the analysis of how origami with networks of creases can be modelled as a kinematic structure. In fact, [Balkcom2006c] shows that simple paper shopping bags cannot be folded using only the creases in the bag -- the bag must flex or bend in order to be folded. A recent paper paper by Weina Wu and Zhong You in the proceedings of The Royal Society follows up on the problem of folding shopping bags.

Papers

Here are the bibtex entries for the following papers. Many of the papers below are subject to copyright restrictions, but you are free to use the preprints linked below for personal use. The first few papers include breaking results, possibly not yet published conference or journal form.

[Wang2015d]
Weifu Wang, Devin Balkcom:
Towards tying knots precisely.
(pdf) Conference paper manuscript (possibly under review). 2015.
[Wang2015c]
Weifu Wang, Devin Balkcom:
Towards arranging and tightening knots and unknots with fixtures.
(pdf) Invited journal article (possibly under review). 2015.
[Lyu2015]
Yu-Han Lyu, Devin Balkcom:
Optimal trajectories for planar rigid bodies with switching costs.
(pdf) Accepted for the International Journal of Robotics Research (2015)
[Balkcom2015]
Devin Balkcom, Ajay Kannan, Yu-Han Lyu, Weifu Wang, Yinan Zhang:
Metric cells: towards complete search for optimal trajectories.
(pdf) Accepted for IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2015.
[Wang2015b]
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.
[Wang2015a]
Weifu Wang, Devin Balkcom, Amit Chakrabarti:
A fast online spanner for roadmap construction.
(pdf) International Journal of Robotics Research (2015)
[Lyu2014b]
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.
[Bell2014]
Matthew P. Bell, Weifu Wang, Jordan Kunzika, Devin Balkcom:
Knot-tying with four-piece fixtures.
(pdf) International Journal of Robotics Research 33(11): 1481—1489 (2014)
[Wang2014]
Weifu Wang, Matthew Bell, Devin Balkcom:
Towards arranging and tightening knots and unknots with fixtures.
Algorithmic Foundations of Robotics (WAFR). 2014.
[Lyu2014a]
Yu-Han Lyu, Devin Balkcom:
Optimal trajectories for planar rigid bodies with switching costs.
(pdf) Algorithmic Foundations of Robotics (WAFR). 2014.
[Wang2013]
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.
[Li2013]
Zhong Li, Devin Balkcom, Aaron M. Dollar:
Rigid 2D space-filling folds of unbroken linear chains.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2013.
[Furtuna2013]
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.
[Wang2012b]
Weifu Wang, Devin Balkcom:
Sampling extremal trajectories for planar rigid bodies.
(pdf) Algorithmic Foundations of Robotics (WAFR). 2012.
[Wang2012a]
Weifu Wang, Devin Balkcom:
Analytical time-optimal trajectories for an omni-directional vehicle.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2012.
[Furtuna2011]
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.
[Kavathekar2010]
Paritosh A. Kavathekar, Bruce A. Craig, Alan M. Friedman, Chris Bailey-Kellogg, Devin Balkcom:
Characterizing the space of interatomic distance distribution functions consistent with solution scattering data.
(pdf) Journal of Bioinformatics and Computational Biology 8(2): 315—335 (2010)
[Bell2010]
Matthew P. Bell, Devin Balkcom:
Grasping non-stretchable cloth polygons.
(pdf) International Journal of Robotics Research 29(6): 775—784 (2010)
[Furtuna2010]
Andrei A. Furtuna, Devin Balkcom:
Generalizing Dubins curves: minimum-time sequences of body-fixed rotations and translations in the plane.
(pdf) International Journal of Robotics Research 29(6): 703—726 (2010)
[Chitsaz2009]
Hamid Reza Chitsaz, Steven M. LaValle, Devin Balkcom, Matthew T. Mason:
Minimum wheel-rotation paths for differential-drive mobile robots.
(pdf) International Journal of Robotics Research 28(1): 66—80 (2009)
[Furtuna2008]
Andrei A. Furtuna, Devin Balkcom, Hamid Reza Chitsaz, Paritosh A. Kavathekar:
Generalizing the Dubins and Reeds-Shepp cars: fastest paths for bounded-velocity mobile robots.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2008.
[Bell2008]
Matthew P. Bell, Devin Balkcom:
Knot tying with single piece fixtures.
(pdf) IEEE International Conference on Robotics and Automation, (ICRA). 2008.
[Balkcom2008]
Devin Balkcom, Matthew T. Mason:
Robotic origami folding.
(pdf) International Journal of Robotics Research 27(5): 613—627 (2008)
[Ray2006]
L. Ray, J. Joslin, J. Murphy, J. Barlow, D. Brande:
Dynamic mobile robots for emergency surveillance and situational awareness.
IEEE International Workshop on Safety, Security, and Rescue Robotics. 2006.
[Balkcom2006c]
Devin Balkcom, Erik Demaine, Martin Demaine, John Ochsendorf, Zhong You:
Folding paper shopping bags.
(pdf) International Meeting of Origami Science, Math, and Education (OSME). 2006.
[Balkcom2006b]
Devin Balkcom, Paritosh A. Kavathekar, Matthew T. Mason:
The minimum-time trajectories for an omni-directional vehicle.
Algorithmic Foundation of Robotics (WAFR). 2006.
[LoomisB06]
Anne Loomis, Devin Balkcom:
Computation reuse for rigid-body dynamics.
(pdf) IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2006.
[Chitsaz2006]
Hamid Reza Chitsaz, Steven M. LaValle, Devin Balkcom, Matthew T. Mason:
Minimum wheel-rotation Paths for differential-drive mobile robots.
IEEE International Conference on Robotics and Automation (ICRA). 2006.
[Balkcom2006a]
Devin Balkcom, Paritosh A. Kavathekar, Matthew T. Mason:
Time-optimal trajectories for an omni-directional vehicle.
(pdf) International Journal of Robotics Research 25(10): 985—999 (2006)
[Balkcom2004]
Devin Balkcom, Matthew T. Mason:
Introducing robotic origami folding.
(pdf) IEEE International Conference on Robotics and Automation. 2004.
[Balkcom2002e]
Devin Balkcom, Matthew T. Mason:
Extremal trajectories for bounded velocity mobile robots.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2002.
[Balkcom2002d]
Devin Balkcom, E. J. Gottlieb, Jeffrey C. Trinkle:
A sensorless insertion strategy for rigid planar parts.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2002.
[Balkcom2002c]
Devin Balkcom, Jeffrey C. Trinkle, E. J. Gottlieb:
Computing wrench cones for planar contact tasks.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2002.
[Balkcom2002b]
Devin Balkcom, Jeffrey C. Trinkle:
Computing wrench cones for planar rigid body contact tasks.
(pdf) International Journal of Robotics Research 21(12): 1053—1066 (2002)
[Balkcom2002a]
Devin Balkcom, Matthew T. Mason:
Time optimal trajectories for bounded velocity differential drive vehicles.
(pdf) International Journal of Robotics Research 21(3): 199—218 (2002)
[Balkcom2000b]
Devin Balkcom, Matthew T. Mason:
Time optimal trajectories for bounded velocity differential drive robots.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2000.
[Balkcom2000a]
Devin Balkcom, Matthew T. Mason:
Extremal trajectories for bounded velocity differential drive robots.
(pdf) IEEE International Conference on Robotics and Automation (ICRA). 2000.