A termite mound is a remarkable thing. It can extend meters both above and below the ground, with complex functional architecture including features like gardens, nurseries, royal chambers, and extensive systems for temperature control and atmospheric regulation. All this is built by vast numbers of tiny, relatively simple insects, acting with no central control or careful advance planning.

I have been studying the problem of engineering artificial systems that build in ways inspired by social insects like these. Such systems could operate in environments hostile to human workers, as in extraterrestrial or underwater settings, facilitating manned space exploration or ocean research. Like other forms of automation, they could improve issues like efficiency, safety, and reliability reported as problems in traditional construction. And they may one day lead to general-purpose fabrication systems that construct smaller-scale artifacts as well as buildings.

The swarm approach allows massive parallelism, has no crucial elements or assigned roles as potential failure points, and is highly robust to failures of individual components. On the other hand, it's a tricky business to program an unknown and potentially variable number of robots, with limited capabilities and only local knowledge, which need to collectively produce a complex global outcome from their local actions.

My focus has been on the design of algorithms for such systems. These let a user take a bunch of robots and a supply of building material, and give them nothing more than a high-level representation or description of a desired structure as input. The robots will then reliably build that particular structure, without requiring further human intervention, or getting stuck in situations where mutually conflicting actions make further progress possible (like building a wall around an area where further work is still needed, and as a result being unable to get into that area to do the work).

One tool for making these algorithms more effective is "extended stigmergy" -- briefly, improving the system by increasing the capabilities of the environment, which can be simpler, cheaper, and more effective than increasing the capabilities of the robots. In the context of construction, embedding processors in building materials and letting them communicate with physically attached neighbors -- or even just sticking passive RFID tags on blocks -- can allow substantial improvements in robustness, construction speed, and ability to take advantage of the parallelism of the swarm.

In the course of working on my thesis, I built a proof-of-concept prototype system capable of building arbitrary specified 2-D solid structures out of square building blocks. Since then, similar robots have been built using Lego Mindstorms, primarily by two undergraduates in the SSR group.

Publications:

• Werfel, Justin. Anthills built to order: Automating construction with artificial swarms. Doctoral thesis, MIT, May 2006. Also CSAIL Technical Report MIT-CSAIL-TR-2006-052.
  This is the most complete and extensive description of everything through the first half of 2006. Some experimental results reported here are slightly more extensive than in papers published earlier.

• Werfel, Justin, Yaneer Bar-Yam, Daniela Rus, and Radhika Nagpal. Distributed construction by mobile robots with enhanced building blocks. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation (ICRA 2006), Orlando, Florida, USA (2006).
  Describes algorithms for 2-D construction; introduces extended stigmergy; discusses the first hardware prototype.

• Werfel, Justin, and Radhika Nagpal. Extended stigmergy in collective construction. IEEE Intelligent Systems 21(2): 20-28 (2006).
  Focuses on analysis of extended stigmergy and the performance of different variants.

• Werfel, Justin, Yaneer Bar-Yam, and Radhika Nagpal. Building patterned structures with robot swarms. Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), Scotland, UK, pp.1495-1502 (2005).
  Considers building structures from heterogenous block types with different functional properties. Also discusses disassembly and error correction.

• Werfel, Justin, and Radhika Nagpal. Collective construction of environmentally-adaptive structures. 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), San Diego, California, USA (2007).
  Considers building structures whose shape is partially or entirely determined by environmental elements.

• Werfel, Justin, and Radhika Nagpal. Three-dimensional construction with mobile robots and modular blocks. International Journal of Robotics Research, 27 (3-4): 463-479 (2008). (Contact me for a copy.)
  Describes algorithms for 3-D construction, with correctness proofs and performance analysis.

• Werfel, Justin, and Radhika Nagpal. Three-dimensional directed construction. Workshop on Self-Reconfigurable Modular Robots, at Robotics: Science and Systems II, Philadelphia, Pennsylvania, USA (2006).
  Earlier progress on 3-D construction.

• Werfel, Justin. Robot search in 3D swarm construction. First IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2007), Cambridge, Massachusetts, USA (2007).
  Analysis of paths on the surface of 3D structures built from cubes, demonstrating the need for a certain amount of complexity in robots or building material.

• Werfel, Justin, and Radhika Nagpal. Towards a common comparison framework for global-to-local programming of self-assembling robotic systems. Workshop on Self-Reconfigurable Robots & Systems and Applications, at IROS 2007, San Diego, California, USA (2007).
  Adaptation of construction approach to programmed self-assembly; modification of a graph grammar approach to handle geometrically specified structures; comparison of the two approaches along several performance axes. This workshop paper primarily states results; fuller explication can be found in the tech report below.

• Werfel, Justin, and Radhika Nagpal. Towards a common comparison framework for global-to-local programming of self-assembling robotic systems. Technical Report TR-14-07, Harvard EECS (2007).
  Expanded version of the above workshop paper.

• Schuil, Crystal, Matthew Valente, Justin Werfel, and Radhika Nagpal. Collective construction using LEGO robots. Robot Exhibition, Twenty-First National Conference on Artificial Intelligence (AAAI 2006), Boston, MA (2006).
  Presentation of the LEGO-based robot system. Received Technical Innovation Award for "elegant connection of theory and design".

• Werfel, Justin, Yaneer Bar-Yam, and Radhika Nagpal. Construction by robot swarms using extended stigmergy. AI Memo AIM-2005-011, MIT Computer Science and Artificial Intelligence Laboratory (2005). (German translation by Johannes Irmer)
  An early-ish tech report, including discussion of algorithms, performance analysis, and interference between robots.

• Werfel, Justin. Building blocks for multi-agent construction. In Distributed Autonomous Robotic Systems 6 (2004).
  A different, earlier approach to the problem of being able to give a swarm construction system just a high-level description of a desired structure and have it automatically generate it.

Movies:
• Simulation, 2D structure.
  "Writable blocks" algorithm.
• Simulation, 3D structure, weightless environment.
  "Gradient-following" robot algorithm.
• ER1-based robot, adding one block to a partial structure.
  "Writable blocks" algorithm, using RFID tags. Inset shows robot's knowledge of target structure and world state. 10x speedup.
• ER1-based robot, building a 3x3 structure.
  "Inert blocks" algorithm. Cuts between attachments to refill block cache. 100x speedup.
• Two Lego Mindstorms-based robots.
  Lego implementation developed by Crystal Schuil and Matthew Valente. 10x speedup.

Coverage:

• CNET and Wired wrote about the live demonstrations of the LEGO robots at the AAAI Robot Exhibition.

Evolutionary systems

Origin and evolution of altruism and intraspecific communication.

Evolution is proverbially driven by competition, yet cooperation is observed to be widespread throughout nature. Explaining this apparent paradox has long been a matter of considerable controversy, with particular reference to the group selection debates starting in the 1960s. The issue centers on the level or levels at which selection acts. Individual-level and gene-level theories state that the most successful variant is the one that produces the most offspring the fastest. However, spatial models have shown the robust evolution of reproductive restraint, evidence of selection operating at higher than the individual level; in a spatially extended population, the individual with greatest fitness on a longer time scale is not necessarily the one with the highest reproductive rate.

By considering the role of explicit intraspecific communication, we demonstrate robustness to undermining by selfish mutants, in a simple system without any of the mechanisms that have traditionally been suggested to explain such stability; support hypotheses for the possible origins of multicellularity, and suggest how higher-level social communication and organization may similarly have come about; and return to the heart of the longstanding controversy, which is to say V.C. Wynne-Edwards and his hypotheses.

Publications:

• Werfel, Justin, and Yaneer Bar-Yam. The evolution of reproductive restraint through social communication. Proceedings of the National Academy of Sciences 101(30): 11019-11024 (2004).

Movies

Coverage:

• Tom Siegfried wrote a piece for the Dallas Morning News entitled "More talk, less sex breeds success for species' survival", which appeared online in the Holland Sentinel and Fox11AZ.com.

Evolution of cellular automata.

Forcing a population of artificial creatures to compete for limited resources, not just to exploit the available resources effectively, can lead to increases in the rate and extent of the progress of evolution. Two coevolving populations, each affected by the other, tend to fall into cycles and make no net progress as measured against an external metric. Coevolution and resource sharing together are experimentally more effective than either alone. We investigated the mechanisms behind this observation, using a framework of cellular automata whose global task was to estimate the density of binary input patterns.

Publications:

• Werfel, Justin, Melanie Mitchell, and James P. Crutchfield. Resource sharing and coevolution in evolving cellular automata. IEEE Transactions on Evolutionary Computation 4:388-393 (2000).

Using evolution as a computer.

A universal computer can be implemented using an evolutionary system, by constructing logic gates based on coevolving populations.

Publications:

• Werfel, Justin. Implementing universal computation in an evolutionary system. AI Memo AIM-2002-010, MIT Artificial Intelligence Lab (2002).

Computational neuroscience

Reinforcement learning in artificial neural networks.

Backpropagation and other explicitly gradient-based approaches, as a model for learning in a system of interconnected and distributed units, suffer from problems of biological realism and other difficulties. Stochastic gradient-following algorithms can be comparably effective in training networks, while bypassing many of the concerns associated with direct methods. We analyzed and compared several algorithms, investigating questions such as: under what circumstances are stochastic methods effective, how does their performance scale with network size, and how does the structure of the problem affect these issues?

Publications:

• Werfel, Justin, Xiaohui Xie, and H. Sebastian Seung. Learning curves for stochastic gradient descent in linear feedforward networks. Neural Computation 17(12): 2699-2718 (2005).
  A more complete version of the conference paper below, including an analysis of algorithm performance in the presence of noise.

• Werfel, Justin, Xiaohui Xie, and H. Sebastian Seung. Learning curves for stochastic gradient descent in linear feedforward networks. In Advances in Neural Information Processing Systems 16 (2004).

Brain-computer interfaces.

Electroencephalograpy, while low-resolution and noisy compared to more recent imaging methods, is inexpensive and noninvasive. The goal of EEG in BCI is to extract a useful and reliable signal correlated with intent, which can be used as a controller for a prosthesis or remote system.

We constructed a system for recording from subjects presented with various sensory stimuli, and developed classifiers for our own and others' data.

We placed first in the BCI Competition 2003 on data set Ia.

Publications:

• Mensh, Brett, Justin Werfel, and H. Sebastian Seung. BCI Competition 2003--data set Ia: combining gamma-band power with slow cortical potentials to improve single-trial classification of electroencephalographic signals. IEEE Transactions on Biomedical Engineering 51(6):1052-1056 (2004).

Zebra finch song production.

Recordings from certain motor areas in zebra finches show extremely characteristic firing patterns. What patterns of interconnectivity might be responsible for the observed activity, and what mechanisms of synaptic transmission are necessary? (With Michale Fee and Sebastian Seung.)

Publications:

• Werfel, Justin. Neural network models for zebra finch song production and reinforcement learning. Master's thesis, MIT, August 2001. (The associated diploma I received did not look precisely like this.) Also AI Technical Report AITR-2004-008.
  The second half of this thesis was theoretical work on reinforcement learning, which eventually developed into the work reported in the reinforcement learning articles above.

Other work

A group at the 2001 Telluride Neuromorphic Engineering Workshop produced this commentary on the role of robotic systems in the study of biology:
• Niebur, Ernst, et al. Research, robots, and reality: a statement on current trends in biorobotics. Behavioral and Brain Sciences 24(6):1072-1073 (2001).
  Our commentary starts on page 40 of the PDF file.

Other, mostly older projects, not leading to refereed publications:

With Whitman Richards, I explored the emergence of regularities in simulated evolutionary systems, in hopes of extending a formalization of natural selection.

With John Hopfield, I explored the effects of topology on the ability of a partially pruned Hopfield network to recover stored memories.

With Curtis Callan, I analyzed the dynamics and equilibria of mathematical models of evolution on fitness landscapes.

With David Huse, I investigated distributions of avalanche sizes in a simulated Ising model.

With Albert Young, I prepared the Princeton cyclotron and beamline for a weak interaction study.

With Gordon Cates, I helped construct a polarized ³He source for a neutron spin structure experiment.

Werfel, Justin, and Radhika Nagpal. Three-dimensional construction with mobile robots and modular blocks. International Journal of Robotics Research, 27 (3-4): 463-479 (2008). (Contact me for a copy.)

Werfel, Justin, and Radhika Nagpal. Extended stigmergy in collective construction. IEEE Intelligent Systems 21(2): 20-28 (2006).

Werfel, Justin, Xiaohui Xie, and H. Sebastian Seung. Learning curves for stochastic gradient descent in linear feedforward networks. Neural Computation 17(12): 2699-2718 (2005).

Werfel, Justin, and Yaneer Bar-Yam. The evolution of reproductive restraint through social communication. Proceedings of the National Academy of Sciences 101(30): 11019-11024 (2004).

Mensh, Brett, Justin Werfel, and H. Sebastian Seung. BCI Competition 2003--data set Ia: combining gamma-band power with slow cortical potentials to improve single-trial classification of electroencephalographic signals. IEEE Transactions on Biomedical Engineering 51(6):1052-1056 (2004).

Niebur, Ernst, et al. Research, robots, and reality: a statement on current trends in biorobotics. Behavioral and Brain Sciences 24(6):1072-1073 (2001).

Werfel, Justin, Melanie Mitchell, and James P. Crutchfield. Resource sharing and coevolution in evolving cellular automata. IEEE Transactions on Evolutionary Computation 4:388-393 (2000).

Werfel, Justin, and Radhika Nagpal. Collective construction of environmentally-adaptive structures. 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007), San Diego, California, USA (2007).

Werfel, Justin. Robot search in 3D swarm construction. First IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2007), Cambridge, Massachusetts, USA (2007).

Werfel, Justin, Yaneer Bar-Yam, Daniela Rus, and Radhika Nagpal. Distributed construction by mobile robots with enhanced building blocks. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation (ICRA 2006), Orlando, Florida, USA (2006).

Werfel, Justin, Yaneer Bar-Yam, and Radhika Nagpal. Building patterned structures with robot swarms. Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), Scotland, UK, pp.1495-1502 (2005).

Werfel, Justin. Building blocks for multi-agent construction. In Distributed Autonomous Robotic Systems 6 (2004).

Werfel, Justin, Xiaohui Xie, and H. Sebastian Seung. Learning curves for stochastic gradient descent in linear feedforward networks. In Advances in Neural Information Processing Systems 16 (2004).

Werfel, Justin, and Radhika Nagpal. Towards a common comparison framework for global-to-local programming of self-assembling robotic systems. Workshop on Self-Reconfigurable Robots & Systems and Applications, at IROS 2007, San Diego, California, USA (2007).

Werfel, Justin, and Radhika Nagpal. Three-dimensional directed construction. Workshop on Self-Reconfigurable Modular Robots, at Robotics: Science and Systems II, Philadelphia, Pennsylvania, USA (2006).

Schuil, Crystal, Matthew Valente, Justin Werfel, and Radhika Nagpal. Collective construction using LEGO robots. Robot Exhibition, Twenty-First National Conference on Artificial Intelligence (AAAI 2006), Boston, MA (2006). Received Technical Innovation Award for "elegant connection of theory and design".

Werfel, Justin. Anthills built to order: Automating construction with artificial swarms. Doctoral thesis, MIT, May 2006.

Werfel, Justin, and Radhika Nagpal. Towards a common comparison framework for global-to-local programming of self-assembling robotic systems. Technical Report TR-14-07, Harvard EECS (2007).

Werfel, Justin, Yaneer Bar-Yam, and Radhika Nagpal. Construction by robot swarms using extended stigmergy. AI Memo AIM-2005-011, MIT Computer Science and Artificial Intelligence Laboratory (2005). (German translation by Johannes Irmer)

Werfel, Justin. Implementing universal computation in an evolutionary system. AI Memo AIM-2002-010, MIT Artificial Intelligence Lab (2002).

Werfel, Justin. Neural network models for zebra finch song production and reinforcement learning. Master's thesis, MIT, August 2001. Also AI Technical Report AITR-2004-008.