Algorithmic Foundations of Circuit-Based Programmable Matter

2014年，我们提出了变形人模型，用于可编程物质的严格算法研究。从那时起，该模型获得了相当大的发展势头，但它只允许缓慢的形状变换。最近，我们提出了一种对变形机器人模型的可重构电路扩展，以便在变形机器人结构中快速传播信息，并表明各种基本计算任务，如领导者选举或罗盘对准，可以比原始模型更快地解决。基于这一扩展，我们打算开发高度可扩展的分布式算法，用于形状变换、形状中的错误检测以及给定形状与目标形状的最佳匹配。这种高度可伸缩的算法对于使我们的研究结果具有足够的技术实现吸引力是至关重要的。

In 2014, we proposed the amoebot model for the rigorous algorithmic study of programmable matter. Since then, the model has gained considerable momentum, but it only allows slow shape transformations. Recently, we proposed a reconfigurable circuit extension of the amoebot model in order to quickly disseminate information in an amoebot structure and showed that various fundamental computational tasks like leader election or compass alignment can be solved significantly faster than in the original model. Based on this extension, we intend to develop highly scalable distributed algorithms for shape transformations, the detection of errors in shapes, and for a best possible matching of a given shape with some target shape. Such highly scalable algorithms are vital in order to make our research results sufficiently attractive for a technical realization.