Programmable parts: A demonstration of the grammatical approach to self-organization

In this paper, we introduce a robotic implementation of the theory of graph grammars[12], which we use to model and direct self-organization in a formal, predictable and provably-correct fashion. The robots, which we call programmable parts, float passively on an air table and bind to each other upon random collisions. Once attached, they execute local rules that determine how their internal states change and whether they should remain bound. We demonstrate through experiments how they can self-organize into a global structure by executing a common graph grammar in a completely distributed fashion. The system also presents a challenge to the grammatical method (and to distributed systems approaches in general) due to the stochastic nature of its dynamics. We conclude by discussing these challenges and our initial approach to addressing them.