Report

Designing Collective Behavior in a Termite-Inspired Robot Construction Team

See allHide authors and affiliations

Science  14 Feb 2014:
Vol. 343, Issue 6172, pp. 754-758
DOI: 10.1126/science.1245842

This article has a correction. Please see:

Abstract

Complex systems are characterized by many independent components whose low-level actions produce collective high-level results. Predicting high-level results given low-level rules is a key open challenge; the inverse problem, finding low-level rules that give specific outcomes, is in general still less understood. We present a multi-agent construction system inspired by mound-building termites, solving such an inverse problem. A user specifies a desired structure, and the system automatically generates low-level rules for independent climbing robots that guarantee production of that structure. Robots use only local sensing and coordinate their activity via the shared environment. We demonstrate the approach via a physical realization with three autonomous climbing robots limited to onboard sensing. This work advances the aim of engineering complex systems that achieve specific human-designed goals.

Robot Rules

In the case of mound-building termites, colonies comprising thousands of independently behaving insects build intricate structures, orders of magnitude larger than themselves, using indirect communication methods. In this process, known as stigmergy, local cues in the structure itself help to direct the workers. Werfel et al. (p. 754; see the Perspective by Korb) wanted to construct complex predetermined structures using autonomous robots. A successful system was designed so that for a given final structure, the robots followed basic rules or “structpaths” in order to complete the task.

In contrast to the careful preplanning and regimentation that characterize human construction projects, animals that build in groups do so in a reactive and decentralized way. The most striking examples are mound-building termites, colonies of which comprise millions of independently behaving insects that build intricate structures orders of magnitude larger than themselves (1, 2) (Fig. 1, A and B). These natural systems inspire us to envision artificial ones operating via similar principles (3, 4), with independent agents acting together to build elaborate large-scale structures, guided by reacting to the local situations they encounter. Such systems could enable construction in settings where human presence is dangerous or problematic, as in disaster areas or extraterrestrial environments.

Fig. 1 Natural and artificial collective construction.

(A and B) Complex meter-scale termite mounds (A) are built by millimeter-scale insects (B), which act independently with local sensing and limited information. (C) Physical implementation of our system, with independent climbing robots that build using specialized bricks. (D) System overview for building a specific predetermined result (Fig. 2, A and C): A user specifies a desired final structure; an offline compiler converts it to a “structpath” representation (Fig. 3), which is provided to all robots; robots follow local rules that guarantee correct completion of the target structure (movie S1).

Engineering an automated construction system that operates by termite-like principles rather than human-like ones requires an ability to design complex systems with desired collective behavior (e.g., producing a particular user-specified building). The hallmark of complex systems of independent agents (57) is unexpected collective behavior that emerges from their joint actions, not readily predictable from knowledge of agent rules. If a specific collective behavior is desired, no method in general is known to find agent rules that will produce it.

We present a decentralized multi-agent system for automated construction of user-specified structures, thereby providing a solution to such a problem of complex system design. An arbitrary number of independent robots follow an identical set of simple, local rules that collectively produce a specific structure requested by a user (Fig. 1, C and D). The rules are automatically generated from a high-level representation of the final target structure and provide provable guarantees of correct completion of that structure. The challenges associated with engineering a complex system are addressed by using principles drawn from social insects—in particular, indirect coordination through manipulation and sensing of a shared environment (stigmergy), and behavioral regularities that constrain the space of possible outcomes—which together make analysis and execution tractable. We first present the theoretical foundation for this work, followed by a physical implementation with three independent robots demonstrating autonomous construction.

The independence of individual robots stands in contrast to other work on automating construction with single (810) or multiple (1114) robots with centralized sensing and/or control. Centralized systems that provide a global computing authority and/or precise positioning information during run time, in settings where such features are feasible, can have advantages in aspects such as efficiency and run-time flexibility. Conversely, decentralization provides advantages including opportunities for greater scalability (no coordinating authority that can become overloaded) and robustness (no single point of failure).

We distinguish between two types of building processes (Fig. 2). A system may produce a predetermined outcome, in which many possible system trajectories all lead to the same guaranteed final state. Alternatively, variation during the process may lead to a variable outcome, in which the final state is determined during the course of construction and can change if the process is rerun. In the context of human construction, single buildings are built via the first type of process, in which the order of operations might vary but the final result always matches a blueprint; cities develop via the second type of process, in which choices are contingent on previous decisions such that many distinct results are possible. Here, we focus on designing processes with fixed outcomes, but also show how our system can be used to generate structures that vary each time robots construct them.

Fig. 2 Two types of building process.

(A) Different possible sequences all lead to the same predetermined endpoint. (B) Different sequences lead to different results, which are determined only during the course of construction. (C) Example of the first type of process, building a step pyramid modeled after the main temple at Chichen Itza [photo by Kyle Simourd, CC BY 2.0]. Upper and lower panels show snapshots from different possible sequences (movie S2), at approximately 10%, 25%, 50%, 67%, and 80% completion of the common final structure. (D) Example of the second type of process, building a set of one-brick-high ramifying paths. (E) A hybrid system can combine elements of both types; in this example, paths of stochastically determined lengths lead to buildings chosen randomly from a set of predefined structures. See (19) for details of agent rules for all cases.

Our system design is motivated by the goal of relatively simple, independent robots with limited capabilities (15), able to autonomously build a large class of nontrivial structures using a single type of prefabricated building material (solid “bricks”). We require a robot to be able to move forward, move back, and turn in place; climb up or down a step the height of one brick; and pick up one brick, move while carrying it, and attach it directly in front of itself at its own level. Robots can build staircases of bricks to climb to higher levels. Robots are limited to local sensing, able to perceive only bricks and other robots in their immediate vicinity. Information about the current state of the overall structure and the actions of more distant robots is not available. Robots obtain information about where bricks have been attached only through direct inspection; after they leave an area, this information is liable to become outdated as other robots modify the structure. The structure, built from square bricks in a nonoverlapping grid pattern, provides a reference that robots can use to keep track of their relative movement around it. A single “seed” brick, the initiation point from which the contiguous structure is built, provides a unique landmark.

We take an approach derived from the classically insect-inspired notion of stigmergy (2, 3, 16), in which, instead of any explicit broadcast or one-to-one communication between agents, all communication is implicit via the joint manipulation of a shared environment. In particular, we focus on qualitative stigmergy (2) in which actions are triggered by qualitatively different stimuli, such as distinct arrangements of building material. Robots in our system add bricks to the structure in response to existing configurations of bricks. In doing so, the rules they follow must be constructed in such a way that correct completion of the target structure is guaranteed, despite stale information about other parts of the structure, and irrespective of the (potentially variable) number of other robots and the order and timing of their own actions. The fact that all robots follow the same rules (17)—as all insects in the same colony follow consistent behavior patterns, or other animals obey intraspecific social conventions (18)—helps to constrain outcomes and restricts the space of possible situations that robots typically encounter and must be able to handle.

To ensure a predetermined outcome, robot rules are based on sensed brick configurations plus a static internal representation of the target structure. A user provides a picture or other high-level representation of the desired final structure, specifying what sites are ultimately meant to be occupied by bricks. An offline compilation step converts this to a “structpath” representation that provides movement guidelines for robots at each location—in a sense, traffic laws appropriate for that structure (19) (Fig. 3). Robots then follow a fixed set of simple rules (19), referring to the static structpath representation and otherwise identical for any target structure; these ensure the growth of that structure to completion in a way consistent with robot capabilities (movie S1). The rules rely on locally available information, preserve a robot’s ability to move freely over the structure and opportunities for parallelism, and prevent deadlocks and other situations where the actions of one robot interfere with those of another. Robots act reactively (20, 21); they do not preplan their actions, as is appropriate in this decentralized multirobot approach in which a robot setting out to perform a specific task might find it already completed by the time it gets there.

Fig. 3 Target structures and corresponding structpaths.

For each predefined target structure at left, the corresponding structpath representation at right is generated by the offline compiler (19). From top to bottom: a simple structure with a unique structpath if the seed location is given; the temple of Fig. 2C, showing one of many possible structpaths; a structure enclosing internal courtyards. Sites in the structpath are shaded according to height (darker = higher); a dot marks the seed brick. Directions are color-coded to clarify flows (red, left; blue, right; green, up; yellow, down).

The structpath representation specifies a set of paths that robots can follow through the structure layout while respecting their movement constraints. In particular, all paths start from the seed and require climbing up or down a height of at most one brick at a time. The structpath specifies a fixed direction for robots to travel between each pair of neighboring sites; off the structure, robots follow its perimeter strictly counterclockwise. This directional restriction smooths traffic flow, ensures a flow of material into the growing structure (avoiding excessive backtracking from, e.g., laden robots making way for unladen ones to exit), and allows regularities in structure growth that let local rules ensure the preservation of global invariants. Paths may split and merge; a robot may have more than one way of leaving or entering a site. A multiplicity of possible paths helps the system exploit the parallelism of the swarm. The compiler performs a recursive search to identify a set of paths without cycles that meets these requirements, or to determine that none exists.

Individual robots then repeat the following routine: With a brick, circle the structure perimeter until reaching the seed; climb onto the structure and move along any legal path, keeping track of relative position with respect to the seed; attach the brick at any vacant site whose local neighborhood satisfies a fixed set of geometric requirements (19); continue to follow the path off the structure; obtain a new brick. These rules can be shown to guarantee successful completion of the target structure while ensuring that no intermediate state calls for a robot to perform tasks beyond its capabilities—in particular, climb or descend a height of greater than one brick, attach a brick at a higher or lower level than itself, or force a brick into place directly between two others (a mechanically difficult operation requiring high precision) (19). Direct interaction between robots is limited to each one yielding to the one ahead of it in this physical loop.

Because robots may take multiple possible paths through a structure, the ordering of the building process can occur in many different ways. Accordingly, the structure will emerge in different ways in different instances of building with the same structpath, with intermediate structures that may be observed in one instance but not another; however, the agent rules guide the process to always end in the same final structure (movie S2).

In addition to this approach for producing predetermined structures, the same robots can use different local rules to build structures whose detailed form emerges from the construction process. Multiple structures built with the same rules share qualitative features but differ in detail. Such a rule set could, for example, be used to generate a randomized street layout for a building complex. Figure 2E shows an example of a hybrid system built by such a rule set (19), where buildings chosen randomly from a set of predefined types are positioned at the ends of lanes of stochastically determined lengths. The robots again use stigmergy to coordinate their actions; for example, particular configurations of bricks constitute cues to agree on which building type should be constructed at the end of a given lane.

To demonstrate the feasibility of such a decentralized multirobot construction system, we present a proof-of-concept implementation in hardware (19) (Fig. 1C and Fig. 4). Design choices were driven by the requisite primitive operations that robots must perform: pick up a brick from a cache; attach a brick directly in front of themselves; detect nearby robots; when on the structure, move forward one site (while staying at the same level or climbing up or down one brick) or turn in place 90° left or right; when off the structure, circle its perimeter. For locomotion, we equipped robots with whegs [hybrid wheel-legs (22)], chosen for their empirical effectiveness in climbing (23). Each robot is equipped with seven active infrared sensors to detect black-and-white patterns on the bricks and ground for navigation; an accelerometer to register tilt angle for climbing and descent; an arm to lift and lower bricks, with a spring-loaded gripper to hold them securely while carried; and five ultrasound sonar units that let each robot evaluate and maintain its distance from the structure perimeter, as well as detect other sonar-using robots nearby. The robot footprint (17.5 cm × 11.0 cm) is smaller than that of the bricks, facilitating their maneuverability atop a wall one brick wide. Bricks (21.5 cm × 21.5 cm × 4.5 cm) are made from expanded urethane foam, with physical features to achieve self-alignment and neodymium magnets for attachment.

Fig. 4 Hardware demonstration.

Independent autonomous robots with purely onboard sensing collectively work on prespecified structures. (A) A castle-like structure (movie S3). (B) A sequence of overhead snapshots building a branching structure (movie S4).

This hardware system demonstrates multiple simultaneously active, independent robots executing the full algorithm with entirely on-board sensing. supplementary movies show fully autonomous robots working on different user-specified structures (Fig. 4 and movies S3 and S4), adding bricks both atop the structure and on the ground, climbing over the structure as they build it, and adapting to one another’s presence and actions, without human intervention beyond reloading the brick cache. The reactive nature of the approach can be demonstrated via externally imposed changes made to a structure while robots work on it (movie S5). Many approaches to mobile robotics deal with the continuous, noisy real world by probabilistically modeling its uncertainty (24); our system instead uses carefully engineered hardware to effectively discretize robot actions on the structure. Sensor feedback and brick features matched to the robots allow reasonable reliability with simple control (19). Minor deviations from ideal behavior are corrected by compensatory routines and/or passive mechanical features; for example, drift in position atop a structure is reduced both by robots checking their pose with respect to the brick markings, and by indentations on brick upper faces that guide the robots to stay within tolerance. Although extending this research prototype to a full production system would require solving many additional engineering challenges (19), our work demonstrates that physical hardware can allow the discretized theory to sufficiently represent the continuous reality.

This work provides an example of an engineered complex system, with multiple autonomous robots following simple, local rules and collectively achieving a specific desired result. Tools drawn from the social insects that inspire our approach—the exploitation of regularities that arise from identical programming in multi-agent systems, and the use of the environment as a means of implicit coordination—make these results possible. Future progress in our ability to design complex systems will advance our capacity to engineer systems that work as nature does (2527), with large numbers of functionally limited, interchangeable parts, individually unreliable, collectively robust.

Supplementary Materials

www.sciencemag.org/content/343/6172/754/suppl/DC1

Materials and Methods

Figs. S1 to S12

Table S1

References (2834)

Movies S1 to S5

References and Notes

  1. See supplementary materials on Science Online.
  2. Acknowledgments: Supported by the Wyss Institute for Biologically Inspired Engineering.
View Abstract

Subjects

Navigate This Article