Overview

We are developing algorithms for automated construction, in which swarms of simple, identical, autonomous robots assemble square building blocks into desired shapes. Putting limited abilities for communication and computation into the blocks allows them to convey nonlocal structure information to robots, and consequently lets structures of arbitrary shape be built rapidly by simple robots exhibiting a few fixed, local behaviors. Functional differentiation between blocks leads to additional classes of constraints on block placement, which may be specified as predefined blueprints, or as local rules allowing for adaptive structures.

Motivation

The ability to automate construction would be useful particularly in settings where human presence is dangerous or problematic; for instance, robots could be sent ahead of human travelers to underwater or extraterrestrial environments, to create habitats in advance. Swarm approaches, involving larger numbers of simpler robots rather than one or a few with greater sophistication, have advantages for such a goal, in particular with respect to decentralization and robustness. Such systems can typically absorb the loss of many components without a significant impact on task completion; similarly, they tolerate components acting in no exact specified order, which is useful because of the difficulty of preplanning robot behavior in detail in uncertain environments.

Swarms of building robots bring to mind, and can draw inspiration from, social insects such as ants and bees. These insects use stigmergy to guide their building activities: e.g., ants deposit materials in ways influenced by their immediate surroundings, and in turn influence those surroundings by depositing material. In this way the insects communicate implicitly through manipulation of the environment.

While stigmergy can be used to produce structures with given qualitative characteristics [1], it does not easily allow the consistent production of specific structures. Nor has a general principle been described for starting with the goal of a particular desired structure and generating a set of low-level agent behaviors to produce it. We use an extended notion of stigmergy, allowing the building material to communicate once attached to the structure, to make these goals possible.

Modular robotics are another area of research we draw on in our approach [2]. This work has produced systems with capabilities such as connections that self-adjust so that inexact alignment is corrected, and communication links between physically attached modules. We envision such tools being essential parts of a system which follows our approach.

Our approach is based on a few simple basic capabilities (directed movement, block pickup, perimeter following, block joining, limited communication with immediate neighbors) which can be made robust and self-correcting. This quality is important for the goal of realizing such a system in hardware. We are currently pursuing such a goal.

General Problem and Assumptions

We consider the problem where mobile robots, caches of building blocks, and a marker indicating the location for the start of construction are deployed at random into an obstacle-free workspace. The marker and caches send out distinct long-range signals which robots can use to navigate to them. The goal is for robots to collect blocks from the caches and arrange them into some desired structure starting at the marker.

An important constraint is that a block can be added to the growing structure if and only if the potential attachment site has at least two adjacent sides open; otherwise there is insufficient room to maneuver to add the new block. This assumption greatly simplifies the task of mechanical design and the precision with which robots must operate, and in particular eliminates situations where a block would need to be maneuvered down a tunnel.

Robots can move in any direction in the plane, detect the presence of other robots for collision avoidance, and follow the perimeter of the structure once in its immediate vicinity.

Building Arbitrary Shapes

In reference [3] we describe construction algorithms which prevent unwanted gaps in a structure, and demonstrate advantages which obtain from transferring sophistication from the robots to the building blocks.

Below are successive snapshots during the construction of a sample structure of complicated perimeter.

Light gray marks robot locations; white, blocks; dark gray, regions where blocks are intended eventually to be placed; black, regions where blocks will never be placed.

The graph below shows how using blocks which communicate allows the system to scale up much more easily to large numbers of robots. Details are again in reference [3].

Functionally Distinct Blocks

Reference [4] describes the extension to blocks which, while still uniformly square in shape, belong to different functional classes (shown as different colors in the figures below).

Patterned structures may be fully prespecified, as in this example:

Construction of a structure of green, yellow, blue, and red blocks (robots are shown in white).

In many cases, the design of structures does not require specific patterns, but rather requires functional relationships between the locations of building elements of various types. The more relevant and natural way to specify constraints is then by reference not to absolute coordinates, but to relationships between block types. Below are three examples of 21x21-block structures built with the constraint that no two yellow blocks be adjacent.

Sample structures of red and yellow blocks.

Satisfying constraints in an 'online' way, during the course of construction, can let the structure be adaptive, and take form according to changing circumstances or conditions unknown in advance. Another potential benefit is increased speed of construction. In the class of the above example (21x21 structures in which no two yellow blocks may be adjacent), 'blueprinted' construction is 70% slower on average than online construction. This difference is a result of the greater flexibility in permissible block attachment when constraints are specified at a low level than when the type of every block is fully specified.

Research support

This work is supported by NSF grant EIA-0130391.

References

[1] Guy Theraulaz and Eric Bonabeau. Coordination in distributed building. Science 269: 686-688.

[2] Daniela Rus and Gregory Chirikjian, eds. Autonomous Robots 10(1):5-124, 2001.

[3] Justin Werfel, Yaneer Bar-Yam, and Radhika Nagpal. Construction by robot swarms using extended stigmergy. AI Memo AIM-2005-011, MIT CSAIL, 2005.

[4] Justin Werfel, Yaneer Bar-Yam, and Radhika Nagpal. Building patterned structures with robot swarms. In Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), to appear, Edinburgh, Scotland, August 2005.