MIT 6.978: Biologically Motivated Programming Technology for Robust Systems

Request for Proposals:
Decentralized sensing and control

Developments in microfabrication and MEMs devices are making it possible to bulk-manufacture millions of tiny computing elements integrated with microsensors and microactuators and embed these into materials and structures. Novel applications are being envisioned, and built: sensor covered beams and bridges, modular self reconfiguring robots, self-assembling nanostructures. New directions in biocomputing may even make it possible to harness the many sensors and actuators in cells and create programmable tissue substrates.

Programming such systems to do useful work presents a significant challenges. Approaches within the applications community have been dominated by a centralized, hierarchical mind-set. In the MEMs community, a common approach is a decentralized versions of traditional centralized control theory, usually heirarchical control which is not very scalable and can be quite brittle, catastrophically failing if a high-level node fails. In the reconfigurable robotics community, the focus has been on centralized planning and heuristic searches, which quickly become intractable for large numbers of modules. A more important problem with these approaches is that there is a strong tendency to depend on centralized information, such as global clocks or external beacons for triangulating position, which puts severe limitations on the possible applications and environments and exposes easily attacked points of failure. These programming strategies put pressure on system designers to build complex, precise (and thus expensive) agents rather than cheap, mass-produced, unreliable computing agents that one can conceive of just throwing at a problem.

Currently, however, few alternatives exist. Approaches based on cellular automata and artificial life research have been difficult to generalize; local rules are constructed empirically for explaining a particular phenomena, without providing a framework for constructing local rules to obtain any desired goal. Evolutionary and genetic approaches are more general but the local rules are evolved without any understanding of how or why they work. This makes the correctness and robustness of the evolved system difficult to verify and analyze.

The papers [1] and [2] represent two different approaches to programming a reconfigurable robot consisting of identical modules; the first approach relies on motion planning to reconfigure arbitrary shapes and the second approach uses cellular automata like local rules for locomotion over objects. The two papers provide an interesting comparison between purely global and purely local techniques.

Biological systems achieve incredible robustness in the face of constantly dying and replacing parts. Termites collectively construct elaborate structures with specific functional constraints; ants effectively forage large areas; cells with identical DNA cooperate to form incredibly complex structures, such as ourselves, starting from a nearly homogeneous egg.

The goal of this project is to explore robust metaphors for engineering applications. Possible projects could be:


[1] "Distributed Motion Planning for modular robots with unit-compressible modules", Butler, Byrnes, Rus, International Conference on Intelligent Robots and Systems (IROS), 2001.

[2] "Generic Decentralized Control for a Class of Self-Reconfigurable Robots", Butler, Kotay, Rus, Tomita, Proceedings of the IEEE Intl Conf on Robotics and Automation (ICRA), 2002.

[3] Links to research on smart materials, reconfigurable robotics and distributed sensor networks.