Local-to-Global Theory and Global-to-Local Programming
for Pattern Formation on Spatial Multi-Agent Systems

Movies | Publications

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.
  • By combining these three techniques, we are able to build a Global-to-Local Compiler that implements this theory: the compiler takes as an input a logic-based 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 self-repairing.

This work has led to many new insights into current global-to-local 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 De-Bruin graphs). An important future area will be generalizing this work from cellular automata to other multi-agent settings, and using this model to better understand existing self-organizing systems. Ultimately, this type of theory will provide an important design tool for self-organizing systems, by allowing us to reason about the complexity and scalability of embedded multi-agent systems where agents have limited capability.



Automated Global-to-Local Programming in 1-D Spatial Multi-Agent Systems, Daniel Yamins, Radhika Nagpal, Intl. Conf on Autonomous Agents and Multi-Agent Systems (AAMAS), 2008. (pdf)

A Theory of Local-to-Global Algorithms for One-Dimensional Spatial Multi-Agent 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 self-repairing 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 Multi-Agent Systems (I),
Daniel Yamins,
Autonomous Agents and Multi Agent Systems Conferences (AAMAS), 2005. (pdf)

Towards a Theory of "Local to Global" in Distributed Multi-Agent 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.


Global-to-Local Programming: Design and Analysis for Amorphous Computers
Tutorial: Overview, Part 1, Part 2, Notes for part 2
Radhika Nagpal, Daniel Yamins, IEEE Conference on Self-Adaptive and Self-Organizing Systems (SASO), July 2007