Simulating Emergent Autonomous Construction with Smart Building Blocks

Jun. 11, 2019

At the end of the first year of the MEAM PhD program at Penn, there are the qualifying exams. Penn's quals process is unique: it is based on a semester-long independent study project. You propose the project in January, work on the thing all semester, and then write a report and give a presentation to a committee of professors, followed by a short oral exam about your research.

My independent study project investigated autonomous construction with 'smart' building blocks. I developed a distributed system that built structures with these smart blocks based on sets of local rules. I'll briefly describe the project below, and speculate about the future work, as part of my process to decide what to do next. For a more formal and detailed presentation of my research, please see my full report.

Research Goals

I've been researching in the field of autonomous construction for about 3 years now. In my view, there are two approaches to construction in unpredictable, real-world environments. You can use a sophisticated system that uses expensive sensors and cameras to build a comprehensive representation of the world, analyze this representation to determine the structure that should be built there, and precisely plan out a sequence of actions that builds this structure. An example of this might be a rover equipped with a robot arm, and cameras and LIDAR. It would perceive its environment, build a map, design a structure, and build it with the robot arm - basically, how humans build structures. This is difficult and expensive and not in any way a solved problem.

The other option is to use a decentralized, multi-agent system that makes use of simpler environmental information to build emergent structures according to sets of rules that are assessed by each agent. Examples of this are widespread in biology - termites build their mounds by responding to pheromone cues, depositing dirt where these cues have been left. This results in an emergent mound. Or beavers, which individually respond to the sound of running water in their dams by depositing more sticks. As all of the beavers perform this behavior, an emergent structure which dams waterways emerges.

For construction that must take place in perilous, unpredictable environments such as disaster areas or extraterrestrial terrains, the latter approach might be nearer at hand. The rules are simple, the capabilities required of each agent are relatively small, and the system is robust because of its redundancy. However, this approach might be limited in the complexity of structures that it builds - as humans, we build beatiful, architected structures that are (hopefully) perfectly designed to fit a large variety of purposes. A system that builds emergent structures is not capable of this sophistication with current technology.

A long-term goal of my research is to make this sort of construction more feasible and more appealing - to create a system that can build with complexity and beauty in unknown, unstructured environments. My research herein is a small step that builds on a great body of literature towards solving this and related problems.

The goal of my research is to enable adaptive construction with smart building blocks, by giving control of construction to the building blocks themselves. I developed a bipartite system of smart building blocks, which are blocks that have sensors and processors and can communicate locally, and actuator robots, which do the actual building, moving across the structure placing new material according to building block instructions. This system architecture has a number of benefits:

  1. It is cheaper than doing the same thing with modular robots
  2. It enables instantaneous response to damage or environmental changes, as opposed to a system using passive building blocks, in which these damages or changes would have to be discovered
  3. Smart blocks can continually embody the state of the system better than an external observation system
  4. Construction with smart blocks is faster than construction with passive building blocks [Werfel & Nagpal]

My Work

In simulation (just using Matlab), I created this system, and tested its capabilities. As a test structure, I chose to build a floodwall, because they fit the use cases of my system: they are built in dangerous, unstructured environments, their construction is time sensitive, they must respond to damage and changes in the environment, and they can be defined by a simple function (keep water out!).

This last characteristic is especially important. I am loading up all of my smart building blocks with the same set of local rules, which the smart blocks use to decide where new building material should be placed - in this way, the local rules and the environmental factors determine the final shape the structure will take. It is difficult to design these local rules for specific end-goal structures, but the function-based definition of a floodwall makes it much easier.

I developed several sets of local rules, but the most important I call the 'hydrostatic' set of rules. The building blocks direct construction wherever water is present, aiming to contain it in a given containment direction. They determine the goal thickness of the wall based on the hydrostatic pressure that is detected by the building blocks. This results in a stable, staircase-shaped wall cross-section.

Here is an example of the system at work, constructing a floodwall:

I performed experiments to test the systems ability to adapt to different environments, adapt to changes in its environment, and repair damage. Here, the system responds to rising water levels during construction:

In this experiment, the system responds to a hole that is broken in the top of the structure - we take the blocks away instantaneously, and the system must discover the damage and take action to repair it:

I also looked at how the system performance, and the cost of construction, changed as the size of the structure increased. By running the simulation with a great variety of structure sizes, I analyzed how the system scales. I found that the number of messages that each building block must handle per time step decreased as I increased structure size, and that the number of messages each actuator robot must handle was relatively constant. The only problem was construction time: it takes a longer time to build a larger structure. This is an obvious limit on construction, but the problem can be addressed by using multiple actuator robots to build, rather than the single actuator robot I used in all my tests.

For more information and details on this research, please see my full report.

Future Work

There are many immediate extensions of this work that could bring it closer to real-world application. I am interested in implementing the system with multiple actuator robots, and addressing the problems of coordinating these robots and avoiding collisions. I also want to look at the robustness of the system; it is built with purposefully cheap sensors and processors, and so noise and malfunctions are expected. How well can the system tolerate this? And I'm also interested in the use of different types of sensor information to inform construction, especially internal force sensors. This could lead to distributed construction of highly stable structures.

One larger goal of this field is to enable robust and complex construction in unstructured environments. When considering the extension of my research towards this eventual goal, two primary questions arise: how do we generate local rule sets autonomously, and how do we use these local rule sets to template complex structures? The former question is difficult to answer, and has only been approached briefly in the literature, with methods such as evolutionary algorithms. The second question seems more tractable: we may be able to form templates of local rule sets that result in a more complex structure. For example, we might have a local rule set for a wall, a pillar, and a roof. We could spatially combine these local rule sets to make a roofed structure that could be stored simply.