I'm an associate professor (tenured 2010) in the Computer Science department at Dartmouth college; my primary research area is robotics. You can reach me at devin.balkcom@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, with an online interactive textbook. 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.

News

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, Dr. Weifu Wang, Dr. 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

Much existing work attempts to tie simple knots using one or two robot hands, often with complex sensing and feedback control. In contrast, we have designed mechanical devices, fixtures, that guide the string into the correct shape. These devices quickly and reliably tie a wider variety of knots than prior approaches. 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?

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.

Journal and conference papers

The Dubins car and other arm-like mobile robots
Devin Balkcom, Andrei Furtuna, Weifu Wang
IEEE International Conference on Robotics and Automation (ICRA). 2018. (Accepted.)
Assembling and disassembling planar structures with divisible and atomic components
Yinan Zhang, Emily Whiting, Devin Balkcom
IEEE Transactions on Automation Science and Engineering (2018) (Accepted.)
Knot grasping, folding, and re-grasping
Weifu Wang, Devin Balkcom
International Journal of Robotics Research (2018)
Rearranging agents in a small space using global controls
Yinan Zang, Xiaolei Chen, Hang Qi, Devin Balkcom
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2017.
A tactile shirt for teaching human motion tasks
Paritosh Kavathekar, Devin Balkcom
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2017.
Assembling and disassembling planar structures with divisible and atomic components
Yinan Zhang, Emily Whiting, Devin Balkcom
Algorithmic Foundations of Robotics (WAFR). 2016.
Re-configuring knots to simplify manipulation
Weifu Wang, Devin Balkcom
Algorithmic Foundations of Robotics (WAFR). 2016.
Interlocking structure assembly with voxels
Yinan Zhang, Devin Balkcom
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2016.
Grasping and folding knots
Weifu Wang, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2016.
Towards tying knots precisely
Weifu Wang, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2016. (Finalist for best manipulation paper.)
Optimal trajectories for planar rigid bodies with switching costs
Yu-Han Lyu, Devin Balkcom
International Journal of Robotics Research 35(5): 454—475 (2016)
k-survivability: diversity and survival of expendable robots
Yu-Han Lyu, Yining Chen, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2016. (Also published as RAL journal article by the same name.)
k-survivability: diversity and survival of expendable robots
Yu-Han Lyu, Yining Chen, Devin Balkcom
Robotics and Automation Letters 1(2): 1164 — 1171 (2016)
Towards arranging and tightening knots and unknots with fixtures
Weifu Wang, Devin Balkcom
IEEE Transactions on Automation Science and Engineering 12(4): 1318—1331 (2015)
Metric cells: towards complete search for optimal trajectories
Devin Balkcom, Ajay Kannan, Yu-Han Lyu, Weifu Wang, Yinan Zhang
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2015.
An online method for tight-tolerance insertion tasks for string and rope
Weifu Wang, Dmitry Berenson, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2015.
A fast online spanner for roadmap construction
Weifu Wang, Devin Balkcom, Amit Chakrabarti
International Journal of Robotics Research 34(11): 1418—1432 (2015)
The bench mover's problem: minimum-time trajectories, with cost for switching between controls
Yu-Han Lyu, Andrei A. Furtuna, Weifu Wang, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2014.
Knot-tying with four-piece fixtures
Matthew P. Bell, Weifu Wang, Jordan Kunzika, Devin Balkcom
International Journal of Robotics Research 33(11): 1481—1489 (2014)
Towards arranging and tightening knots and unknots with fixtures
Weifu Wang, Matthew Bell, Devin Balkcom
Algorithmic Foundations of Robotics (WAFR). 2014.
Optimal trajectories for planar rigid bodies with switching costs
Yu-Han Lyu, Devin Balkcom
Algorithmic Foundations of Robotics (WAFR). 2014.
A fast streaming spanner algorithm for incrementally constructing sparse roadmaps
Weifu Wang, Devin Balkcom, Amit Chakrabarti
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2013.
Rigid 2D space-filling folds of unbroken linear chains
Zhong Li, Devin Balkcom, Aaron M. Dollar
IEEE International Conference on Robotics and Automation (ICRA). 2013.
Structure and geometry of minimum-time trajectories for planar rigid bodies
Andrei A. Furtuna, Weifu Wang, Yu-Han Lyu, Devin Balkcom
Allerton Conference on Communication, Control, and Computing. 2013.
Sampling extremal trajectories for planar rigid bodies
Weifu Wang, Devin Balkcom
Algorithmic Foundations of Robotics (WAFR). 2012.
Analytical time-optimal trajectories for an omni-directional vehicle
Weifu Wang, Devin Balkcom
IEEE International Conference on Robotics and Automation (ICRA). 2012.
Minimum-time trajectories for kinematic mobile robots and other planar rigid bodies with finite control sets
Andrei A. Furtuna, Wenyu Lu, Weifu Wang, Devin Balkcom
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2011.
Characterizing the space of interatomic distance distribution functions consistent with solution scattering data
Paritosh A. Kavathekar, Bruce A. Craig, Alan M. Friedman, Chris Bailey-Kellogg, Devin Balkcom
Journal of Bioinformatics and Computational Biology 8(2): 315—335 (2010)
Grasping non-stretchable cloth polygons
Matthew P. Bell, Devin Balkcom
International Journal of Robotics Research 29(6): 775—784 (2010)
Generalizing Dubins curves: minimum-time sequences of body-fixed rotations and translations in the plane
Andrei A. Furtuna, Devin Balkcom
International Journal of Robotics Research 29(6): 703—726 (2010)
Minimum wheel-rotation paths for differential-drive mobile robots
Hamid Reza Chitsaz, Steven M. LaValle, Devin Balkcom, Matthew T. Mason
International Journal of Robotics Research 28(1): 66—80 (2009)
Generalizing the Dubins and Reeds-Shepp cars: fastest paths for bounded-velocity mobile robots
Andrei A. Furtuna, Devin Balkcom, Hamid Reza Chitsaz, Paritosh A. Kavathekar
IEEE International Conference on Robotics and Automation (ICRA). 2008.
Knot tying with single piece fixtures
Matthew P. Bell, Devin Balkcom
IEEE International Conference on Robotics and Automation, (ICRA). 2008.
Robotic origami folding
Devin Balkcom, Matthew T. Mason
International Journal of Robotics Research 27(5): 613—627 (2008)
Dynamic mobile robots for emergency surveillance and situational awareness
L. Ray, J. Joslin, J. Murphy, J. Barlow, D. Brande
IEEE International Workshop on Safety, Security, and Rescue Robotics. 2006.
Folding paper shopping bags
Devin Balkcom, Erik Demaine, Martin Demaine, John Ochsendorf, Zhong You
International Meeting of Origami Science, Math, and Education (OSME). 2006.
The minimum-time trajectories for an omni-directional vehicle
Devin Balkcom, Paritosh A. Kavathekar, Matthew T. Mason
Algorithmic Foundation of Robotics (WAFR). 2006.
Computation reuse for rigid-body dynamics
Anne Loomis, Devin Balkcom
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 2006.
Minimum wheel-rotation Paths for differential-drive mobile robots
Hamid Reza Chitsaz, Steven M. LaValle, Devin Balkcom, Matthew T. Mason
IEEE International Conference on Robotics and Automation (ICRA). 2006.
Time-optimal trajectories for an omni-directional vehicle
Devin Balkcom, Paritosh A. Kavathekar, Matthew T. Mason
International Journal of Robotics Research 25(10): 985—999 (2006)
Introducing robotic origami folding
Devin Balkcom, Matthew T. Mason
IEEE International Conference on Robotics and Automation. 2004.
Extremal trajectories for bounded velocity mobile robots
Devin Balkcom, Matthew T. Mason
IEEE International Conference on Robotics and Automation (ICRA). 2002.
A sensorless insertion strategy for rigid planar parts
Devin Balkcom, E. J. Gottlieb, Jeffrey C. Trinkle
IEEE International Conference on Robotics and Automation (ICRA). 2002.
Computing wrench cones for planar contact tasks
Devin Balkcom, Jeffrey C. Trinkle, E. J. Gottlieb
IEEE International Conference on Robotics and Automation (ICRA). 2002.
Computing wrench cones for planar rigid body contact tasks
Devin Balkcom, Jeffrey C. Trinkle
International Journal of Robotics Research 21(12): 1053—1066 (2002)
Time optimal trajectories for bounded velocity differential drive vehicles
Devin Balkcom, Matthew T. Mason
International Journal of Robotics Research 21(3): 199—218 (2002)
Time optimal trajectories for bounded velocity differential drive robots
Devin Balkcom, Matthew T. Mason
IEEE International Conference on Robotics and Automation (ICRA). 2000.
Extremal trajectories for bounded velocity differential drive robots
Devin Balkcom, Matthew T. Mason
IEEE International Conference on Robotics and Automation (ICRA). 2000.