University of Liverpool

Department of Computer Science, School of EEE/CS, University of Liverpool, Liverpool, UK

The team from the University of Liverpool has been working on the algorithmic foundations of Programmable Matter since 2016. Their expertise lies on formal modeling of traditional and emerging computing systems, understanding their behavior and complexity both analytically and experimentally, and designing centralized and distributed algorithms for core tasks in those systems. Their work so far in programmable matter has focused on formal models of a number of potential systems, such as network constructors in dynamic environments and 2D reconfigurable systems in static environments via operations such as local rotation, sliding, or linear-strength pushing of modules. In this settings, they have been designing and formally analyzing reconfiguration algorithms (centralized and distributed) and have been providing feasibility and complexity characterizations (e.g., universal transformations, impossibility results, upper/lower bounds, and optimality). Their work in this area has led to publications in PODC, Distributed Computing, ICALP, JCSS, CACM, and ALGOSENSORS. At the same time, they are exploring, together with the School of Engineering at the University of Liverpool and international partners, novel engineering approaches towards realizing the programmable matter systems of the future.

In the 3D CATOMS project, they will be involved in (i) the development of abstract formal representations of 3D CATOMS, (ii) the characterization of the feasibility and the complexity of reconfiguration, (iii) the development and analysis (analytically and experimentally) of centralized and distributed reconfiguration algorithms for the feasible cases, (iv) the programming of the CATOMS to implement the most efficient algorithms.