Anthills built to order : automating construction with artificial swarms

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2006.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Includes bibliographical references (leaves 110-116).Social insects build large, complex structures, which emerge through the collective actions of many simple agents acting with no centralized control or preplanning. These natural systems motivate investigating the use of artificial swarms to automate construction or fabrication. The goal is to be able to take an unspecified number of simple robots and a supply of building material, give the system a high-level specification for any arbitrary structure desired, and have a guarantee that it will produce that structure without further intervention. In this thesis I describe such a distributed system for automating construction, in which autonomous mobile robots collectively build user-specified structures from square building blocks. The approach preserves many desirable features of the natural systems, such as considerable parallelism and robustness to factors like robot loss and variable order or timing of actions. Further, unlike insect colonies, it can build particular desired structures according to a high-level design provided by the user. Robots in this system act without explicit communication or cooperation, instead using the partially completed structure to coordinate their actions.(cont.) This mechanism is analogous to that of stigmergy used by social insects, in which insects take actions that affect the environment, and the environmental state influences further actions. I introduce a framework of extended stigmergy in which building blocks are allowed to store, process or communicate information. Increasing the capabilities of the building material (rather than of the robots) in this way increases the availability of nonlocal structure information. Benefits include significant improvements in construction speed and in ability to take advantage of the parallelism of the swarm. This dissertation describes system design and control rules for decentralized teams of robots that provably build arbitrary solid structures in two dimensions. I present a hardware prototype, and discuss extensions to more general structures, including those built with multiple block types and in three dimensions.by Justin Werfel.Ph.D