Videos
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.
- 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).
- 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).
- 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.