AF: Small: Self-Organizing Particle Systems

AF：小型：自组织粒子系统

• 批准号: 1422603
• 负责人: Andrea Richa
• 金额: $ 45万
• 依托单位: Arizona State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422603&HistoricalAwards=false
• 关键词: AF; Small; Self; Organizing; Particle

The goal of this project is to lay the foundations for algorithmic research on self-organizing particle systems. Particle systems are physical systems of simple computational particles that can bond to other particles and that can use these bonds in order to communicate with neighboring particles and to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far.This project will prepare the ground for rigorous algorithmic research on self-organizing particle systems by proposing basic models and solving some basic algorithmic problems in this area. More specifically, the main objectives of this three-year project are (i) to refine an amoeba-inspired model  for particle systems in 2D, and to develop appropriate models for particle systems in 3D; and (ii) to develop self-organizing algorithms for the smart paint problem, covering and bridging problems, shape formation problems, and the macrophage problem in 2D and 3D. A transformative, novel thinking approach will be needed if one indeed wants to capture the essential nature of these systems, in some ways mimicking those that already exist in nature.The proposed research will have an impact in several respects, such as: (i) bridging the gap between theory and practice in the area of self-organizing particle systems, with impact on many application areas such as micro-fabrication and cellular engineering; (ii) international collaboration; (iii) multidisciplinary activities, since the topics in this proposal will foster collaboration with researchers in multiple areas such as nano-scale micro-fabrication, cellular engineering, nano-scale medical applications, biochemistry, and computer science; and (iv) enhancing diversity at Arizona State University and at the Computer Science Theory\Algorithms community at large.

该项目的目的是为自组织粒子系统奠定基础。粒子系统是简单计算粒子的物理系统，可以与其他粒子键合，并且可以使用这些键与相邻粒子进行通信，并从一个位置转移到另一个位置（非占用）位置。预计这些粒子系统能够自组织以适应所需的形状而没有任何中央控制。自组织粒子系统具有许多有趣的应用，例如用于监测和修复目的的涂料对象以及用于手术和分子尺度电子结构的纳米级设备的形成。尽管在这一领域有很多系统工作，尤其是在模块化自我可控机器人系统的背景下，到目前为止，在该领域中，仅在该领域完成了很少的理论工作。该项目将通过提出基本模型并解决该领域的一些基本算法问题来为对自我组织粒子系统的严格算法研究做好准备。更具体地说，这个三年项目的主要目标是（i）完善2D中粒子系统的变形虫启发的模型，并为3D中的粒子系统开发适当的模型； （ii）为智能油漆问题开发自组织算法，涵盖和桥接问题，形状形成问题以及2D和3D中的巨噬细胞问题。如果确实想捕获这些系统的基本本质，以某种方式模仿已经存在的人的基本本质，则需要进行变革，新颖的思维方法。拟议的研究将在几个方面产生影响，例如：（i）在自我组织粒子系统领域中弥合理论和实践之间的差距，并对许多应用领域（例如微型构造和细胞蜂窝式和蜂窝式发动机）产生影响； （ii）国际合作； （iii）多学科活动，因为该提案中的主题将促进与纳米级微型制作，蜂窝工程，纳米级医学应用，生物化学和计算机科学等多个领域的研究人员合作； （iv）在亚利桑那州立大学和计算机科学理论\算法社区中增强多样性。

项目成果

On the runtime of universal coating for programmable matter

• DOI: 10.1007/s11047-017-9658-6
• 发表时间: 2018-03-01
• 期刊: NATURAL COMPUTING
• 影响因子: 2.1
• 作者: Daymude, Joshua J.;Derakhshandeh, Zahra;Strothmann, Thim
• 通讯作者: Strothmann, Thim

Collaborative Computation in Self-Organizing Particle Systems

• DOI: 10.1007/978-3-319-92435-9_14
• 发表时间: 2017-10
• 作者: Alexandra M. Porter;A. Richa

Improved Leader Election for Self-organizing Programmable Matter

• DOI: 10.1007/978-3-319-72751-6_10
• 发表时间: 2017-01-01
• 期刊: Algorithms for Sensor Systems. 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017. Revised Selected Papers: LNCS 10718
• 作者: Daymude, Joshua J.;Gmyr, Robert;Strothmann, Thim
• 通讯作者: Strothmann, Thim

Universal coating for programmable matter

用于可编程物质的通用涂层

• DOI: 10.1016/j.tcs.2016.02.039
• 发表时间: 2017
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Derakhshandeh, Zahra;Gmyr, Robert;Richa, Andréa W.;Scheideler, Christian;Strothmann, Thim
• 通讯作者: Strothmann, Thim