Bruce Randall Donald
Associate Professor
brd@cs.cornell.edu

Ph.D. MIT, 1987

I have moved to Dartmouth. Please visit my new home page there.

Job openings in my lab at Dartmouth.

This webpage was last updated in July, 1997. Please visit my new home page, which may be more current.

Address/Phone.
Teaching.
Research.
- Demos.
- Papers and Publications.
- Laboratory.
  - Lab Pictures.
- Students.
- Post-Docs.
My Official Departmental Home Page.
In the news.
- TV.
- New York Times.
Fun.

Teaching

In Spring 1997, I taught CS 212, Structure and Interpretation of Computer Programs. I also teach Robotics, Robotics and Machine Vision, and other courses.

Cornell Robotics and Vision Laboratory

Dan Huttenlocher and I founded the Cornell Robotics and Vision Laboratory in 1991.

Research

Our Laboratory serves as an umbrella for interdisciplinary research in several interlocking sub-disciplines. The field of Physical Geometric Algorithms studies computational processes that compute or reason about geometric or spatial relationships in the physical world, and their realization in a variety of application areas. These areas include Robotics, Microelectromechanical Systems (MEMS), and Computer Graphics. In the canonical examples of Physical Algorithms, we employ a computer to control a physical device in the world--- for example, one may imagine a computer-controlled robot arm or mobile robot. Our laboratory pursues the value proposition that, for such systems, predictions of behavior, arguments of correctness, and combinatorial precision devolve to a geometric analysis.

The Laboratory studies and develops Physical Geometric Algorithms in three domains:

Robotics
Robotics is the science that seeks to forge an intelligent, computational connection between perception and action. Our primary focus is the development and analysis of robot algorithms to solve tasks in mobile robotics, manipulation, manufacturing robotics (parts feeding), and haptics. Our Robotics work comprises a research program in distributed manipulation, in which distributed systems of sensors, actuators, and computers cooperate to perform manipulation tasks. Examples of distributed manipulation systems include teams of mobile robots, and parallel arrays of micromanipulators. For instance, we have previously developed teams of small mobile robots that can cooperate to maneuver large objects (e.g., furniture) by coordinated pushing. Such systems can be useful in warehousing applications. At the same time, we have developed a computational theory for the design, analysis and synthesis of such systems.
We are also pursuing research collaborations with the Medical School. For example, we will explore the use of robots in minimally invasive surgery and haptic telediagnosis. We also will employ vision systems and other sensory devices in the service of robotic tasks.
More on recent progress in Robotics in our laboratory.
Microelectromechanical Systems (MEMS)
MEMS is a broad term for a the emerging science and technology of bulk-fabrication silicon processes to create electromechanical micro-machines. MEMS may be viewed as the fabrication technique for micro-robotics; however, the design and analysis of MEMS is often more like Very Large-Scale Integration (VLSI) circuits, and mandates novel algorithmic paradigms. Our work to date studied how massively-parallel "teams" of micro-machines can be designed, fabricated, controlled, and programmed to accomplish manipulation tasks. The primary goal is to deliver actuation capabilities as a commodity (in the same way that computation and sensing are broadly available today). For example, in the past, we have explored how to build 'intelligent' surfaces, tiled with micro-actuators, in order to perform manipulation tasks. Specifically, we developed massively-parallel arrays of distributed microactuators, and showed how such systems can be useful for the orienting, posing, and feeding small parts such as integrated circuit (IC) chips. To do this, we developed a theory by which well-understood manipulation algorithms from traditional manufacturing robotics can be parallelized and distributed over arrayed systems comprising tens of thousands of tiny actuators.
MEMS faculities include the National Nanofabrication Laboratories at Cornell and Stanford, plus equipment for measuring, testing, controlling, and programming MEMS; microscopes and video equipment for observing experiments; and simple packaging equipment. In addition, graphics workstations are used for computer-aided design (CAD).
A survey paper on our MEMS research.
A more detailed paper on Algorithmic MEMS (the mathematical and computational challenges).
Computer Graphics and Multimedia
Physical Geometric algorithms are an essential component of computer graphics research. Our work in Graphics has three main thrusts:
- AUTHORING TOOLS. Currently, multimedia content can be played by millions but created by few. We are working to develop authoring tools, particularly for animation, that will greatly expand the authoring population. For example, our previous work in computer graphics focused on model-based geometric algorithms for animation. We developed methods for generating animations from very high-level scripts. This yields a method for automatically rendering animation sequences of moving objects without keyframes.
- DIRECT MANIPULATION AND HAPTICS. Currently, Multimedia content can be edited and reused by directly tugging on a graphic or animation using a pointing device like a mouse. We are working to develop novel user interfaces using 3D haptic, forcefeedback devices. Haptics will be explored both as a graphic manipulation device, and as a method for expressing content (shape, texture, and design choices).
- ACTIVE OBJECTS. Multimedia playback should be an immersive, interactive experience, in which a virtual reality system can manipulate the user's physical environment to generate realistic effects. To achieve this goal, we are working to develop servoable cameras and sensors, which capture data from the user to influence Multimedia presentation (e.g., to control an avatar). For example, we have pursued algorithms for automatic camera control; this work has applications to Multimedia authoring and to teleconferencing. Video applications tax the limits of high-performance computing, and hence are interesting to a variety of computer science researchers.
More on our graphics and multimedia research.

Demos

Massively parallel micro-fabricated actuator arrays.
MPEG video of Tommy chasing Lily. Tommy and Lily are mobile robots we built. Using algorithms developed by the vision group in our lab, Lily can track Tommy and follow him, using visual information alone. This video shows Lily's view of the `chase.'
Face Morphing.

Hot Off The Presses (Preprints)

Computational Methods for the Design and Control of MEMS Micromanipulator Arrays, (with K.-F. Böhringer, G. Kovacs, N. MacDonald, and J. Suh) IEEE Computational Science and Engineering, Vol. 4, No. 1. Special Issue on Computational MEMS (Jan-March 1997). pp. 17--29.
Vector Fields for Task-Level Distributed Manipulation: Experiments with Organic Micro Actuator Arrays, (with K.-F. Böhringer, J. Suh, and G. Kovacs) in Proc. IEEE International Conference on Robotics and Automation, Albuquerque, NM (1997). pp 1779-1786.
The Area Bisectors of a Polygon and Force Equilibria in Programmable Vector Fields, (with K.-F. Böhringer, and D. Halperin) To appear, Proc. ACM Symposium on Computational Geometry, Nice, France (1997).
Programmable Vector Fields for Distributed Manipulation, with Applications to MEMS Actuator Arrays and Vibratory Parts Feeders, (with K.-F. Böhringer, and N. C. MacDonald), (Submitted to International Journal of Robotics Research, 1996).
Sensorless Manipulation Algorithms Using a Vibrating Surface, (with K.-F. Böhringer, V. Bhatt, and K. Goldberg) (Submitted to Algorithmica, Special Issue on Algorithmic Foundations of Robotics, 1996).
Mobile Robot Self-Localization without Explicit Landmarks, (with R. G. Brown), (Submitted to Algorithmica, Special Issue on Algorithmic Foundations of Robotics, 1996).
Visibility-Based Planning of Sensor Control Strategies, (with Amy Briggs), submitted to Algorithmica, Special Issue on Algorithmic Foundations of Robotics, (1996).

Selected Recent Publications

K.-F. Böhringer, B. R. Donald, and N. C. MacDonald, Upper and Lower Bounds for Programmable Vector Fields with Applications to MEMS and Vibratory Parts Feeders, International Workshop on the Algorithmic Foundations of Robotics, Toulouse, France (1996). in Algorithms for Robotic Motion and Manipulation,, ed. J. P. Laumond and M. Overmars, A. K. Peters, Wellesley, MA (1997). pp. 255--276.
Amy Briggs and B. R. Donald, Robust Geometric Algorithms for Sensor Planning, International Workshop on the Algorithmic Foundations of Robotics, Toulouse, France (1996).
K.-F. Böhringer, B. R. Donald, and N. C. MacDonald, Single-Crystal Silicon Actuator Arrays for Micro Manipulation Tasks, IEEE Workshop on Micro Electro Mechanical Systems (MEMS), San Diego, California (February 1996).
K.-F. Böhringer, B. R. Donald, and N. C. MacDonald, Classification and Lower Bounds for MEMS Arrays and Vibratory Parts Feeders: What Programmable Vector Fields Can (and Cannot) Do, IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, Minnesota (April 1996).
Provably Good Approximation Algorithms for Optimal Kinodynamic Planning: Robots with Decoupled Dynamics Bounds (with P. Xavier) Algorithmica (Vol 14, no 6) (1995). pp. 443-479.
Provably Good Approximation Algorithms for Optimal Kinodynamic Planning for Cartesian Robots and Open Chain Manipulators (with P. Xavier) Algorithmica (Vol 14, no 6) (1995). pp. 480-530.
. Kinodynamic Motion Planning (with P. Xavier, J. Canny, and J. Reif) Journal of the ACM, Vol. 40, No. 5, Nov., 1993. pp. 1048-1066.
Information Invariants for Distributed Manipulation (with J. Jennings and D. Rus) in International Journal of Robotics Research, (in press) (1996).
B. R. Donald, J. Jennings, and D. Rus, Minimalism + Distribution = Supermodularity , Journal of Experimental and Theoretical Artificial Intelligence (JETAI), (in press) Special issue on Software Architectures for Hardware Agents; Vol. 9 No. 2-3 (1997).
. I am writing a book entitled Information Invariants in Robotics. A draft of the first quarter of this book appeared as a paper in Artificial Intelligence. Here it is: Information Invariants in Robotics. Revised MS based on the paper "On Information Invariants in Robotics," Artificial Intelligence Vol. 72 (Jan, 1995) pp. 217-304.
Distributed Robotic Manipulation: Experiments in Minimalism, in International Symposium on Experimental Robotics, (ISER) Stanford, CA (1995). Appears in: in Experimental Robotics IV}, Lecture Notes in Control and Information Sciences 223, ed. O. Khatib et al., Springer Verlag (Berlin) 1997 pp. 11--25.
Moving Furniture with Teams of Automonous Mobile Robots, (with J. Jennings and D. Rus) in Proc. IEEE/Robotics Society of Japan International Workshop on Intelligent Robots and Systems, (IROS) Pittsburgh, PA (1995).
Sensorless Manipulation Using Massively Parallel Micro-fabricated Actuator Arrays (with K.-F. Böhringer, R. Mihailovich, and Noel C. MacDonald), Proc. IEEE International Conference on Robotics and Automation, San Diego, CA (May, 1994).
A demo and more detailed explanation.
K.-F. Böhringer, B. R. Donald, R. Mihailovich, and N. C. MacDonald, A Theory of Manipulation and Control for Microfabricated Actuator Arrays, Proceedings of the IEEE Workshop on Micro Electro Mechanical Systems (MEMS), Oiso, Japan (January 1994).
. Program Mobile Robots in Scheme(with J. Rees) Proc. IEEE International Conference on Robotics and Automation Nice, France (May, 1992), pp. 2681-2688.
- Many people do not realize that the title of this paper is in the imperative mode. It should be read as:
  Program Mobile Robots in Scheme! Note the exclamation point.
Information Invariants for Distributed Manipulation (with J. Jennings and D. Rus) in The First Workshop on the Algorithmic Foundations of Robotics, A. K. Peters, Boston, MA. ed. R. Wilson and J.-C.Latombe (1994).
Automatic Sensor Configuration for Task-Directed Planning (with Amy Briggs), Proceedings 1994 IEEE International Conference on Robotics and Automation, San Diego, CA (May 1994).