In the field of programmable matter we consider materials that can change their physical properties such as shape, elasticity, conductivity, or color, based on programmable behavior and reacting to external influences. Various interpretations of programmable matter have been portrayed in popular science fiction, and there are many possible applications for such materials: Minimally invasive medical treatment, monitoring and repairing buildings and machines, advanced manufacturing, or exploration of hazardous or obstructed environments.

We view programmable matter as large systems of tiny particles with limited locomotion, computation and communication abilities. With recent advances in micro- and nanorobotics, it seems likely that the production of such particles will be possible within the next few decades.

In our research, we study programmable matter from a theoretical perspective. In order to program the particles in such a way that arbitrarily large numbers of them can cooperate to achieve complex goals in a reasonable time, the fundamental capabilities and limitations of such systems must be explored. Therefore, we use abstract mathematical models to focus on the most important aspects of programmable matter systems. Such models allow us to precisely formulate assumptions on the particles' abilities and rigorously analyze the correctness and runtime of algorithms. By these means, we explore under which assumptions the fundamental coordination problems can be solved and develop efficient distributed algorithms, building a theoretical foundation for future physical implementations.

Due to the local communication and movement constraints, many algorithms in the amoebot model require a runtime that grows at least linearly with the number of amoebots, which is generally too slow for real applications with many particles. This problem motivated two extensions of the amoebot model: Reconfigurable circuits and joint movements.

The reconfigurable circuit extension allows amoebots to construct communication networks, so-called circuits, on connected subgraphs of the amoebot structure. On the circuits, they can send primitive signals called beeps, which are transmitted instantaneously to all amoebots connected by a circuit. This extension allows much more efficient solutions for leader election and other problems, such as constructing spanning trees and shortest path forests.

The joint movement extension enables amoebots to push and pull each other with their contractions and expansions. Thereby, a chain of amoebots that expands together can cover a much greater distance than if all amoebots move separately from each other. This extension allows for rapid shape transformations and fast locomotion of an amoebot structure along a surface, but it introduces new coordination challenges to avoid collisions and conflicting movements.

The two extensions were inspired by the nervous and muscular system and are designed to work together. We hope to utilize communication via circuits to solve the coordination problems of joint movements and ultimately develop much more efficient shape formation algorithms.