CRII: AF: Reconfiguration Algorithms for Programmable Matter

可编程物质是指能够根据需要改变其物理性质的材料。可编程物质的一个很有前途的实现是使用模块化机器人，它们可以彼此连接和分离，相互通信和移动，有效地改变系统的形状。这赋予了系统灵活性，以适应不同的情况和执行新的任务，并具有弹性，因为模块是可互换的，故障部件可以通过重新配置来替换。然而，形状重构仍然是该领域最大的算法挑战之一。这些问题引起了理论计算机科学界的兴趣，这方面的工作越来越多。虽然文献中的一些实际方法没有被证明可以在每个场景中找到重构，但理论界提出的有效算法可以在非现实的数学模型中运行。这个项目的重点是获得新的算法，并使现有的算法适应更现实的模型，推进该领域的最新技术。该奖项支持的研究将提供一个统一的框架，对文献中由于不同硬件约束和方法而存在的不同模型进行分类。在这个框架内，已知的技术将适应新的模型，新的算法将被开发出来。由于已知重构问题在某些模型中难以计算，因此将研究近似算法。在重构领域，近似算法的探索相对较少，因此，这样的结果将引起更广泛的理论界的兴趣。可编程物质和可重构机器人领域本质上是多学科的，汇集了计算机科学、机器人技术、机械和电气工程、材料科学等方面的努力。该项目还提出了一项调查，以传播计算几何社区中被其他领域所忽视的知识。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Programmable matter refers to materials with the ability to change their physical properties on demand. A promising implementation of programmable matter uses modular robots that can attach and detach from each other, communicate and move relative to each other, effectively changing theshape of the system. This gives the system flexibility to adapt to different situations and perform new tasks, and resilience since modules are interchangeable and faulty parts can be replaced via reconfiguration. Shape reconfiguration, however, remains one of the biggest algorithmic challenges in the field. Such problems have captivated the interest of the theoretical computer science community, evidenced by a growing body of work in the topic. While some practical approaches in the literature are not proven to find a reconfiguration in every scenario, efficient algorithms proposed by the theoretical community operate in non-realistic mathematical models. This project focuses on obtaining new algorithms and adapting existing ones to more realistic models, advancing the state-of-the-art in the area.The research supported by this award will provide a unifying framework to categorize the different models that exist in the literature due to the different hardware constraints and approaches. Within this framework, known techniques will be adapted to new models, and new algorithms will be developed. Since reconfiguration problems are known to be computationally hard in some models, approximation algorithms will be studied. In the field of reconfiguration, approximation algorithms are relatively unexplored, thus, such results will interest the broader theoretical community. The fields of Programmable Matter and Reconfigurable Robotics are intrinsically multidisciplinary, aggregating efforts in computer science, robotics, mechanical and electrical engineering, material sciences among others. This project also proposes a survey to disseminate the knowledge created within the Computational Geometry community that have been overlooked by other fields.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.