EAGER: Self-organizing particle systems: Models and algorithms

点击翻译按钮获取中文摘要

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.The main objectives of this one-year project are (i) to develop appropriate models for particle systems; (ii) to develop self-organizing algorithms for smart paint problems; and (iii) to better educate the Computer Science (CS) Theory/Algorithms community on self-organizing particle systems. The proposed NSF sponsored workshop will foster collaboration of research in this interdisciplinary area.