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.