AF: Small: Self-Organizing Particle Systems

Arizona State University, Scottsdale AZ

Investigators

Abstract

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.