Harvard University
Loading the player ...
  • Offer Profile
  • Our group is interested in self-organizing multi-agent systems, where large numbers of simple agents interact locally to produce complex and robust global behavior. We study programming paradigms for engineering such systems in robotics and sensor networks, drawing inspiration mainly from multicellular biology and social insects. We also investigate models of self-organization in biology, specifically how cells cooperate during the development of multicellular organisms.

    A common theme in all of our work is understanding the relationship between local and global behavior: how does robust collective behavior arise from many locally interacting agents, and how can we program the local interations of simple agents to achieve the global behaviors we want. 
Product Portfolio
  • Research

  • Our work on self-organizing multi-agent systems lies at the intersection of Computer Science, Robotics, and Biology. The main theme in our lab is understanding and engineering collective behavior,but we do it in many ways -- both theory and hardware, and both bio-inspired and collaborations with biologists.
        • The TERMES Project

        • Collective construction of 3D structures by termite-inspired climbing robots

          Nature provides us with impressive examples of animal construction: many species of termites build complex mounds several orders of magnitude larger than themselves. Yet the individual architects and engineers are small, expendable, and seem to operate with with little to no centralized supervision. Social termites provide an inspiration for the design of a swarm construction system, where many autonomous robots cooperatively build large-scale structures. Human construction traditionally involves direct human operation of tools and equipment, careful preplanning, and little or no true automation. Bringing automation to construction has the potential to improve measures like its speed and efficiency, as well as enabling construction in settings where it is difficult or dangerous for humans to work, e.g., disaster areas or extraterrestrial environments.

          Inspired by termites and their building activities, our goal in the TERMES project is to develop a swarm construction system in which robots cooperate to build 3D structures much larger than themselves. The current hardware system consists of simple but autonomous mobile robots and specialized passive blocks; the robot is able to manipulate blocks to build tall structures, as well as manuever over and around the structures it creates. The multi-robot control allows many simultaneously active robots to cooperate in a decentralized fashion to provably build a user-specified structure, working from a high-level description as input.
        • The Kilobot Project

        • A Low Cost Scalable Robot System for Demonstrating Collective Behaviors

          In current robotics research there is a vast body of work on algorithms and control methods for groups of decentralized cooperating robots, called a swarm or collective. These algorithms are generally meant to control collectives of hundreds or even thousands of robots; however, for reasons of cost, time, or complexity, they are generally validated in simulation only, or on a group of a few 10s of robots. To address this issue, we designed the Kilobot, a low-cost robot designed to make testing collective algorithms on hundreds or thousands ("kilos") of robots accessible to robotics researchers. Each robot has the basic capabilities required for a swarm robot, but is made with low-cost parts, and is mostly assembled by an automated process. In addition, the system design allows a single user to easily and scalably operate a large Kilobot collective, such as programming, powering on, and charging all robots. systems.

          We are now using the Kilobot swarm to investigate algorithms for robust collective behavior, such as collective transport, human-swarm interaction, and shape self-assembly, as well as new theory that links individual robot capabilities to acheivable swarm behaviors. See our publications and movies to learn more about this research.

          The Kilobot won first place in the 2012 African Robotics Network $10 Robot Design Challenge. The goal of the AFRON challenge is to develop a low-cost robot for education in developing countries. The Kilobot design is available open-source for non-commercial use, and you can also purchase Kilobots from K-Team Corp. We are also developing new example programs and programming environments for using the Kilobot in research and education.
        • The Robobee Project

        • Honeybee colonies exhibit incredibly efficient and adaptive behaviors as a group, even though an individual bee is tiny compared to the world it lives in. Honeybee colonies regularly find and exploit resources within 2-6 km of their hive, adapt the number of bees exploring and exploiting multiple resources (pollen, nectar, water) based on the environment and needs of the colony, and can even recover when dramatic changes are made to their world. While much remains to be understood, biologists believe that many of these sophisticated group behaviors arise from fairly simple interactions between honeybees in the hive, as they share information and adapt their own choices. There seems to be no leader, no centralized authority, to coordinate the hive.

          Achieving the sophistication of social insect colonies poses a number of challenges. It will involve the development of sophisticated coordination algorithms, that match the fairly simple and limited sensing and communication we expect in individual robobees. Just as with honeybees, the ability to leverage the colony as a whole will be critical -- for parallelism (exploration of large areas), energy efficiency (through information sharing and division of labor), and robustness (since individuals may fail or make errors). Especially since each individual robobee has strong limitations on the weight and power (and thus sensing/communication) it can carry.

          At the same time, to manage swarms of robots (with thousands or more individuals) one cannot be managing single robobees. We will need programming languages and theory tools that support a "global-to-local" approach. A key challenge will be the design and scalable implementation of macro languages, where goals can be expressed in terms of high-level objectives for the colony and where the underlying system translates objectives into individual bee decisions and re-optimizes as the world changes.

          The RoboBee colony challenges are shared with many other fields in computer science -- for example multi-robot and robot swarm systems, distributed sensor networks, programming languages research, and even synthetic biology. Our colony team leverages expertise and knowledge in multiple disciplines, and we expect our methodologies to apply to many large-scale systems.
        • Collective Construction

        • Termite mounds can be towering, complex structures on the scale of several meters,with complicated functional architectures that include features such as ventilation systems and humidity regulation. The architects are vast numbers of simple insects on the scale of millimeters, working with no centralized control or preplanning. Yet these animals achieve tremendous complexity, parallelism and robustness, from individuals that are small, simple, and expendable. How swarms of social insects build the structures they do is a fascinating topic not fully understood. Engineering offers a complementary problem: How could you program an artificial robotic swarm to build a particular structure?

          Our group studies how this can be achieved. We combine ideas from swarm intelligence and programmable self-assembly, to create algorithms, theory, and robot designs. We have developed a family of decentralized algorithms by which simple robots -- without wireless communication or GPS/localization -- can cooperate to build a large classes of user-specified structures out of modular blocks. We are developing new robotic platforms, for example, climbing robots that can build block structures much larger than themselves, and material-depositing robots that can build in unstructured environments. Most recently, we are collaborating with biologists to study and model the mound-building termites in Namibia.

          Collective construction has many important potential civilian applications, from the construction of human habitats to containments or support structures in disaster areas. It also is a difficult challenge for robotics and poses many interesting challenges in mechanical design, manipulation, autonomy, and multi-robot coordination.
        • Programmable Self-Adaptation

        • Biologically-Inspired Control for Self-Adaptive Multiagent Systems

          Biological systems can achieve scalable and adaptive group behaviors, such as animal flocking, through local interactions amongst a vast network of unreliable agents. In these systems, each agent acts autonomously and interacts only with its neighbors, yet the global system exhibits coordinated behavior. Large-scale multi-agent systems, e.g. distributed robot systems, are similar to these biological systems, in that their overall tasks must be achieved by coordinating many independent agents. One important question to ask is: How can we program large networks of agents to achieve collective tasks, and at the same time adapt to dynamic conditions like living systems?

          Our group has developed a biologically-inspired control framework for multiagent networks to achieve coordinated tasks in a scalable, robust, and analyzable manner. We focus on distributed homeostasis, a type of task in which agents must use distributed sensing to solve collective tasks and to cope with changing environments. This task space can be formulated more generally as distributed constraint-maintenance on a networked multi-agent system, and this approach allows us to capture various multi-agent scenarios and tasks. We show how one can exploit the locality of this formulation to design nearest-neighbor agent control, based on simple sensing, actuation and local communication.
        • Programmable Soft Orthotics

        • The long-term goal of this collaborative project is to develop programmable active soft orthotics ("programmable second-skin") that can assist children with cerebral palsy in promoting normal gait development, by adapting and compensating for neuromuscular disorders. Such orthotics have the potential for impact in many ways: everyday locomotion assistance, out-patient rehabilitation, and reprogramming gait control in young children.

          This project brings together concepts and expertise from childhood locomotion development, self-adapting modular robotics, and soft robotics, to tackle a challenging but important area.

          Our collaborative group works on many aspects, from the design of specific targetted devices (ankle-foot orthotic), to the design of novel sensor-actuator materials, to studies of locomotion in young children. Some of the overarching objectives are:
          (1) lightweight clothing-like orthotics with soft actuators, sensors, and braces, that do not limit the inherent degrees of freedom of the leg
          (2) bio-inspired distributed design with many sensors and actuators that can sense and control multiple degrees of freedom in different ways
          (3) human-adaptive control, such that the orthotic works with the human leg (arm) compensating only as needed to guide the correct gait (task). We also interact closely with the cerebral palsy team at Children's Hospital.
        • Self-organizing Synchronization and Desynchronization in Wireless Sensor Networks

        • 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. One of the powerful features of these systems is that simple, decentralized node behaviors result in the whole network robustly maintaining synchronization, despite individual faults or changes in topology.

          Our group is interested in how we can use inspiration from these biological systems to design simple self-organizing algorithms for sensor networks, that can easily adapt to errors, changes in topology, and changes in usage. We have shown how firefly-inspired synchronization (pulse-coupled oscillator models) can be adapted to solve different types of problems in ad-hoc wireless sensor networks.
          • We have adapted the Mirollo-Strogatz model of firefly sychronization to work on wireless sensor networks where there are message delays, clock skew, and frequent topology changes. This algorithm (RFA-sync) was implemented on the MicaZ motes and tested on the building-wide MoteLab network (SENSYS 2005). We are now investigating new types of decentralized synchronization algorithms that use the same basic principles, but converge more quickly.
          • We have also shown how one can adapt these principles to generate other useful 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 DESYNC 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 (IPSN 2007). This TDMA scheme was demonstrated on Telos motes, where it achieves near perfect bandwidth utlization under both low and high loads. We are now investigating how the DESYNC algorithm and TDMA scheme behave in multi-hop networks, where there are close relations to problems such as graph coloring and distributed consensus.
        • Proliferation Networks and Epithelial Tissues

        • From Cell Division to Network Topology

          The fruitfly wing is an amazing example of self-assembly.

          Starting from a small disc of 30 cells, the wing forms through many rounds of division until it is a large tissue with some 30,000 cells. During this time the wing also manages to create important architectures, from the cobblestone like regularity of cell shapes, to laying down the pattern of veins, to controlling overall organ size and shape. Many researchers study this system as a model for multicellular organism development. At the same time, the wing belongs to a category of tissues that is common throughout the animal kingdom (and similar to plants) called epithelial tissues. As a result it shares many interesting properties with other multicellular organisms and gives us a clue about the evolution of multicellular systems.

          We are interested in the link between local and global, i.e. how do the local decisions of a cell result in high-level tissue structure? And vice-versa, can high-level tissue structure give us clues about how cells take decisions? Our approach involves looking at tissue as an expanding network (graph) of cell connections and using different techniques to understand the properties of this graph. We have a series of papers on this topic, that captures most of our work.

          Together with our long-time collaborators, Dr Matt Gibson (Stower's Institute) and Dr. Norbert Perrimon (Harvard Medical School) we are investigating this system. This work was led first by Ankit Patel, an applied math student who graduated in 2009, and then by William ("Tyler") Gibson, a biophysics student who graduated in 2011.
        • Local-to-Global Theory and Global-to-Local Programming for Pattern Formation on Spatial Multi-Agent Systems

        • One of the difficulties in both understanding and designing self-organizing multi-agent systems is the lack of theoretical models that allow us to ask fundamental questions about computability and complexity. Given a global goal and a multi-agent system where the agents have limited capability (finite state, limited view), we can ask many theoretical questions: Is the global task solvable? What are the minimal agent capabilities required to robustly solve the task? What are the lower bounds on parallelism and scalability? 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 recently developed the beginnings of a global-to-local theory that can answer such questions, in the context of self-organizing pattern formation tasks on asynchronous cellular automata. This work was developed by Daniel Yamins, as his PhD thesis, and is inspired in part by the amazingly robust and complex pattern formation that is achieved by biological systems such as the fruit fly embryo, as well as the engineering application of pattern formation ideas to robot swarms, modular robots and self-assembly.

          Some of the contributions of this work are:
          • We have shown that there is a necessary and sufficient condition, Local Checkability, that not only allows us to answer the question of existence, but also produce minimal state agent programs for self-repairing pattern formation. Local checkability can be thought of as a distributed voting (or stopping) condition and can be used to solve three problems.
            1. An existence problem: Local checkability forms a simple criterion that any robustly solvable goal must satisfy. If a pattern is not locally checkable, no robust local rule can self-organize it. The minimum radius for local checkability gives us a way to reason about minimal agent programs. We have used local checkability to show lower bounds on agent state and communication for several common classes of patterns (repeated, scale-invariant).
            2. A construction problem: For all patterns that are locally checkable, we can use the local check to algorithmically derive local rule that generates it robustly. The local agent rule is by construction scale-invariant (works for varying numbers of agents), robust (works for any initial condition and asynchronous timing), and self- repairing (pattern reemerges after perturbation).
            3. A resource problem: The two main resource parameters of the model, the agent interaction radius and agent memory size, exist in a radius-state resource tradeoff. We describe algorithms for tuning along the continuum between large-radius/low-state and low-radius /high-state implementations.
        • Programmable Self-Assembly: Bio-inspired, Modular Robotics, 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. Even after development, multicellular organisms show amazing abilities to repair and regenerate. Yet colonies of cells are not the only living things that create complex structure. Even colonies of social insects ("superorganisms") show the ability to create complex large-scale structures that is self-repairing, for example millimeter size termites cooperate to create mounds with complex architecture that are 2-5 meters high, weaver ants create bridges and pulling chains to fold leaves, and army ants create nests (bivouacs) out of their own bodies.

          Our group uses inspiration from these systems to understand how global structure, repair and adaptation can be achieved through simple local behaviors. We are interested in programmable self-assembly and its application to the design of programmable materials, self-reconfiguring modular robots, and coordinating robot swarms. A key focus of our work is the design of global-to-local compilers, where 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. Our work in this area is algorithmic and theory-oriented, but also in many cases tied closely to robotic implementations. Below are several of the self-assembly related themes we pursue and have pursued:
          • Self-assembling and Self-reconfigurable Modular Robots
          • Bio-inspired Self-assembly using Global-to-local Compilers
          • Self-repairing Formation Control for Mobile Agent Swarms
        • Extended Stigmergy

        • Social insects, such as ants and termites, collectively build large and complex structures. These animals achieve tremendous complexity, parallelism and robustness, even though the individuals are small, simple, and expendable. One question is whether we can achieve the same kind of collective intelligence with robots: can a group of simple robots collectively build complex user-specified structures, in a similarly adaptive and robust fashion?

          We have developed a family of decentralized algorithms by which simple robots -- without wireless communication or GPS/localization -- can cooperate to build a large classes of user-specified structures out of modular blocks. Some of the main themes and contributions of our work are:
          • Simple Robots & Extended Stigmergy: Simple robots, without GPS or wireless, can coordinate indirectly by storing information in the environment -- an idea inspired by social insects like termites and ants. In our case, the "blocks" provide a means for both localization and coordination, e.g. by providing a grid-like environment and by allowing the robots to store information (e.g.embedded writeable RFID tags).
          • Coherent Structure Through Local Rules: We consider the construction process as a type of lattice self-assembly. This allows us to leverage ideas from programmable/algorithmic self-assembly to automatically generate local rules for complex 2D shapes. The local rules provably create correct structure even though the assembly may proceed in many possible decentralized orders and some steps may fail; they also take into account movement and manipulation constraints of the robots.
          • Algorithms and Theory: This approach shows that collective construction is algorithmically closely related to other kinds of self-assembly, from DNA self-assembly to modular robotics, even though it exists at a very different size scale. The algorithms generalize to other implementations (e.g,. self-reconfigurable robots) and some related tasks (e.g. 3D structures and disassembly). There are still many open algorithmic challenges, especially in environmentally-adaptive structures.
          • Robot Hardware: Another important thrust has been the design of physical prototypes. We have built several robots that construct 2D structures, using simple but autonomous robots (ER1 and lego platforms) and RFID-tagged blocks. Our hardware implementations demonstrate the level of autonomy and coherent behavior that can be achieved by simple robots, and also demonstrate how the co-design of the blocks (e.g. using self-aligning connectors, RFID tags) can allow the robots to achieve more complex tasks by manipulating the environment.