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

• Applicants: Professor Dr. Sándor Fekete; Professor Dr. Christian Scheffer
• Subject Area: Theoretical Computer Science
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 530918134

Building and modifying structures consisting of many basic components is an important and natural objective in a vast array of applications. In many cases, the use of autonomous robots promises significant advantages, but also faces numerous additional complications. This applies to a wide spectrum of scenarios, but it is particularly true at both very large and very small dimensions that are hard to access for direct human manipulation, e.g., in extraterrestrial space or in microscopic environments. In recent years, significant advances have been made to facilitate overall breakthroughs, Firstly, ultralight and scalable composite lattice materials allow the construction of modular, reconfigurable, lattice-based structures; their cellular structure also resolves issues of accuracy and error correction, allowing it to focus on the underlying discrete, combinatorial structures. Secondly the development of simple autonomous robots enables using large numbers to carry out complex tasks, both at microscopic and macroscopic dimensions. In this project, we address the next step in this hierarchy: How can we enable a collective of robots to master a spectrum of construction tasks that are 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 ultralight, 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 the development of distributed mechanisms is 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. While our own aim is for algorithmic methods for these challenges, with a focus on theoretical foundations, context and real-world realization will be provided through close collaboration with a number of award-winning international colleagues who combine expertise in a spectrum of relevant areas.

• DFG Programme: Research Grants
• International Connection: USA
• Cooperation Partners: Professor Dr. Aaron T. Becker, Ph.D.; Dr. Kenneth C. Cheung, Ph.D.; Professor Dr. Erik Demaine, Ph.D.; Professor Dr. Neil A. Gershenfeld, Ph.D.; Professor Dr. Sven Koenig; Professor Dr. Joseph S. B. Mitchell, Ph.D.