ProjectsProgrammable Matter

Programmable matter is composed of many small and simple robots that together form smart objects. It has been featured in movies, such as in the form of the microbots in "Big Hero 6", and is nearly a reality today. There are many use cases for programmable matter, such as prototyping, construction, and repair of smart objects. Objects made from programmable matter can be changed interactively and directly. Programmable matter has the clear advantage over 3D printing that there is no loss of material and (next to) no waiting time, enabling fast design cycles and reducing waste.

The robots that make up a programmable matter system have limited power, limited memory, communicate only with local neighbors, and can run simple programs. Researchers in Theoretical Computer Science are studying a variety of algorithmic models for programmable matter. The Applied Geometric Algorithms group focuses on two models: amoebots and sliding cubes.

Contact: prof.dr. Bettina Speckmann ∙ dr. Tim Ophelders ∙ dr. Tom Peters

Sliding Cubes

In the sliding cubes model, the robots are cubes which execute only two simple moves (see figure). In this model, the robots are always connected into a single configuration. We developed efficient and provably correct algorithms to reconfigure with sliding cubes and we implemented and tested our algorithms in simulation environments. We also studied the 2-dimensional sliding squares version of this model; our 2D results and software can be found here.

Videos

The first video explains one of our cube reconfiguration algorithms in more detail, the second video shows a simulated construction of the Eiffel Tower using this algorithm, and the third video illustrates why a specific straightforward approach to reconfiguring cubes can never work.

Amoebots

In the amoebots model, the robots occupy nodes of a triangular grid in the 2D plane. A robot can occupy either a single node or a pair of adjacent nodes. Robots can move by expansions and contractions (see Figure). Moreover, the robots can communicate only with their direct neighbors on the grid; communication at large distances is hence a challenge in the amoebot model. We developed an efficient algorithm to reconfigure any amoebot configuration into any other configuration. The video shows how our algorithm reconfigures an amoebot dove into an amoebot fish. Our algorithm is the first that can reconfigure directly; it does not need to proceed via an intermediate configuration.

Building Orders

When building physical structures out of programmable matter, the restrictions of the physical world place restrictions on the order in which building blocks can be placed. Furthermore, certain placement orders are faster than others. As part of a collaboration with NASA, we designed a building order for programmable matter structures that optimizes for fast and parallel construction.

Publications

Tom Peters, Geometric Algorithms for Programmable Matter, PhD Thesis, TU Eindhoven, 2024

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann, Optimal In-Place Compaction of Sliding Cubes, Journal of Computational Geometry 16(1):800–820, 2026

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann, Optimal In-Place Compaction of Sliding Cubes (Media Exposition), Proc. 40th International Symposium on Computational Geometry (SoCG), pp. 89:1–89:4, 2024

Hugo Akitaya, Erik Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms, Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares, Proc. 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 4:1–4:19, 2022

Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms, Hiding sliding cubes: Why reconfiguring modular robots is not easy (media exposition), Proc. 36th International Symposium on Computational Geometry (SoCG), pp. 78:1-78:5, 2020

Irina Kostitsyna, Tom Peters, and Bettina Speckmann, Fast reconfiguration for programmable matter, Proc. 37th International Symposium on Distributed Computing (DISC), pp. 27:1-27:21, 2023, full version on arXiv

Tom Peters, Kenneth Cheung, and Irina Kostitsyna, Assembly Order Planning for Modular Structures By Autonomous Multi-Robot Systems, IEEE International Conference on Robotics & Automation, 2025

Thijs van der Horst, Maarten Löffler, Tim Ophelders, and Tom Peters, Reconfiguration of Squares Using a Constant Number of Moves Each, European Workshop on Computational Geometry, 2026