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.