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

在大量的应用中，构建和修改由许多基本组件组成的结构是一个重要而自然的目标。在许多情况下，自主机器人的使用承诺显著的优势，但也面临许多额外的复杂性。这适用于各种各样的情景，但在难以直接进行人类操作的非常大和非常小的维度上尤其如此，例如在地外空间或微观环境中。近年来，在促进整体突破方面取得了重大进展，首先，超轻和可扩展的复合晶格材料允许构建模块化，可重构的晶格结构；它们的细胞结构还解决了精度和纠错问题，使其能够专注于潜在的离散组合结构。其次，简单的自主机器人的发展使得使用大量的机器人来执行复杂的任务，无论是在微观还是宏观层面。在这个项目中，我们解决了这个层次结构的下一步：我们如何使一群机器人掌握基于细胞结构的一系列建筑任务，比如建造、维护和重新配置由大量基本组件组成的结构？实现可伸缩性取决于大量这样的简单机器人之间的并行性，将分布式协调的算法机制与解决各种几何方面的优化方法相结合。在提议的工作中，我们的目标是为处理这些挑战奠定基础，而不依赖于具有巨大个人能力的机器人。相反，我们将开发算法方法来协调大群个体能力有限的自主机器人，这些机器人能够共同构建、维护和重新配置大型结构。这些结构可能由超轻的、模块化的、基于格子的组件组成，这些组件可能由（可能是微型的）机器人自己形成，或者在微型工厂的帮助下建造。将特别注意分散式和集中式方法的结合：对建筑和重新配置的所有详细方面进行集中控制既不可能也没有必要，因此发展分散式机制对所产生的系统的全面运作至关重要；另一方面，完全放弃全局控制的所有特征既是不必要的，也是不可取的。虽然我们自己的目标是为这些挑战提供算法方法，但我们将通过与众多获奖的国际同事密切合作，提供理论基础，背景和现实世界的实现，他们结合了相关领域的专业知识。

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.