Local force cues for strength and stability in a distributed robotic construction system

Abstract

Construction of spatially extended, self-supporting structures requires a consideration of structural stability throughout the building sequence. For collective construction systems, where independent agents act with variable order and timing under decentralized control, ensuring stability is a particularly pronounced challenge. Previous research in this area has largely neglected considering stability during the building process. Physical forces present throughout a structure may be usable as a cue to inform agent actions as well as an indirect communication mechanism (stigmergy) to coordinate their behavior, as adding material leads to redistribution of forces which then informs the addition of further material. Here we consider in simulation a system of decentralized climbing robots capable of traversing and extending a two-dimensional truss structure, and explore the use of feedback based on force sensing as a way for the swarm to anticipate and prevent structural failures. We consider a scenario in which robots are tasked with building an unsupported cantilever across a gap, as for a bridge, where the goal is for the swarm to build any stable spanning structure rather than to construct a specific predetermined blueprint. We show that access to local force measurements enables robots to build cantilevers that span significantly farther than those built by robots without access to such information. This improvement is achieved by taking measures to maintain both strength and stability, where strength is ensured by paying attention to forces during locomotion to prevent joints from breaking, and stability is maintained by looking at how loads transfer to the ground to ensure against toppling. We show that swarms that take both kinds of forces into account have improved building performance, in both structured settings with flat ground and unpredictable environments with rough terrain.

1 Introduction

Construction is a major industry in which the role of automation so far remains very limited. Increasing automation in construction could carry substantial advantages such as reducing injury rates, handling repetitive tasks, and helping to enable construction in settings not currently feasible, e.g., for use in disaster relief or other dangerous or challenging environments. A fully autonomous construction system, able to operate without supervision or intervention, would need to be able to handle unpredictable and changing conditions during the course of a project.

Fig. 1

Overview image showing a swarm of force-aware robots assembling a cantilevering truss out across a gap

The traditional approach to construction is generally preplanned and centralized, starting from a fully detailed design and carrying out a predetermined plan to realize it. For example, construction of even a small pedestrian bridge will typically require months of design and planning, weeks of site preparation (including pouring and curing concrete foundations), and the erection of temporary scaffolding to support the bridge during construction. Such an approach is unable to adapt without replanning if site conditions change or other demands arise during the construction process, as essentially always occurs in practice. An approach in which actions are affected by ongoing feedback during the process will be more robust to such changes. Monitoring physical forces throughout the structure during construction is one form of such feedback that may be particularly useful for anticipating and avoiding potential structural failures.

We are interested in maintaining structural stability (the ability of a structural system to transfer loads to the ground in equilibrium) throughout a building sequence—i.e., the structure must be stable and self-supporting not just at the point of completion (as might be sufficient if it were built with the help of supporting scaffolding), but at every moment while being constructed. In this work, we focus on horizontal cantilevers (as with a bridge being extended from one side of a gap, before it touches down on the far side), as a scenario in which stability and physical forces within the structure are particularly relevant. As a first step, we consider only structures limited to a two-dimensional vertical plane.

Typically, building bridges in unstructured environments requires a variety of distinct tasks such as erecting (and later removing) scaffolding, preparing the terrain, pouring a concrete foundation or otherwise providing an anchor for the structure, etc. Each such required task increases the range of capabilities an autonomous system needs to be able to achieve. To reduce the needed complexity of a robotic system, here we consider structures built as trusses (struts and connecting nodes in a regular lattice) and resting atop existing terrain without site preparation or anchoring. Trusses can span gaps without the need for supplementary scaffolding; structures can be built in response to existing site features, to conform to challenging topographies rather than leveling them; and stability can be achieved by building in such a way as to provide counterbalancing with mass rather than anchoring a structure to a substrate.

In contrast to the centralized approach familiar in human-engineered projects, construction in natural systems is frequently carried out using the swarm approach of decentralized control and local perception. Termites, beavers, and social weaverbirds are examples of communal organisms that collectively build large-scale structures. Their building processes are robust to unpredictable variability in agent actions and external perturbations, and the structures they build are not limited in scale by the size of individual animals.

Drawing inspiration from these animals, we focus on the use of climbing robots operating with decentralized control, local sensing, and a reactive rather than preplanned approach. Climbing robots avoid the workspace limitations associated with stationary or ground-based robots and require considerably less energy than aerial robots. Decentralized control avoids limits on the size and scalability of the building system, issues with communication range and reliability, and fragility associated with a single failure point that could halt the entire process. A reactive approach, adapting to conditions as they are encountered, is more suitable in unstructured terrains where environmental hazards could compromise a preplanned building sequence.

While it would be possible for a swarm to build a predetermined structure according to a precise blueprint, we instead focus on creating structures specified by high-level requirements such as “span a chasm” or “build a 15-m tower.” In this paper, we focus on steps toward the former example, building a cantilever unsupported out over an open space (Fig. 1). In the scenario we consider, the target length of the cantilever, and in some cases the topography of the ground support, is not known in advance, which precludes the possibility of preplanning an optimal bridge shape. Instead, the agents must react to the environment as they encounter it, and build a horizontal cantilever as far as possible before failure. (Note that the geometry of the resulting structure is constrained at the low level, fixed to be a triangular lattice by the node-and-strut design; but the high-level geometry is an emergent outcome of the agent activity, not determined in advance.) In this work, we do not consider the details of touching down on the far side of the gap, which would require specialized building elements and additional control routines. A complete bridge-building sequence might include additional tasks such as detecting stable ground on the far side, installing a specialized foundation to establish ground support, and redistributing previously installed struts to strengthen the final bridge. This complete sequence will be the focus of future work.

In order to ensure that the truss remains stable throughout the building sequence, agents must have feedback allowing them to anticipate and prevent structural failures of multiple types, including breaking and toppling into the chasm. In this paper, we demonstrate that local force information can be used to allow a swarm of truss-climbing robots to significantly improve their performance for this cantilever-building task. One heuristic uses measurements of local forces at a node to evaluate whether venturing out on a strut is likely to be safe or may lead to a joint snapping. Another heuristic uses measurements of local forces at a specific location (the cache where robots obtain material) to evaluate when counterbalancing is needed in order to prevent the structure from toppling into the gap.

This paper develops and extends previously reported work (Melenbrink et al. 2017) in three main ways: replacing finite element calculations with more accurate physics-based simulations, exploring performance in unstructured terrains, and evaluating the scalability of the proposed approach as the number of robots increases.

2 Related work

We first discuss related work in the domain of multi-robot systems. We then look at techniques used in both robotics and building construction involving measuring forces in the built environment and using those forces as cues to inform a building sequence.

2.1 Construction by multi-robot systems

Ardiny et al. (2015) provide a general review of autonomous mobile robots for construction automation, including single-robot as well as multi-robot systems. They discuss and categorize a wide range of research based on construction applications and materials, covering diverse topics including human–robot interaction on the construction site (Stroupe et al. 2006) and large gantry systems for architectural-scale additive manufacturing (Khoshnevis 2004).

One way to categorize work in multi-robot construction systems is by locomotion strategies, with systems that focus on either aerial, climbing, or terrestrial robots. We review each in turn.

A primary limitation of stationary robots in construction scenarios is the workspace limitations they impose, which are prohibitive for many common construction tasks; aerial robots provide one solution. Centralized quadrotor teams that build using struts (Lindsey et al. 2011, 2012) or blocks (Willmann et al. 2012; Augugliaro et al. 2014) have demonstrated a method of expanding the viable workspace, which could be feasibly generalized to an irregular terrain. One limitation of aerial robots is that precise positioning in general settings remains a challenge; the above studies rely on high-accuracy external localization systems in an instrumented laboratory environment. These examples also use building sequences which are preplanned and not robust to environmental perturbations. In addition to aerial systems that build with blocks or struts, work has been done on equipping autonomous flying robots to weave structures out of fibers, such as that presented by Augugliaro et al. (2013, 2015). Fiber structures require stationary anchor points and involve a material suited to a limited range of select construction tasks.

While aerial robots offer a large viable workspace, their potential utility in construction tends to be limited by power consumption. Climbing robots similarly allow for an expanded workspace compared to stationary or ground-based robots, but require less power to transport comparable loads. An early example of a climbing robot that built with custom blocks was the AMAS system by Terada and Murata (2005, 2008). A swarm of climbing robots capable of building with customized blocks was presented by Werfel et al. (2014). Like several other systems discussed here, the latter was able to build structures whose size was not limited by that of the individual robots, but which were limited to being trivially stable: each building element had to be directly supported by others or by the ground, and structures could not cantilever or span unsupported distances.

While the climbing robots discussed above are capable of traversing and assembling structures composed of custom blocks, other examples use climbing robots to build with nodes and struts. An algorithm for truss reconfiguration by a collective of strut-climbing robots was presented by Yun and Rus (2011). This concept was extended by Nigl et al. (2013), who developed a climbing robot and custom 3D-printed node-and-strut construction system, which demonstrated the ability to detach and reattach a strut. Galloway et al. (2010) addressed the workspace limitation problem with the Factory Floor project, a stationary truss assembler capable of building structures without climbing on them. A custom node-and-strut assembly allowed each level to be constructed on a ground plane before being lifted to make room for the next level below. While this is an effective approach in a controlled environment, it would be challenging to adapt to an unstructured terrain. The approaches discussed in this paragraph additionally did not consider forces or stability, and were based on square lattices (struts attached at 90${^\circ }$ or 180${^\circ }$ angles); the strength of a square lattice is limited without diagonal cross-bracing.

Other robots operating in laboratory environments are designed to remain ground-based. Melhuish et al. (1999) reported on wall-building with pucks by groups of robots, inspired by nest construction behaviors in ants. Wawerla et al. (2002) presented a system where robots respond to a beacon to place blocks of alternating color along a straight line. Other systems build with continuous or irregular materials rather than prefabricated units. Napp et al. (2012); Napp and Nagpal (2014a, b) present a method of amorphous construction where autonomous robots deposit foam or similar material in order to construct ramps to overcome obstacles. Parker and Zhang (2006) propose an algorithm that controls a swarm of autonomous robots to clear a region of gravel, as for construction site preparation.

While the references listed above deal with implementations of construction-related robotics within controlled laboratory environments, there are far fewer examples of mobile robots being used for construction on-site. Most of these outdoor examples are terrestrial robots, which often consist of an arm mounted to a wheeled chassis (Stroupe et al. 2006; Shepherd and Buchstab 2014; Helm et al. 2012), and are more typically single-robot than multi-robot systems. Keating et al. (2017) presented the Digital Construction Platform, which consists of two robotic arms mounted in series atop a mobile platform and was demonstrated to be successful in building architectural-scale shell structures. Jokic et al. (2014) demonstrated the Minibuilders team of 3 specialized robots (two climbing robots and one terrestrial robot) capable of building large structures through continuous material deposition.

While these achievements represent a body of research that has evolved considerably over the past 20 years, industry adoption has been limited. Over 20 years ago, the BRONCO robot was developed by Pritschow et al. (1996) for autonomous mobile bricklaying. In recent years, a number of construction robots have begun to gain traction in commercial construction. Among these are SAM (Semi-Automated Mason), designed to work alongside human masonry workers (Sklar 2015), and Tiger-Stone, which has been developed for paving applications (Coxworth 2010).

2.2 Force awareness

None of the examples in the previous section consider forces or stability during assembly, a relatively neglected topic within distributed robotics. Force feedback has been used in the context of studies like that of Wang and Schwager (2016), who demonstrate the ability of a team of robots to use local force measurements to coordinate cooperative transport. This example is a study in distributed robotics where individual robots respond to forces as cues to help determine their behavior, though in a very different context from the one we consider.

A considerable amount of the published work on force sensing in the built environment is related to experimental modal analysis, a type of structural health monitoring that involves the comparison of an on-site frequency response to a known finite element model. This field of research is valuable for the evaluation of completed structures where the global topology is known in advance, but does not afford techniques that could be employed during the construction process, all the more so if the final structural layout is not predetermined. Also of note is a considerable amount of research from the fields of architectural design, structural design, and building construction. Much of this work previews construction in the sense that finite element or physics simulations are used to facilitate agent-based optimization of force-aware building elements within the design process (Parascho 2013; Baharlou and Menges 2013, 2015; Vasey et al. 2015). However, it is important to differentiate work that deals with a force-aware design process from work that deals with a force-aware construction process. While a force-aware design process can optimize material usage for a static structural state, it does not consider forces that change dynamically during construction and therefore does not allow for resilience or adaptation in the building sequence.

The issue of considering forces at each stage of the construction sequence was investigated by McEvoy et al. (2014), who proposed a path planning algorithm for assembly sequences, promoting stability by greedily selecting the most stable option at each time step in the construction process based on a centralized evaluation of the entire (globally known) structure. They were able to demonstrate that the algorithm could produce sequences that led to stable assembly for certain types of trusses. They also considered structures that were anchored to a flat surface, so that the overall stability of the structure (i.e., preventing toppling) was not a consideration.

In an unsupervised construction system where anchoring is not a given, counterbalancing would be an important asset for providing overall stability. Funes and Pollack (1999) describe counterbalancing features that emerge from an evolutionary algorithm that seeks to satisfy a high-level goal of building a cantilever that reaches a given point. While the authors demonstrate the stability of the resulting final configurations, they do not consider the buildability of candidate structures, in the sense of the existence of a building sequence for which the partial structure is stable at each step.

Brodbeck and Iida (2014) extend the principles established by Funes and Pollack. Their framework consists of one stationary robot that can perform two basic operations—adding a single cube to an aggregate assembly and sliding the whole assembly one space over—to construct a cantilever reaching a given point. They are concerned with maintaining stability throughout the entirety of the building sequence, but the approach is preplanned and not reactive, as the robot knows each step it will take in advance.

In general, there is little research on using structural forces to inform a construction process because conventional building practices do not require considering such issues. Self-organized construction is a relatively new field that uniquely demands new methods for sensing and reacting to forces in the construction process.

3 Setup

The objective in the simulations described in this research is to build a cantilever as far as possible out over a gap, via decentralized robotic agents that respond to locally measured forces as cues, using these cues to prevent or delay failure. In the interest of reducing the number of tasks that robots need to be able to perform, we use counterbalancing rather than anchoring to forestall or prevent the otherwise inevitable failure mode of toppling into the chasm the cantilever is intended to cross. We develop the approach in a scenario where the ground leading up to the edge of the chasm is flat. Then, again motivated by simplifying the mechanical requirements for the robots and avoiding the need for preparing a level site before construction begins, we apply our approach to randomly generated rough terrains and characterize its performance in such settings.

Fig. 2

Node and strut at scale, showing a strut present in the “0” position of the node. The forces that can be measured at the joint between the node and strut 0 are axial force (red), shear force (green), and torque (blue) (Color figure online)

3.1 Assumptions

For the purposes of this investigation, we consider a swarm of climbing robots capable of traversing and extending a two-dimensional truss structure, built as a triangular lattice for strength, and confined to a vertical plane. The proposed truss structures are composed of nodes and struts. Robots can carry one strut at a time and cannot pass each other on the truss. Robots are capable of attaching the strut they carry to any of 6 possible vacancies at a node (see Fig. 2). For simplicity, detachment and reconfiguration are not considered in this work (though this may be a topic for future work).

Robots do not communicate directly with each other but rather indirectly through the environment, inspired by the biological phenomenon of stigmergy used to organize construction behavior in termites and other animals, in which cues in the environment affect the actions taken by agents that encounter them. In this application, robots’ actions are affected by force information they receive at nodes, and their actions in turn change the mass distribution on the structure and thereby affect the readings of the nodes’ force sensors. This approach allows the system to bypass the need for direct wireless communication, which can encounter difficulties related to range, occlusion, etc. When located at a node, a robot is able to read sensor information indicating local forces, including axial force, shear force, and torque (Fig. 2). A robot at a node can determine whether each of the available attachment sockets has a strut present or absent, and (as a measure to prevent collisions) whether another robot is currently located at each of the directly adjacent nodes. Robots can keep track of their relative movement along the lattice (and the coordinate system it embodies) as they move from one node to another.

In earlier work, we presented a hardware prototype for a system based on the above assumptions (Melenbrink et al. 2017).

Fig. 3

a The building sequence for each trial begins with a triangle of three struts and three nodes. The node which acts as the supply cache is located at the origin; the red line at $x = 3$ indicates the starting point from which the cantilever length is measured. b A snapshot of a trial where the cantilever has reached 6.5 m. The 4 agents are indicated by blue circles. The red circle marks the origin node. Agents are disallowed from building at or below ground level beyond the edge of the cliff (Color figure online)

For the simulation experiments conducted in this paper, we make the following assumptions. Construction begins with a single pre-assembled triangle composed of 3 nodes and 3 struts (Fig. 3). A supply cache of materials is located at a point taken to be the origin of the coordinate system. Only by visiting this cache node can robots acquire a new strut. Ground support is available for an unlimited distance in the -x direction and for 3.2 m in the +x direction. Nodes are considered to be resting on the ground (not anchored) unless otherwise noted. The simulation begins with a single robot at the origin node. Additional robots enter the simulation at the origin node one by one; in order to avoid congestion, each new robot entering does so as soon as the origin node has been unoccupied for 5 consecutive frames. We conduct initial evaluations with a group size of 4 robots, and later evaluate the scalability of the approach with the number of robots (Sect. 5.6).

At each time step, each robot moves from one node to another (unless no valid option exists), with asynchronous update. Attaching a strut to a node takes one simulation step; retrieving a new strut from the cache occurs during the same simulation step as the robot leaves that node.

For physical plausibility, material assumptions were made based on existing, readily available construction materials, which are desirable from the standpoint of ease of adoption and cost. The struts are considered to be standard hollow steel scaffolding tubes, with a 48-mm outer diameter and a 4-mm wall thickness. The nodes are modeled as hexagonal prisms made of rigid polymer. The unit length of the grid is 1 m. The mass of a strut is taken to be 4 kg and that of a node 2 kg; a robot is taken to be 4 kg when unladen, and 10 kg when laden with a strut with a pre-attached node. In this study, we neglect the details of attachment where some struts would need to infill a gap between two existing nodes, with the extra node being removed and returned.

3.2 Simulation environment

In previous work (Melenbrink et al. 2017), we used a simulation environment that approximated rigid bodies with linear elements and used finite element analysis (FEA) for structural calculations. Since FEA returns only static solutions, the calculations had to be reset and solved independently for every frame. This method did not accurately capture the properties of a dynamic system. Another limitation was that the FEA software was optimized for speed over accuracy, in order to feasibly accommodate the thousands of simulations (each consisting of up to thousands of discrete elements) represented in the work. While the nodes and struts in the system could have been modeled as meshes instead of lines and studied with a more detailed representation, doing so would have required a solution time orders of magnitude greater. In the simplified linear paradigm that was selected instead, constraints were modeled as being fixed or unfixed for each of 6 axes (3 dimensions of translation and 3 dimensions of rotation). This requirement precludes the possibility of modeling nodes as simply resting on the ground, as opposed to being anchored to it. As a result, the FEA model was not able to handle physical properties like surface friction or collisions between elements.

Because of these limitations of the FEA method, in order to consider situations like unanchored structures and irregular terrains, for this work the assumptions described above were implemented in a new dynamic simulation environment built with Unity3D, a game development tool that uses the NVIDIA PhysX 3.3 engine for rigid-body physics simulations.

Rigid-body dynamics is a branch of classical mechanics that focuses on systems of connected bodies and how they react to forces. Discrete bodies are assumed to not deform under applied loads, which simplifies calculations (as opposed to FEA or linear elastic models) and is more conducive to representing the discrete, rigid building elements presented here. All rigid bodies are assigned a PhysX Material, which comprises a coefficient of friction and a coefficient of restitution. Rather than inferring local forces by querying the elastic deformation of node elements as in the previous FEA model (Melenbrink et al. 2017), the PhysX solver allows for direct querying of forces and torques between any two connected bodies.

The PhysX solver operates on a different timescale than the robots in the progression of the simulation. By default, there is a fixed number of PhysX passes per execution of a simulation step, which we set to 500, a very high value compared to typical usage of the engine. However, perturbations to the structure that occur when robots move or add struts may require longer to settle to equilibrium. Because we expect robot movement to occur on a slower timescale than that at which the structure reaches equilibrium, we pause the progression of the agent behavior after each step until the truss reaches a state of equilibrium. Equilibrium is defined as a minimum of 20 consecutive “settling steps” where no element moves more than 1 cm. One pass of Algorithm 2 plus an arbitrary number of “settling steps” needed to reach equilibrium constitutes one full simulation step, as is reported in the tables.

A joint between a node and a strut is considered broken in the simulator if its force magnitude exceeds 6000 N or its torque magnitude exceeds 200 N m. These values are chosen to be conservative given the materials proposed (e.g., a construction-grade steel scaffold tube of the dimensions we simulate would require a shear force of 26 kN to yield), in order to maintain a wide margin of safety for applied loads that could occur during a construction process in a dynamic environment. A structure is considered to have failed if any joint breaks in either way, or if the position of any of its connected elements falls below $y = - 1$ (indicating falling into the gap). Each trial in a simulation experiment continues until either a structural failure occurs or 5000 simulation steps have elapsed.

3.3 Unstructured terrains

Most of the trials presented are in a flat or “structured” environment, characterized by the flat ground support described in Fig. 3. As with all rigid bodies in the simulation, this ground object is assigned a PhysX Material. Its coefficient of friction is set to 1.0 and coefficient of restitution set to 0.0, indicating a material where collisions are highly damped and inelastic. These properties remain constant throughout all trials.

In Sect. 5.5, to explore how our algorithmic approaches would perform in less regular environments, we use procedurally generated terrains with the option to increase feature resolution. These terrains are generated by a recursive function that subdivides line segments and adds noise to the positions of the intermediate vertices, as described in Algorithm 1. At each step of the recursion, the algorithm loops through each edge of the two-dimensional shape that represents the terrain. A new vertex is introduced at the midpoint of the edge, then randomly displaced. The amount of displacement is scaled down according to the depth of the recursion, so that the terrain features being introduced are smaller at each pass. The material properties remain the same as in the flat ground case. Figure 4 shows an example of such a generative process for one terrain, along with other sample terrains.

Fig. 4

a Illustration of Algorithm 1, showing an example progression of recursion steps for generating a terrain. b Additional examples of terrains procedurally generated for trials

4 Robot algorithms

We first present a baseline algorithm for agent-based construction, in which agents act to extend the cantilever in a straightforward way without regard to forces. This approach results in two distinct failure modes: breaking, where forces between elements exceed thresholds and the connections snap; and toppling, where the structure as a whole overbalances and tips into the gap (Fig. 5). We next propose sensing-based solutions to forestall each of these two failure modes. Breaking is addressed by the agent considering local forces at each node in deciding where to move and attach material, while toppling is addressed by considering the balance of forces at the origin node. These two considerations can be combined and allow building significantly further before failure.

We note that while we can generally characterize failures as being of those two types, in practice it can be difficult to definitively classify a given failure as being purely due to one or the other factor. The center of mass of the truss often shifts slowly over the course of a simulation, such that the entire structure may be tilting for up to several hundred simulation steps before toppling. During this gradual tilting, which is otherwise a precursor to toppling, forces get redistributed among ground-resting nodes, which can lead to a break as a result.

4.1 Baseline algorithm

The baseline agent algorithm (“No Awareness Isn’t Very Effective,” or naive) is described in Algorithm 2. Each agent starts at the origin node and traverses the lattice in a random walk, biased in the +x direction. At each simulation step, the agent chooses one of the six socket positions at its current node. If a strut is present there, the agent moves along it to the node at the other end. If no strut is present, the agent installs the strut it carries in that position. Upon installing a strut, the agent returns in a biased random walk to the cache, where it retrieves a new strut.

Fig. 5

Two failure modes that structures are subject to: a toppling and b breaking

4.2 Preventing breaking

An algorithm designed to prevent breaking failures (“Stop Advancing if Forces Evince Risk,” or safer) eliminates from consideration any directions where the forces measured indicate that a potential structural failure might occur if the robot were to move down that strut (Algorithm 3).

When an agent following the safer behavior arrives at a node, the specific value that it considers at each socket is the ratio of the torque to the total force (resultant of axial plus shear forces) there. Looking at the magnitude of the torque alone was found to be sufficient for preventing robots from causing local breaking failures. However, as the structure grows, the magnitude of the torques at certain nodes scale up, inappropriately indicating to agents that a direction is unsafe (Fig. 6). This has the effect of stifling construction, as agents cease to be allowed to walk out on actually safe cantilevers. To avoid this slowdown and risk of deadlock, dividing the magnitude of the torque by the magnitude of the force at the same socket was found to be an effective heuristic. If that quotient exceeds a given threshold (in this case a value of 0.1 m, chosen by looking at specific failure cases and selecting a value conservative enough to prevent common failure modes), the robot should not move along that strut. The use of this heuristic is illustrated in Fig. 6. Two scenarios are pictured where agents measure comparable levels of torque acting on the struts they intend to traverse (marked in red). In (a), an agent wishes to traverse the strut in position 1, which will lead to this joint breaking a few steps later (b). This is a typical occurrence in the naive variant, whereas the safer variant prevents traversal. In (c), the truss has accrued considerably more mass. While the intended traversal is actually safe in this case, this distinction is not reflected by the comparable torque values of 42 and 41 N m. Dividing the torques by the corresponding total forces gives values of 0.75 and 0.02 m, respectively. Thus, with a threshold of 0.1 m, safer will prevent the traversal in the first scenario and permit it in the second.

Fig. 6

Illustration of the need to scale the torque measurement by the magnitude of the total force (axial + shear forces) as a cue to judge whether a strut is safe to traverse. This metric will disallow the agent from traversing down the red strut in (a), but allow for traversal in (c) (Color figure online)

4.3 Preventing toppling

To prevent the structure from falling into the chasm, we further modify the algorithm so that agents build in a way that counterbalances the cantilever. They do this by adding material in other directions, so the center of mass stays over the ground support, using the weight distribution of the structure to effectively provide anchoring. (Note that as before, agents are responding only to local force cues and do not have access to global metrics such as center of mass.) We consider two different approaches to counterbalancing.

The “Predetermined Likelihood for Adding Nodes iN Either Direction” (planned) variant is an extension of safer that maintains equilibrium by adding material in the opposite direction as often as in that of the cantilever. In this variant, when a robot at the origin retrieves a new strut from the cache and is assigned a goal location for biasing its random walk (line 7 of naive), instead of that goal always being (1000, 0), it is assigned randomly from among three possibilities: (1000, 0), (-1000, 0), or (0, 1000) with probabilities of 0.45, 0.45, and 0.1, respectively (Algorithm 4). (The small probability of building upwards is included because, if robots build toward goals only to the left and right, a weak area with a deficit of material appears above the origin, resulting in breaking there.) In this way, the center of mass should always stay over the origin on average, preventing toppling no matter how long the cantilever gets.

The planned variant is potentially wasteful; a more efficient scheme would only use material for counterbalancing when needed. An alternative variant, “Bulk Added to Lean Against Non-Compensated Equilibrium” (balance), has agents look at local forces at the origin node when they return there to collect material, as cues in deciding whether to spend their next trip extending the cantilever or building up the counterweight.

An intuitive way to use the force measurements available at the cache node is to look at the axial forces in the two upward-pointing struts (positions 1 and 2 as indicated in Fig. 2). For a symmetrically loaded structure, the axial reaction forces corresponding to these struts would also be symmetric, while asymmetry in these forces may be an indication that the structure is unevenly loaded and approaching risk of toppling. balance accordingly uses the relative difference between the axial forces at sockets 1 and 2 as the measure indicating when counterbalancing is needed (Algorithm 5, Fig. 7). Each time an agent arrives at the origin node to resupply, it evaluates the difference in axial reaction forces between struts 1 and 2, scaled by the magnitude of the force on socket 2 in order to compensate for the increasing magnitude of forces as the truss grows larger. If this quantity is above a certain threshold, agents bias their random walk in either the vertical direction or the opposite direction from the cantilever. Otherwise, they keep the usual bias in the direction of the cantilever. This effectively creates cyclical patterns of cantilever extending and counterbalancing actions.

Fig. 7

Struts in positions 1 and 2 relative to the origin node are indicated in red and blue, respectively. a For a structure at an early stage, struts have small negative values, indicating that the struts are under comparable compressive forces. b By the time the structure begins tilting, the difference in axial forces is considerable: the compressive force on strut 1 has increased fourfold, and strut 2 is now in tension (Color figure online)

This method of using axial forces also provides a cue for when it is safe for counterbalancing to cease. If a structure has been effectively counterbalanced such that the forces acting on the origin node are approaching symmetry, agents stop counterbalancing and resume extending the cantilever until the threshold is once again crossed.

5 Results

This section presents the results of simulation experiments using the four algorithmic variants described in the previous section. Each entry in the tables below reports the results of 100 trials. Each trial records the number of simulation steps before structural failure (or timeout at 5000 steps), the number of struts attached to the structure in that time, and the length the cantilever reaches beyond the last ground-resting node before the edge of the cliff.

We first evaluate the performance of the baseline naive variant, and compare it to the three other variants in different conditions to investigate the utility of force awareness to prevent local breaking and overall toppling. We evaluate the performance of all four variants in both flat and rough terrains. Finally, we look at the scaling performance of balance, the most effective variant, as swarm size increases.

5.1 Baseline behavior

The results for the baseline naive variant (Table 1) reflect the observation that robots without access to local force measurements build poor structures, which often suffer from breaking even before reaching the edge of the cliff.

Table 1 shows a high degree of variance between trials. Breaking failures generally occur when agents venture out and add material at the end of an unsupported strut (i.e., one that is not connected to other struts via the node on its far end). This can happen very early in the simulation, or later after the swarm has by chance built a sizable cantilever.

Table 1 Results for baseline behavior (no force sensing) on flat terrain

5.2 Preventing breaking

The naive algorithm builds trusses that tend to break before accruing enough mass to topple. In order to study breaking in isolation, we can temporarily eliminate from consideration the failure mode of toppling, by anchoring structures to the ground. Under this condition, nodes at ground level are fixed immovably in place. We can then evaluate force awareness as a means of avoiding breaking failures.

When structures are anchored, neither tilting nor toppling is possible. Table 2 shows that robots with access to local force measurements (safer) are able to build trusses that cantilever significantly further before breaking, compared to those built by robots without access to local force information (naive). For the naive variant, results are nearly identical to the unanchored case. Failures occurred at any arbitrary joint that happened to hold an unsupported strut. For the safer variant, however, failures typically occurred at the joints connected to the anchored, ground-resting nodes, as the global bending of the truss increasingly exerts upward force on these joints.

Typical failures under the naive and safer algorithms for the case of anchored structures are shown in Fig. 8.

Fig. 8

Typical failures for the anchored condition for: a the naive variant, showing the aftermath of a joint breaking under excessive weight; and b the safer variant, where the uplift force from the cantilever has caused a strut to break from the ground-resting origin node (indicated by the red arrow). The latter breakage did not cascade, and therefore, the failure is not visually apparent (Color figure online)

Table 2 Anchored structures, breakable joints, flat terrain

5.3 Preventing toppling

In order to look at the failure mode of toppling in isolation, we return to unanchored structures and temporarily eliminate the failure mode of breaking: under this condition, joints between rigid bodies are treated as infinitely strong, so that they remain intact under any force or torque. We evaluated the safer, planned, and balance variants in this case (Table 3). Because baseline trials in Sect. 5.1 showed breaking failures typically occurring long before toppling becomes a risk—suggesting that when both failure modes are permitted, measures to avoid toppling will rarely be of use in the absence of measures to avoid breaking—we did not evaluate naive in this section.

Trials in the two counterbalancing variants under these conditions may continue indefinitely without failure. (Simulations without timeout were observed to continue for tens of thousands of frames without risk of toppling.) All 100 trials in both counterbalancing variants terminated due to timeout at 5000 frames. In all trials, these variants allowed building farther than safer. The balance variant was able to build significantly further than planned before timeout ($p<0.002$) and used significantly less material ($p<0.001$). Figure 9 shows typical trials at timeout for both counterbalancing variants as well as at the moment of failure for the safer variant.

Table 3 Unanchored structures, unbreakable joints, flat terrain

Fig. 9

Unanchored condition with unbreakable joints. a safer variant: toppling failure. b planned variant: timeout at 5000 steps. c balance variant: timeout at 5000 steps

5.4 Overall performance: flat terrain

In this set of trials, we re-enabled both failure modes of toppling and breaking. The counterbalancing variants can no longer cantilever indefinitely and will now eventually break under their own mass. We tested all four algorithms under these conditions, first on flat ground (Table 4). An example of each of the four variants at the moment of failure is shown in Fig. 10. For the planned and balance variants, failure generally occurred because of the breaking of a joint in the first cantilevering node (indicated by the red arrow in Fig. 10c).

We observed that all trials using safer failed while the structure was tilting, either due to toppling or due to breaking because of the load redistribution associated with tilting. On the other hand, all trials in the planned and balance variants failed due to breaking, never due to toppling, which suggests that in general, these counterbalancing approaches are successful at preventing toppling. While balance reached essentially the same cantilever length as planned before failing, it did so around a third faster and with around a quarter less material consumption.

Table 4 Unanchored structures, breakable joints, flat terrain

Fig. 10

Typical failures for the unanchored condition with breakable joints for: a naive, b safer, c planned, d balance. Red arrows indicate the location of an initial break in each case (Color figure online)

5.5 Overall performance: rough terrain

As an exploration of how these methods might perform in situations without site preparation, we test the four agent algorithms in unstructured terrains (Table 5), randomly generated for each new trial as described in Algorithm 1. Both failure modes remain enabled: structures are not anchored, and joints are breakable.

A comparison of the results for both flat and rough terrain is given in Fig. 11a. Unsurprisingly, all variants are more subject to early failures in rough terrain than in flat ground conditions. Both failure modes can occur sooner in an unstructured terrain. All four agent algorithms encounter early failures associated with weight redistribution as trusses begin to accrue mass, which may result in a shift to different support points. This shift may be associated with tumbling (defined here as tipping onto another face of the structure, i.e., through a rotation of approximately 60 degrees, which (OR: approximately 60$^\circ$, which) which only rarely occurred with flat terrain. Tumbling can precipitate toppling into the chasm, but can also cause breaking as the weight distribution changes extensively with the new orientation. Trusses often will rock back and forth or tumble, causing a strut to break from the truss as it comes into contact with an environmental feature. This was the dominant failure mode for the planned and balance variants, which is understandable as counterbalancing causes frequent weight redistribution to different support points.

Figure 11b, c shows typical early and late failures with balance on rough terrain. The truss shown in panel B will fail a moment after the snapshot shown, when agent movement redistributes weight so as to cause the truss to rock backwards, pressing a horizontal strut against a small feature in the landscape and causing the joint indicated by the red arrow to break. The truss shown in panel C has avoided early failure and survives until much later, where the red arrow indicates a joint that will break under the static load of the entire truss. If a truss survives past the early stage, it typically remains stable to permit construction of a much longer cantilever. These two cases underlie the two distinct peaks especially visible in the safer and planned rough terrain histograms in Fig. 11a.

The balance variant outperformed the planned variant, as the kind of weight redistribution described above did not begin until later in the trial, allowing trusses to be built further ($p < 0.05$) than in the planned variant. On the other hand, the safer variant still failed primarily due to toppling, on average much sooner than in a structured environment. All variants exhibit a high degree of variance in all three metrics, indicating that the specific terrain encountered has a strong effect on the success of building activity.

Table 5 Unanchored structures, breakable joints, rough terrain

Fig. 11

a Distribution of cantilever lengths at time of failure for 100 trials each of naive, safer, planned, and balance in both flat and rough terrains. b A typical early failure. c A typical failure at a later stage. Red arrows indicate joints about to break (see text) (Color figure online)

5.6 Scalability with swarm size

Part of the motivation for the swarm approach is the desired ability to be able to deploy any number of agents, without concerns like needing to change the control approach or overwhelming the capacity of a centralized coordinator. However, the method considered here could potentially not scale well to large numbers of agents, e.g., congestion could build up around the single supply cache and lead to slowdowns or even deadlock. Moreover, in this scenario focused on physical stability, increasing the number of robots has the potential to introduce domain-specific problems, e.g., if many robots are present near the end of the cantilever simultaneously, the extra mass could result in toppling that would not otherwise occur. To investigate such issues, we performed a set of simulation experiments characterizing the performance of the balance algorithm as the number of robots increases.

With the structural strength parameters used in the previous simulations, trusses typically fail when around 10 robots have entered the workspace (using the same deployment rule as before, where a new robot enters whenever the origin node has been unoccupied for 5 consecutive simulation steps). In order to evaluate the scalability of the algorithm over a larger range of swarm sizes, in this section we increased the joint strength by a factor of 10: i.e., a joint between a node and strut breaks if its force magnitude exceeds 60 kN or its torque magnitude exceeds 2 kN m. The result is much longer trials and larger trusses; these require considerably greater simulation time, and so the values reported in Table 6 reflect only 10 trials per entry.

Table 6 Unanchored structures on flat terrain with 10x joint strength, using the balance algorithm

Table 6 shows that the size of the cantilevers built by the swarm is independent of the swarm size. That is, the size of the buildable trusses is a function of the materials and the approach, not of the number of robots, and larger swarms do not introduce new failure modes. Consistent with previous trials of the balance variant, all failures were due to joints breaking at the first cantilevering node.

Fig. 12

Scalability results for building a cantilever of length 30 m with swarms of increasing size, using the balance algorithm. a Number of simulation steps. b Total agent effort: number of simulation steps times number of robots. c Effective total agent effort: number of simulation steps times average number of robots active over the construction period

Figure 12 shows that the time required to build a truss of a given size scales approximately inversely with the number of robots. This result indicates a lack of interference between robots when building, and an ability to make effective use of the parallelism of the swarm. Table 6 shows that traffic congestion remains minimal over the range of swarm sizes tested: for the largest swarms tested, each robot had on average one neighbor at any adjacent node less than half the time. Robots spread out over the path between cache and building front without undue interference with each other’s progress, and the deployment rule helps keep congestion from building up when there is insufficient room on the truss to accommodate more robots.

6 Discussion

Our results show that heuristics based on local force measurements allow independent agents to postpone cantilever failures due to toppling and breaking. Mitigating the failure mode of breaking was demonstrated by an approach in which agents do not move out onto a strut if the torque measured at that socket is too large compared to the axial force measured at that socket (safer). Mitigating the failure mode of toppling was demonstrated by an approach in which agents also add material in the opposite direction from the cantilever if axial forces at the origin node become too unbalanced (balance). The latter approach, addressing both modes of failure, outperformed all other variants both in structured and unstructured terrains.

For anchored structures where toppling cannot occur, force-aware agents (safer) build cantilevers that extend twice as far as agents not using force cues (naive), demonstrating the utility of local force sensing for preventing breaking (Table 2).

For structures with unbreakable joints but free to topple, both counterbalancing strategies consistently reached the timeout at 5000 frames without toppling for all trials, demonstrating the ability of this basic approach to prevent this failure mode; counterbalancing in response to measured forces (balance) was more efficient in use of time and material than unconditional counterbalancing (planned) (Table 3).

Interestingly, on flat ground, the safer algorithm was able to build cantilevers on average 1.5 m further when unanchored than when anchored (Tables 2, 4). This is because in the anchored case, failure typically occurred when joints in nodes attached to the ground broke due to excessive reaction torque. In the unanchored case, this reaction torque is released as the ground-resting nodes lift off of the ground, and loads are redirected to the nodes that remain on the ground. Ultimately, connections at the latter nodes will break, but on average later in the simulation than when failure would have occurred with anchored nodes.

For all agent algorithms, failures occasionally cascade: i.e., when one connection breaks, the redistribution of forces that results can lead to forces at another connection exceeding the threshold and breaking there, and so on. In our simulation environment, any broken joint constitutes a failure, whether in isolation or leading to a cascading failure. In future work, a distinction could be made between minor failures, which could potentially be compensated for as the swarm continues to work, and catastrophic failures, where damage is severe and construction cannot effectively continue.

Fig. 13

Typical sequence for the balance variant in an unstructured environment. a Shows the initiation of a trial in which a pre-assembled triangle is allowed to fall from height of $y = 1 m$, finding equilibrium in the irregular terrain (b) before agents begin adding struts. In some cases, the structure rocks forward without breaking (f), exposing new building sites, which can then be filled in with struts newly conforming to the space (g–h)

Our results show that the balance algorithm, which incorporates the local force awareness of safer and also pays attention to cues at the origin node to determine the need for counterbalancing, builds cantilevers that stably reach further than any other variant considered, in both structured and unstructured terrains. Tables 4 and 5 show that building in irregular terrain is much less predictable than in flat terrain. However, the kind of circumstances where the distributed construction methods that we propose are more likely to be useful would be in unstructured and unpredictable environments. In a structured or prepared environment, a building sequence could hypothetically be preplanned in detail so as to prevent breaking or toppling; however, this would not hold in an unstructured or changing environment. A responsive approach like those considered here allows construction to adapt to unknown or dynamic conditions (Fig. 13).

The balance algorithm scales effectively with swarm size at least up to teams of dozens of robots (Fig. 12, Table 6). The size of the structures they can build is not affected by the number of robots, and the time taken to do so decreases proportionally with the swarm size, without being too badly affected by interference between robots. The deployment rule used here, where robots wait to enter the workspace until the cache is unoccupied for five consecutive steps, helps prevent traffic congestion and lets the size of the swarm adapt to the amount of available work.

Fig. 14

a Shows a possible extension to three dimensions consisting of 3 parallel lattices composed of triangles (yellow) and connected by struts of equal length. This configuration is unstable in 3 planes, indicated by the teal, blue, and magenta squares. The only fully stable configuration of struts of equal length is a tetrahedral lattice b, in which 12 struts meet at each node. A cubic lattice composed of vertex-connected octahedra c is one possible method of simplifying the connection between units, though vertex connections perform poorly under bending forces. A lattice composed of edge-connected octahedra d would be better at resisting bending forces. These cellular units could be equipped with force sensors (shown in blue). A measure of the difference in forces between two sensors on the same face can be used as a proxy for bending forces, which would indicate potential failure (Color figure online)

7 Limitations and future work

While the heuristics proposed can be useful for improving the performance of a decentralized robot construction system of the sort we consider, they do not provide a guarantee for stability throughout the process, especially in unstructured environments. Due to the complexity of irregular environments, it may not be possible to completely prevent the failure mode of toppling by looking at forces only at one single node. One area for future work is to look at ways a robot could collect and integrate information as it moves over a structure to give it a more informed basis for its actions, which may further improve performance and perhaps make possible formal guarantees of safety.

Another important area for future work is to generalize the approaches described in this paper to 3D construction systems (Fig. 14). Due to the dexterity required to attach many struts at a single node (Fig. 14b), it may be more effective to build not with struts as the elementary unit, but with prefabricated cellular units: higher-order compositions of struts pre-assembled in a triangulated and thus stable-by-construction configuration (Fig. 14c, d). Such units would preserve the favorable strength-to-weight ratio of truss structures while simplifying the connection between units, as has been reported by others (Trinh et al. 2017). In a cubic lattice of cellular structures, joints consist of orthogonal connections between two faces, which would require less dexterity than the many diagonal connections that would be needed for 3D node-and-strut construction. While cellular lattices are likely the most straightforward extension to 3D, the regularity of the lattice might present complications in conforming to unstructured terrains, which will continue to be a motivating factor of this research. The design and instrumentation of custom building units will be explored further in future work.

Looking at structures that are built off-lattice is an approach that might be more conducive to adapting to a challenging terrain. This could resemble a construction type similar to conventional scaffolding tube-and-clamp systems, where connections are made between two struts at arbitrary positions along their length, and potentially arbitrary angles. While such a system would have a considerably compromised strength-to-weight ratio, it might be more capable of conforming in detail to an unstructured terrain, and allow adding extra material to provide reinforcement in places where extra structural strength is needed. The costs and benefits of both the lattice and off-lattice approaches will be evaluated in future work.

For either approach, we could consider the use of heterogeneous materials (more heavily reinforced or lighter materials to be used in suitable locations). For example, in the work presented, there was a high likelihood that joints at ground-resting nodes would be the first to break; using stronger elements at these known locations would allow structures to be built further on average.

Another issue which so far has not been addressed is the culmination of a successful building sequence, where a cantilevering truss touches down on the far side of a chasm, becoming a bridge. This transition represents a drastic shift in structural state, where forces throughout the structure change dramatically. Moreover, once the structure is supported at both ends, material previously needed to counterbalance may no longer be necessary. In this more complete building sequence, the possibility of allowing disassembly and reuse of building materials becomes more relevant. The counterbalanced variants presented suggest that they might require considerably more material than a conventional truss bridge. However, if disassembly were permitted, the extra struts could be removed or repositioned, leading to a more structurally optimal bridge in the end.

Finally, future work will return to the topic of hardware for systems supporting the theory presented in this paper, further developing building modules that are able to sense forces, and eventually robotic agents capable of manipulating and moving over material to build structures that are resilient to perturbations and remain stable throughout their construction.