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.