CRII: AF: Reconfiguration Algorithms for Programmable Matter

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

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.