A Compiler for Scalable Construction by the TERMES Robot Collective

The TERMES system is a robot collective capable of autonomous construction of 3D user-specified structures. A key component of the framework is an off-line compiler which takes in a structure blueprint and generates a directed map, in turn permitting an arbitrary number of robots to perform decentralized construction in a provably correct manner. In past work, this compiler was limited to a non-optimized search approach which scaled poorly with the structure size. Here, we first recast the process as a constraint satisfaction problem (CSP) to apply well-known optimizations for solving CSP and present new scalable compiler schemes and the ability to quickly generate provably correct maps (or find that none exist) of structures with up to 1 million bricks. We compare the performance of the compilers on a range of structures, and show how the completion time is related to the inter-dependencies between built locations. Second, we show how the transition probability between locations in the structure affect assembly time. While the exact solution for the expected completion time is difficult to compute, we evaluate different objective functions for the transition probabilities and show that these optimizations can drastically improve overall efficiency. This work represents an important step towards collective robotic construction of real-world structures. (C) 2019 Elsevier B.V. All rights reserved.