This CAREER award will support research in algorithms to design motion strategies for robots and other mechanical systems. Applications include mobile-robot control, analysis of protein structure for drug design, and design of more reliable tools for automated manufacturing.
There are a number of fundamental open problems. Given a resource to conserve, such as time, energy, precision, or opportunities for sensing, what is the optimal trajectory between two configurations? How should motions be planned for highly-constrained mechanical systems, for which it is difficult to automatically generate feasible configurations? Can mechanical devices be designed so that all motions lead reliably to the goal, in spite of errors in sensing and control?
These challenges span several facets of the motion problem, but there is an underlying theme. Constraints due to the requirement for optimality, kinematics of the mechanism, or frictional contact mechanics impose a global structure on the space of possible configurations of the system. Often, the configuration space can be described as a collection of relatively homogeneous regions, separated by sharp boundaries at which the behavior of the system changes.
The basic goal is to extract as much information as possible about the structure of the configuration space using whatever analytical techniques are most appropriate, including Pontryagin's Maximum Principle, Morse Theory, and tools from mathematical programming. Once this structure has been determined, the next step is to find ways to represent the space and reason about it automatically.
The research program will be complemented by the development of a strong curriculum in robotics and geometric-reasoning algorithms. The award will support a small team of graduate student researchers, the development of a core group of classes to prepare undergraduate and graduate students for robotics research, and a summer robotics camp for K-12 students.
Theory and practice are tightly coupled in robotics. New practical robot designs force examination of underlying geometry, and new theoretical results lead to more creative and effective mechanisms and algorithms. I and my students build robots to achieve new manipulation and locomotion tasks. We also find new ways to model and solve foundational problems, with a combination of tools from classical mechanics, continuous mathematics, and discrete computer science. Main results of work funded by the CAREER award involve a study of the most efficient way to drive robots from one configuration to another ("robot geodesics"), and a study of how flexible materials such as cloth or string may be best manipulated by robots. Robot geodesics One of the most fundamental problems in robotics is how to move a robot from one configuration to another efficiently. There may be many paths, but some are better than others for reasons of safety, speed, precision, or fuel use. General-purpose path planning algorithms can often find a path that connects two configurations, but these algorithms are computationally expensive, and the resulting paths are rarely guaranteed to be efficient. We discovered the optimal trajectories for two of the most common types of mobile robots: wheelchair-like differential-drive robots with two driven wheels, and three-wheeled omni-directional robots. These robots, together with steered cars studied by Dubins and Reeds-Shepp, are still the only non-trivial mobile robots for which the minimum-time trajectories are known exactly. Most recently, we were able to pose and solve a more general problem, that includes all of the previous systems as special cases: what are the minimum-time trajectories for a rigid body in the plane, using actions from a finite set of rotational and translational controls? Our recent work raises the possibility of motion planners that are more general, but still give guarantees about optimality. In the long term, we are interested in building a new approach to motion-planning, that integrally makes use of knowledge of and constraints on optimal trajectories. Flexible object manipulation Building products out of thin flexible materials may reduce material costs, and allow storage in small volumes. Automatic manipulation of flexible materials seems inherently challenging, due to the potential need to control and sense many degrees of freedom. Everyone seems to want a machine that can fold laundry, and we set out to build one. But folding cloth is not difficult, if the cloth is already in a flat, known configuration. Instructional videos on the web describe how to build a t-shirt folding machine out of cardboard and tape -- flaps of cardboard are folded and unfolded in sequence to fold the t-shirt. The more challenging problem is how to flatten a wrinkled or bunched-up piece of fabric. An obvious approach is to grab the corners of a piece of cloth, and pull. A rectangular handkerchief requires exactly four fingers, one at each corner; a six-pointed star requires six. It might seem obvious that grasping the convex corners of a planar cloth polygon always rigidifies the polygon (it works for the square and star!), but we have show that this is not the case: there are polygons that require n + k/3 grasp points, where n and k are the number of convex and concave vertices. This bound is tight; every polygon can be grasped with n + k/3 or fewer fingers. This result also has implications for sensing: n + k/3 point location sensors are always sufficient to ensure that a polygonal piece of cloth has reached a flat configuration. Typical knot-tying robots use many fingers and much sensing, but we have built single-piece devices that tie wire into a knot as the wire is pushed through. We have also built devices to tie string using pressurized air, with only a few moving parts and no sensing. The current challenge for building knot-tying fixtures is that for every new type of knot or type of material, we have to design a new fixture that allows for smooth motion of the string, and easy extraction from the fixture. If the design is simple enough, it can be produced quickly on a rapid prototyping machine (3D printer). In ongoing work, we are creating algorithms that take a description of a knot as input, and output a shape of fixture that can be used to tie the knot.
