AF: Small: Self-Organizing Particle Systems

该项目的目标是为自组织粒子系统的算法研究奠定基础。粒子系统是由简单的计算粒子组成的物理系统，这些粒子可以与其他粒子结合，并且可以利用这些结合与邻近的粒子进行通信，并从一个点移动到另一个（未被占用的）点。这些粒子系统应该能够自组织，以便在没有任何中央控制的情况下适应所需的形状。自组织粒子系统有许多有趣的应用，如用于监测和修复目的的涂层物体，以及用于外科手术和分子尺度电子结构的纳米级设备的形成。虽然在这一领域已经有相当多的系统工作，特别是在模块化自重构机器人系统的背景下，但到目前为止，这一领域的理论工作还很少。本项目将提出自组织粒子系统的基本模型，解决该领域的一些基本算法问题，为自组织粒子系统的严格算法研究奠定基础。更具体地说，这个为期三年的项目的主要目标是：(i)完善一个受阿米巴虫启发的二维粒子系统模型，并为三维粒子系统开发合适的模型；（ii）开发自组织算法，用于2D和3D中的智能油漆问题、覆盖和桥接问题、形状形成问题以及巨噬细胞问题。如果人们真的想要捕捉这些系统的本质，以某种方式模仿自然界中已经存在的系统，就需要一种变革性的、新颖的思维方法。提出的研究将在几个方面产生影响，例如：(i)弥合自组织粒子系统领域理论与实践之间的差距，对微制造和细胞工程等许多应用领域产生影响；国际合作；（三）多学科活动，因为本提案的主题将促进与多个领域的研究人员的合作，如纳米级微制造、细胞工程、纳米级医疗应用、生物化学和计算机科学；（iv）加强亚利桑那州立大学和整个计算机科学理论和算法社区的多样性。

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.