LocaltoGlobal Theory and GlobaltoLocal Programming
for Pattern Formation on Spatial MultiAgent Systems
Movies 
Publications
One of the difficulties in both understanding and designing
selforganizing multiagent systems is the lack of theoretical models
that allow us to ask fundamental questions about computability and
complexity. Given a global goal and a multiagent 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 globaltolocal 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 globaltolocal
theory that can answer such questions, in the context of selforganizing 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 selfassembly.
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 selfrepairing 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 selforganize 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, scaleinvariant).
 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 scaleinvariant (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 radiusstate resource tradeoff. We describe
algorithms for tuning along the continuum between
largeradius/lowstate and lowradius /highstate implementations.
 By combining these three techniques, we are able to build a GlobaltoLocal Compiler that implements this
theory: the compiler takes as an input a logicbased
description of a pattern or a set of example patterns, derives a local
checkability condition, and produces a cellular automata rule that is
both scalable and selfrepairing.
This work has led to many new insights into current globaltolocal
compilers, for example how eļ¬cient they are in terms of agent state
and time. It has also revealed new and surprising connections between
cellular automata and traditional computing models (such as Turing
machines, Languages, and DeBruin graphs). An important future area
will be generalizing this work from cellular automata to other
multiagent settings, and using this model to better understand
existing selforganizing systems. Ultimately, this type of theory will
provide an important design tool for selforganizing systems, by
allowing us to reason about the complexity and scalability of embedded
multiagent systems where agents have limited capability.
Movies
Publications
Automated GlobaltoLocal Programming in 1D Spatial MultiAgent Systems,
Daniel Yamins, Radhika Nagpal, Intl. Conf on Autonomous Agents and MultiAgent Systems (AAMAS),
2008. (pdf)
A Theory of LocaltoGlobal Algorithms for OneDimensional Spatial MultiAgent Systems,
Daniel Yamins, Doctoral thesis, Harvard University,
Feb 2008.
(pdf)
The AAMAS 2008 paper describes the main ideas of the first half of
the thesis, including the Local Checkability condition, its
relationship to regular languages, its use in deriving lower bounds,
and its use as a tool in constructing selfrepairing cellular automata
rules. These topics are discussed in much more detail in the
thesis. The thesis also includes many unpublished but important
results, for example the use of this theory to reason about completion
time lower bounds as well as theory for composing patterns.
Towards a Theory of "Local to Global" in Distributed MultiAgent Systems (I),
Daniel Yamins,
Autonomous Agents and Multi Agent Systems Conferences (AAMAS), 2005. (pdf)
Towards a Theory of "Local to Global" in Distributed MultiAgent Systems (II),
Daniel Yamins,
Autonomous Agents and Multi Agent Systems Conferences (AAMAS), 2005. (pdf)
The two AAMAS 2005 papers ahow some of the earlier versions of
these ideas which were applied to mobile agents moving on a 1D
cellular automata. This work shows how ideas of formation control and
flocking are related at a fundamental level to pattern formation.
Tutorial
GlobaltoLocal Programming: Design and Analysis for Amorphous Computers
Tutorial: Overview, Part 1, Part 2, Notes for part 2
Radhika Nagpal, Daniel Yamins, IEEE Conference on SelfAdaptive and
SelfOrganizing Systems (SASO), July 2007


