People | Publications | Picture Gallery | Movies

Social insects, such as ants and termites, collectively build large and complex structures, with many individuals following simple rules and no centralized control or planning. Such swarm systems have many desirable properties: a high level of parallelism, cheap and expendable individuals, and robustness to loss, addition, and errors of individual insects.

Our goal is to design systems for automating construction that are similarly adaptive and robust, but build what we want. Automated construction will impact our ability to operate in inhospitable habitats, from outer space to under water, and allow automated disassembly and repair.

We have developed a family of decentralized algorithms by which identically-programmed autonomous agents can collectively and reliably build user-specified solid 2D configurations from building blocks. Here, agents act without explicit communication, instead relying on the partially built structure as a form of indirect coordination similar to stigmergy in insects. We have shown that adding even simple capabilities to blocks, e.g. writeable state using RFID tags, can significantly increase the robustness and simplicity of the system as a whole (extended stigmergy). The algorithms rely on simple but analyzable agent behaviors, and the process is robust to variable numbers of agents, asynchronous agent timing, and addition/loss of agents.

We have also built two hardware demonstrations. The first was built using the ER1 robot. Our current one uses the LEGO Mindstorms system. We recently demonstrated the LEGO Mindstorm robots at the Robot Exhibition at AAAI 2006 (read about it on CNet and Wired News).