Ameba-inspired Self-organizing Particle Systems

Abstract

Particle systems are physical systems of simple computational particles that can bond to neighboring particles and use these bonds 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. We attempt to bridge this gap by proposing a model inspired by the behavior of ameba that allows rigorous algorithmic research on self-organizing particle systems.