SoftwareSliding Squares and Cubes

As part of our research into modular robots, we investigated the sliding cube model. In this model, robots consist of cube-shaped building blocks called modules. These modules can move within the three-dimensional grid, relative to each other, so that the robot is able to change its overall shape. The central question is: given the current configuration of the robot, and a desired target shape, how do we efficiently move modules to actually reach this target shape?

A variant of this question is about the two-dimensional equivalent of this problem (the sliding square model), in which modules are square-shaped and live in the two-dimensional grid.


To investigate the sliding square model, we developed SquareSlider, a visualization tool and framework to experiment with the sliding square model. SquareSlider is available here. We produced an explanatory video:

Willem Sonke and Jules Wulms, An Interactive Framework for Reconfiguration in the Sliding Square Model (Media Exposition), Proc. 38th International Symposium on Computational Geometry (SoCG), pp. 70:1-70:4, 2022


In our paper

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 2022), pp. 4:1-4:19, 2022

we proposed a novel algorithm called Gather&Compact to reconfigure modular robots formed by edge-connected squares.

The implementation we created for this paper is now available through SquareSlider (see above). For reproducibility reasons, we also still offer the original version of the code and the datasets generated for the paper. These can be found on GitHub.

Two videos contrasting Gather&Compact to the implementation of Dumitrescu-Pach by Moreno and Sacristán (MSDP):