AF: EAGER: Randomization and Parallelization in Algorithmic Self-Assembly

AF：EAGER：算法自组装中的随机化和并行化

• 批准号: 1555626
• 负责人: Robert Schweller
• 金额: $ 9.98万
• 依托单位: The University of Texas Rio Grande Valley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555626&HistoricalAwards=false
• 关键词: AF; EAGER; Randomization; Parallelization; Algorithmic

In this project the PIs explore various theoretical models of algorithmic self-assembly, as well as the development of new models while engaging a number of undergraduate and graduate students in research activities. Self-assembly is the process by which simple, unorganized components autonomously combine to form larger, more complex structures. This process is abundant in nature and is a key underlying mechanism for the construction of biological organisms. Researchers are turning to self-assembly technology for the design of ever smaller, more complex, and precise nanoscale devices, and as an emerging fundamental tool for nanotechnology. The possible revolutionary changes to healthcare, computation, and engineering make this an exciting and important area of research.The focus of this project is algorithmic self-assembly in which the objects of a system assemble through local interactions that simulate sophisticated computation to efficiently assemble target shapes and patterns. Fully understanding the power of self-assembly systems, and how to control them, presents the possibility of designing molecular algorithms for precise and efficient manipulation of matter at the nanoscale. Developing models and theory towards this goal that are closely tied to experimental reality is the focus of this project. The PIs explore various established tile-based theoretical models of self-assembly, as well as the development of new models motivated by current experimental technology. This includes examining specific problems within tile self-assembly systems, and the creation and use of randomness within different models. Using randomness along with the parallel computation of self-assembly systems should allow for novel solutions and efficient running times for many useful functions.Technical aspects of this project focus on the tools of randomization and parallelization in the context of tile self-assembly theory. Specific directions are as follows. The PIs consider the design of concentration robust tile systems in which randomized abstract tile assembly systems are converted into equivalent systems whose probability distribution over assemblies is maintained over adversarially chosen concentration assignments of tile species. The goal of this direction is to generate a toolbox for general conversion of tile systems into approximately equivalent systems that are robust to concentration choice. The PIs further examine the application of such robust randomized systems for the parallelized solution to classic computational problems including sorting, primality testing, and the general simulation of randomized boolean circuits. The PIs also study complexities related to h-handed self-assembly in which up to h prebuilt assemblies may combine in a single step. Finally, the continued development and improvement of the VersaTile and Nubot simulation software are also an important aspect of this project. These systems are used for verification and educational purposes in research allowing users to easily create, test, modify, and visualize the self-assembly process.In tandem with the theoretical work described, a major goal of this project is to increase research participation among students at the University of Texas - Rio Grande Valley and increase the throughput of undergraduate and masters students who enroll in Ph.D. programs in Computer Science. This project includes support for undergraduate and graduate student research assistantships, as well as the extension of a successful ongoing series of research seminars, hosted by the PIs, focused on attracting undergraduate student participation and co-authorship. The University of Texas - Rio Grande Valley is a minority-serving institution that has about 30,000 students with a 90% Hispanic and 55% female student population. Due to these demographics, this project offers a rare opportunity to make a substantial impact on broadening participation among under-represented minority groups in the field of Computer Science.

在这个项目中，PI探索算法自组装的各种理论模型，以及新模型的开发，同时吸引了一些本科生和研究生参与研究活动。 自组装是简单的、无组织的部件自主地联合收割机组合成更大、更复杂的结构的过程。 这个过程在自然界中是丰富的，是生物有机体构建的关键基础机制。 研究人员正在转向自组装技术，用于设计更小，更复杂，更精确的纳米级器件，并作为纳米技术的新兴基础工具。 医疗保健、计算和工程可能发生的革命性变化使其成为一个令人兴奋和重要的研究领域。该项目的重点是算法自组装，其中系统的对象通过模拟复杂计算的局部交互组装，以有效地组装目标形状和图案。 充分理解自组装系统的力量，以及如何控制它们，提出了设计分子算法的可能性，以精确和有效地操纵纳米级的物质。 开发模型和理论，实现这一目标，是紧密联系在一起的实验现实是这个项目的重点。 PI探索各种已建立的基于瓦片的自组装理论模型，以及由当前实验技术驱动的新模型的开发。 这包括检查瓷砖自组装系统中的特定问题，以及在不同模型中创建和使用随机性。 使用随机性沿着自组装系统的并行计算应该为许多有用的功能提供新颖的解决方案和高效的运行时间。该项目的技术方面重点关注自组装理论背景下的随机化和并行化工具。 具体方向如下。 PI考虑浓度鲁棒瓦片系统的设计，其中随机抽象瓦片组装系统转换成等效系统，其概率分布在组件上保持在对抗选择的瓦片种类的浓度分配。 这个方向的目标是生成一个工具箱，用于将瓷砖系统转换为对浓度选择具有鲁棒性的近似等效系统。 PI进一步研究了这种强大的随机化系统的并行化解决方案的经典计算问题，包括排序，素性测试，随机布尔电路的一般模拟的应用。 PI还研究了与h-手自组装相关的复杂性，其中多达h个预构建组件可以在单个步骤中结合联合收割机。 最后，VersaTile和Nubot仿真软件的持续开发和改进也是该项目的一个重要方面。 这些系统用于研究中的验证和教育目的，使用户能够轻松创建、测试、修改和可视化自组装过程。与所描述的理论工作相结合，该项目的主要目标是提高德克萨斯大学-格兰德河谷分校学生的研究参与度，并提高攻读博士学位的本科生和硕士生的吞吐量。在计算机科学的程序。 该项目包括对本科生和研究生研究助学金的支持，以及由PI主办的一系列成功的持续研究研讨会的延伸，重点是吸引本科生的参与和合著。 德克萨斯大学-格兰德河谷分校是一所少数民族服务机构，拥有约30，000名学生，其中90%为西班牙裔学生，55%为女性学生。 由于这些人口统计数据，该项目提供了一个难得的机会，使在计算机科学领域的代表性不足的少数群体之间扩大参与产生重大影响。

项目成果

Self-assembly of shapes at constant scale using repulsive forces

• DOI: 10.1007/s11047-018-9707-9
• 发表时间: 2016-08
• 期刊: Natural Computing
• 影响因子: 2.1
• 作者: Austin Luchsinger;R. Schweller;Tim Wylie