Building Blocks for Multi-Robot ConstructionJustin WerfelMassachusetts Institute of Technology, Cambridge, MA, USA [email protected]. One notable capability of social insect colonies that has traditionally inspired dis-tributed robot systems is their construction activity. In this paper, I describe a system of simple,identical, autonomous robots able to build two-dimensional structures of arbitrary design byrearranging blocks of building material into desired shapes. Structure design is specified com-pactly as a high-level geometric program; robots translate this program into physical formvia their fixed behavioral programming. Robots are interchangeable both within and betweenconstruction projects, and need not be individually reprogrammed between dissimilar projects.Such a construction team could be used as the first stage in a system for remote building ofstructures, laying out the floor plan that a more sophisticated system could extend upwards.1 IntroductionA primary inspiration for distributed multi-robot systems is the set of orders of so-cial insects, notably ants, termites, and bees, whose swarms or colonies accomplishmany complex high-level tasks through the collective actions of lower-level agents.One of the most characteristic of these tasks is the robust construction of large-scale,complicated structures, despite the insects’ own small size and limited complexity. Acorresponding research pursuit is the engineering of multi-robot systems that buildspecific desired structures, while retaining advantageous features of the insect sys-tems that inspire them (flexibility, robustness, etc.). The possible uses for structure-building teams of robots are many and far-ranging, from automating the productionof low-cost housing to allowing construction and related activities in settings wherehuman presence is dangerous or problematic. This latter class in turn ranges fromuses in disaster areas, to the construction of first-stage bases of operations to awaitthe arrival of pioneers in, for example, underwater or extraterrestrial environments.In this work, I describe the design and simulation of a system of simple, identi-cal, autonomous robots able to build structures in the shape of arbitrary non-crossingcurves in the horizontal plane, by rearranging blocks of building material into desiredshapes on a grid. The shape is specified compactly by a high-level geometric pro-gram stored in a separate beacon, which serves as the reference point around which2 Justin Werfelall robot activity occurs. Robots receive the program for the structure shape from thebeacon at short range during the course of the construction project, and translate itinto the appropriate arrangement of blocks via their behavioral programming. Thusthe same robots can be used in any construction project without needing to be repro-grammed. The intended method of operation is to scatter a handful of generic robotsin the vicinity of sufficient building material, place a beacon preprogrammed withthe desired structure design, and let construction proceed without further interven-tion. This system is an example of those for which the goal is to robustly generateprespecified global behavior from local interactions among myriad unreliable com-ponents [1].1.1 Previous workMost previous work on autonomous construction teams has focused on other aspectsof the problem. In [20], robots build a linear wall out of blocks held together byVelcro of alternating polarity. Their multi-robot simulations focus on the benefit ofexplicit communication, showing that when robots broadcast one bit indicating thepolarity of the last block placed, the number of attempts to place blocks of inappro-priate polarity is reduced. However, they do not address the issue of specifying morecomplex structures, nor consider more extensive communication in their buildingstrategies. [10] describes a system of physical robots with force sensors only, thatwork without explicit cooperation or communication to clear an area of material, bypushing it to the edges of a gradually expanding clearing. [8, 9] describe minimalistapproaches to sorting and construction, which have the advantage of simplicity butare typically slow, probabilistic (relying on the correction of frequent errors), andrelatively inflexible in the range of structures they can generalize to building. [5]outlines a project whose goal is robots that build 3-D arches and walls at humanscale; its robots are intended to work independently rather than collaboratively, andits primary concern is with mechanical engineering considerations, with no referenceto the question of controlling high-level building design. Its approach is that of [3,4],whose simulations consider the inverse problem of studying the kinds of structuresthat result from different simple rules for agent behavior, but do not address the issueof generating prespecified high-level structures.A related topic is the regulation of formations of agents. Such approaches canbe applied directly to construction if building blocks themselves are mobile robots.Some approaches to formation control require continuous global knowledge about allagents, and/or user intervention [2,6,15]; others can generate crystalline formations,but do not lend themselves to the design of high-level forms [14]; reconfigurationalgorithms for modular robots create two- or three-dimensional forms out of agentswhich are not arbitrarily mobile, but remain always in contact with one another [18,19].In contrast to the preceding, this work focuses on a system of mobile robots withlocal knowledge and local interagent communication. These arrange passive build-ing materials in the horizontal plane into arbitrary non-crossing curves, which can beeasily prespecified by the user. Mobility and structural requirements are separated,Building Blocks for Multi-Robot Construction 3allowing the design of each class of elements to be specialized, the more sophisti-cated elements (robots) to be reused for multiple projects, and the passive elements(building materials, which after installation need never move again) to be of minimalmanufacturing difficulty and cost.2 Component capabilitiesObjects in the world of this system are mobile robots, a fixed beacon, and passive,movable blocks, all of which are initially scattered at random over the workspace.Robots are assumed to possess the following abilities: move in any direction un-less obstructed, and detect if intended movement in a