Models and Algorithms for Systems of Programmable Particles

This PhD project will investigate the algorithmic framework necessary for developing systems of
programmable particles. These are typically systems of tiny entities equipped with weak computing
capabilities. Some systems have the added capacity for actuation. Programmable entities can show
substantial dynamism in space and time. During the project, the student is expected to explore
topics from the related areas of Population Protocols and Network Constructors, Dynamic Networks,
Discrete Dynamic Systems, and Algorithmic properties of Programmable Matter. This research could
reveal new modes of computing and establish computability and complexity insights about them.
The student will be based in CS but co-supervised by a Mechanical Engineering colleague, enabling
the provision of realistic physical parameters to enrich the computational models. The project shall,
for each model: explore adaptations of existing problems, identify and formulate new problems (as
they arise), investigate feasibility and efficiency questions, and develop a number of centralised and
distributed algorithms. The various models shall be compared (e.g. through simulation relations,
characterisations, and complexity classes) and the developed solutions shall be tested analytically
and experimentally (e.g. through simulations and visualisation).