Research

Our work on self-organizing multi-agent systems lies at the intersection of Computer Science and Biology. This page has brief descriptions of the major themes in our group as well as links to project webspages. You can also see movies from several projects.

Bio-inspired Multi-agent Systems, Robotics, and Networks

Programmable Self-Assembly: Bio-inspired, Modular Robots and Swarms
Programmable Self-Adaptation: Modular Robots and Multi-Agent Systems
Collective Construction: Extended Stigmergy and Termes Project
Microrobot Colonies: The Robobee Project and Ant-inspired Autonomy
Self-Organizing Wireless Sensor Networks: Sync, Desync, etc

Multi-cellular Systems Biology and Bio-inspired Multi-agent Theory

Self-Assembly in Epithelial Tissues: From Cell Division to Network Topology
Global-to-Local Theory: Pattern Formation in Spatial Multi-Agent Systems

Project Descriptions

Recent Highlights

Termes Project

Kilobot Project

Self-Adapting Robots

Programmable Orthotics

Robobees Project

Epithelial Topology

Bio-inspired Multi-Agent Systems, Robotics, and Networks

	Programmable Self-Assembly: Bio-inspired, Modular Robots and Swarms Cells with identical DNA cooperate to create complex structures, from fruitflies to humans, with incredible reliability in the face of cell death, variations in cell numbers, and changes in the environment. Our group uses inspiration from these systems to understand how global structure, repair and adaptation can be achieved through simple local behaviors. One of focus areas is self-assembly and its application to the design of programmable materials, self-reconfiguring modular robots, and coordinating robot swarms.A key aspect of our work is the design of global-to-local compilers: in each case the goal is described using a high-level shape language, and the compiler automatically translates the user-specified global goal into a provable agent ("cell") program. We have shown that these kinds of compilers can be designed for many kinds of agents (e.g. origami shape language for a programmable material, or the collective construction compilers for robot swarms) and for many classes of shapes. We have also shown that higher-level phenomena such as scale-invariance and regeneration can be directly encoded into the compilation process. Our work in this area is algorithmic and theory based, but also in many cases tied closely to robotic implementations. See topics below (collective construction, prog. self-adaptation, global2local theory) for many current versions of this theme. Our most recent work is on the Kilobot Project, where the goal is to design a thousand robot swarm using a novel low-cost robot design. Kilobot Project, Self-Assembly Project Webpage
	Programmable Self-Adaptation: Modular Robots and Multi-Agent Systems Many living systems constantly adapt their shape to the environment through distributed sensing and actions: e.g. the human capillary network adjusts to oxygenation needs, plants adjust to sunlight, termites constantly adjust the size and airflow in their nests. In contrast, most studies of programmable self-assembly focus on static shape goals. Our goal is to understand how we can create multi-agent robotic systems that constantly adapt their shape to the environment in order to solve user-specified goals. We originally studied this problem in the context of a modular robot with many distributed tilt sensors that must adapt to variable/changing terrains (e.g. self-balancing walkway or building). We showed that a simple self-organizing algorithm, called distributed homeostasis, provably solves this problem for large classes of complex shape goals and complex agent networks. The approach is closely related to distributed consensus in biological systems (flocking, firefly synchronization). Our approach generalizes to diverse adaptation goals with many types of sensors, e.g. tilt, pressure, light, etc as well as some dynamic goals, like adaptive locomotion. Our group has developed several modular robot hardware prototypes to demonstrate different applications of adaptive materials, for example a self-balancing table and pressure-adaptive gripper, as well as new types of deformable modular robots inspired by biology. Most recently, we are interested in adapting ideas from this work to design flexible and adaptive orthosis for children with gait disabilities. Project webpage
	Collective Construction: Extended Stigmergy and Termes Project Social insects, such as ants and termites, collectively build large and complex structures -- even though the individuals are small, simple, and expendable. One question is whether we can achieve the same thing: can a group of simple robots collectively build complex user-specified structures, in a similarly adaptive and robust fashion? Our group has shown how this can be achieved, by combining ideas from swarm intelligence and programmable self-assembly. We have developed a family of decentralized algorithms by which simple robots (without wireless communication or GPS) can cooperate to build a large class of user-specified 2D structures out of modular blocks; the algorithms are provably robust and deadlock-free. The key insight is that the robots use the environment as a means for indirect communication and coordination during building (extended stigmergy), for example using RFID tags embedded in the modular blocks. We have built some hardware demonstrations using ER1 and Lego robots and blocks with writeable RFID tags. The algorithmic approach generalizes to other implementations (e.g. passive blocks, modular robots) and also to some related tasks (disassembly and repair, 3D shapes). More recently we are working on the Termes Project, to develop robots capable of constructing 3D structures, inspired by mound building by termite colonies. Collective construction has many important potential civilian applications, and also poses many interesting challenges in robot design, coordination, and manipulation. Project webpage
	Microrobot Colonies: The Robobee Project and Ant-inspired Autonomy In nature, social insects have shown how scale can be dramatically exploited: large colonies of small ants effectively forage large areas, millions of tiny termites construct structures a million times their own size, tiny honeybees forage over 6kms from their nests to find nectar. In this project, we plan to design and implement programmable microrobot swarms. One project focuses on terrestrial swarms, using a cockroach-inspired robot design that can traverse complex 3D terrains and swarm-inspired algorithms that leverage simple robot capabilities to achieve efficient and adaptive collectives. A second newer project has the the ambitious goal of being able to create an artificial robobee colony, that like its biological counterpart can achieve tasks as complex as pollination. A interesting question is the relationship between mobility and multiplicity: scaling the agent size down allows novel mobility and access, while scaling the swarm size up allows the system as a whole to attack large tasks. The long term vision of both projects is to create a programmable microrobot colonies that can exist in symbiosis with other living creatures while monitoring, studying, and maintaining the ecological setting. Robobee Project website
	Synchronization and Desynchronization on Wireless Sensor Networks [2004-2008] The spontaneous emergence of synchronization from simple individuals has fascinated scientists for decades: thousands of pacemaker cells synchronize to create a single heartbeat, and firefly swarms synchronize their flashes to form a powerful visual beacon. Our group is interested in the design of simple, self-organizing algorithms for sensor networks, that can easily adapt and repair to errors and changes in topology. We have shown how firefly-inspired synchronization can be adapted for applications on real wireless sensor networks, with message delays, clock skew, and frequent topology changes. We have also shown how one can adapt these principles to create new types of timing patterns, such as desynchronization, where the nodes attempt to flash in a perfect round-robin so as not to interfere with their neighbors. We have used this to design a self-repairing TDMA scheme for collision-free wireless transmissions, such that the transmission schedule automatically adapts as the set of nodes changes. Our group pursues both the theoretical side (how to prove correctness/convergence) and the implementation side (using Berkeley motes), and we collaborate with groups at Harvard and BBN. Project webpage

Multi-cellular Systems Biology and Multi-agent Theory

Systems Biology: From Cell Division to Network Topology in Epithelial Tissues

In a multicellular tissue or organism, how do individual noisy cells interact to create complex systems with global robustness? Understanding the connection between local cell decisions and emergent system-level properties is an important and difficult challenge. Our goal is to develop cell-level (agent-level) models to study such questions, and we work in close collaboration with experimental biologists. Our current work is focused on the cell division process in the rapidly-dividing epithelial tissue of the developing fruit fly wing. In early work, we developed a mathematical model that showed an unexpected cell-to-tissue relationship -- that a purely local and stochastic cell division strategy can robustly regulate the global network topology of cell connections in such a tissue, resulting in a signature equilibrium distribution of cell shapes. This work led to the discovery of a conserved cell shape distribution that occurs in many organisms: fruit fly, frog, hydra and even some plants. It has also led to the development of more computational models that show that there are some necessary conditions to produce the low shape variability seen in these natural systems, and that it may be possible to infer cell division strategies from tissue-level observations. While we continue to look at the impact of this on fruitfly development, this work also has many interesting implications for biology (.g. proliferation in cancer) and also for computer science (network generation).

Project webpage

A Global-to-Local Theory for Pattern formation in Spatial Multi-Agent Systems

[2004-2008] Given a global task, and given an agent model with limited local state and communication radius, one can ask some important theoretical questions: Does a local rule exist such that the multi-agent system will robustly solve the task? And, what are the minimal agent requirements? Answers to these theoretical questions have important practical implications: they tell us fundamental limits on what global-to-local algorithms and compilers can achieve, and how agent design restricts the set of tasks that the system is able to solve. We have developed the beginnings of such a theory, in the context of pattern formation tasks on an asynchronous cellular automata. In particular, we have shown a necessary and sufficient condition, called Local Checkability, that not only allows us to answer the question of existence, but also produce minimal state programs for self-repairing pattern formation. This work sheds new light on current approaches to multi-agent self-assembly and also builds a connection between such spatial systems and more traditional computer science theory. This works also gives us fundamental ways to think about pattern formation and self-repair in biological systems

Project website