Algorithmic Foundations for Constructing and Reconfiguring Large­-Scale Structures with Simple Robots

We study a fundamental challenge for scalable construction of large structures: How can we enable a collective of robots to master a spectrum of construction tasks based on cellular structures, such as building, maintaining and reconfiguring constructions consisting of a large number of basic components? Achieving scalability hinges on parallelism between large numbers of such simple robots, combining algorithmic mechanisms for distributed coordination with optimization methods that address a variety of geometric aspects. In the proposed work, we aim to lay the foundations for handling these challenges without relying on robots of tremendous individual powers. Instead, we will develop algorithmic methods for coordinating large swarms of autonomous robots of limited individual capabilities that together are able to build, maintain and reconfigure large structures. These structures may consist of ultra-light, modular, lattice-based components, that may be formed by (possibly microscopic) robots themselves, or constructed with the help of micro-factories. Special attention will be given to the combination of distributed and centralized methods: Central control over all detailed aspects of construction and reconfiguration is neither possible nor necessary, so distributed mechanisms are crucial for the overall functioning of the resulting systems; on the other hand, it is both unnecessary and undesirable to completely abandon all features of global control.