This proposal is submitted by Prof. Andrea W. Richa, Arizona State University, to be considered under the CCF-AF program by Dr. Balasubramanian Kalyanasundaram.

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 some 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-inpired 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.

This project is a natural continuation of the PI's seed one-year NSF EAGER award, and is a necessary component of the work that is needed to lay the grounds for theoretical research on particle systems comprised of computational particles such as nano-sensor nodes.

- Intellectual Merit:

This three-year project will bridge the gap between applied and theoretical research in self-organizing particle systems both in terms of models and algorithmic research: It will significantly advance the field of self-organizing particle systems from an algorithmic/computational point-of-view.

- Broader Impact:

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 microfabrication and cellular engineering; (ii) international collaboration, since we will further foster the successful collaboration with Prof. Scheideler and the U. of Paderborn, Germany; (iii) multidisciplinary activities, since the topics in this proposal will foster collaboration with researchers in transdisciplinary areas such as nano-scale microfabrication, cellular engineering, nano-scale medical applications, biochemistry, etc.; (iv) advancing education at ASU; and (v) enhancing diversity at ASU and at the CS Theory\Algorithms at large.