Input-Sensitive Reconfiguration of Sliding Cubes

Hugo A. Akitaya, Matias Korman, Frederick Stock · 2025

Read Input-Sensitive Reconfiguration of Sliding Cubes by Hugo A. Akitaya, Matias Korman, Frederick Stock (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-04170.txt.

Introduction

Hugo Akitaya, Matias Korman, and Frederick Stock study how to reshape a swarm of cube-shaped robots that slide over each other. The cubes sit on a grid and must stay joined as one blob. The task is to find a chain of slides that turns a start shape into a goal shape.

Known methods can join any two shapes, but the move count can be high. When the goal is a compact shape, the count drops if it is tied to the input's size. The new method blends both ideas: it works for any goal shape, and its move count tracks the size of both shapes. Each move also costs very little compute time on average.

Catalog record

CREATORHugo A. Akitaya, Matias Korman, Frederick Stock
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-04170

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Input-Sensitive Reconfiguration of Sliding Cubes Hugo A. Akitaya, Matias Korman, Frederick Stock Abstract A configuration of n n unit-cube-shaped modules (or robots ) is a lattice-aligned placement of the n n modules so that their union is face-connected. The reconfiguration problem aims at finding a sequence of moves that reconfigures the modules from one given configuration to another. The sliding cube model (in which modules are allowed to slide over the face or edge of neighboring modules) is one of the most studied theoretical models for modular robots. In the sliding cubes model we can reconfigure between any two shapes in O ⁡ ( n 2 ) O(n^{2}) moves ([Abel et al. SoCG 2024]). If we are interested in a reconfiguration algorithm into a compact configuration , the number of moves can be reduced to the sum of coordinates of the input configuration (a number that ranges from Ω ⁡ ( n 4 / 3 ) \Omega(n^{4/3}) to O ⁡ ( n 2 ) O(n^{2}) , [Kostitsyna et al. SWAT 2024]). We introduce a new algorithm that combines both universal reconfiguration and an input-sensitive bound on the sum of coordinates of both configurations, with additional advantages, such as O ⁡ ( 1 ) O(1) amortized computation per move. \newcounter section-preserve \newcounter theorem-preserve 1 Introduction Modular self-reconfigurable robotic systems offer several advantages over typical robotic systems. Such systems are composed of a set of robotic units (called modules ) that can communicate, attach, detach, and move relative to each other. This means modules can move to change the overall system’s shape, providing versatility to perform unforeseen tasks. While advantageous, the increased degree of freedom also incurs an algorithmic challenge, as it is not easy to determine how to use the module’s operations so that the union of all modules creates a specific shape (this is known as the reconfiguration problem). The algorithmic community has investigated the reconfiguration problem for many variations of modular robots, be it the type of moves allowed (sliding [ 5 , 9 , 10 ] , pivoting [ 3 , 13 ] , and so-called square “atoms” [ 6 , 7 ] ) or shape (such as hexagons [ 4 ] ). We investigate one of the most established models, which is called the sliding (hyper-)cube model : modules are lattice-aligned unit (hyper-)cubes where two modules are adjacent if they share a face (i.e., a (d-1) -dimensional facet). In this model, two types of moves are allowed: a module can slide along the co-(hyper-)planar faces of two other adjacent modules, or it can slide along two orthogonal faces of another module (see Fig. 1 ). (a) (b) Figure 1 : (a) Slide and (b) Convex transition. The reachability problem asks whether, given two configurations with n modules, there exists a sequence of moves that can transform one into the other. If the answer is always ‘yes’ we say that the model admits universal reconfiguration. The first universal result for the two dimensional sliding model was obtained by Dumitrescu and Pach [ 9 ] with a reconfiguration algorithm that required O(n^{2}) moves. This result could be seen as optimal since some instances require \Omega(n^{2}) moves. The 2-dimensional result was afterwards extended to three and higher dimensions in an informal publication of Abel and Kominers [ 2 ] . Their paper claimed universal reconfiguration and that O(n^{3}) many moves were always sufficient. Other research [ 3 ] focused on variations of the model, in both the shape of the modules and the type of movements that were allowed. They obtained characterization of which variations of the model have universal reconfiguration. For the versions in which no universal reconfiguration algorithm exists, they showed that determining if a particular instance can be reconfigured into a target configuration is PSPACE-complete. Recently there have been two simultaneous, independent results in three dimensions. Abel et al. [ 1 ] formally published their preliminary result, reducing the number of moves to O(n^{2}) . In the same paper, the authors explain how the algorithm can be made in-place and input-sensitive (the exact bound depends on the dimension of the bounding box of both configurations). In-place means throughout the reconfiguration there are never more than a constant number of modules outside the bounding boxes of the start and end configuration. Further, these modules are never more than distance 1 from the bounding box 1 1 1 Traditionally, in-place algorithms are a bit more restrictive, only one module is allowed outside the bounding box, making both constants exactly 1. In this paper we relax the condition for ease of description. . Parallel to [ 1 ] , Kostitsyna et al. [ 12 ] independently produced a different input-sensitive reconfiguration algorithm: a configuration C can be reconfigured into a compact configuration , intuitively, a shape where all modules are clumped together without holes (formal definition given in Section 2 ). Their algorithm takes O(\sum_{\mathbf{m}\in C_{1}}\|\mathbf{m}\|_{1}) sliding moves where \|\mathbf{m}\|_{1} denotes the L_{1} norm of the position of a module \mathbf{m} . This result has a better input-sensitive bound, but is slightly limited: they only show how to reconfigure into a compact configuration. Since there is more than one compact configuration with the same number of modules, this does not directly lead to a universal reconfiguration strategy. Reconfiguration between compact configurations is significantly simpler than compactification, but does not immediately follow. This paper we improve on both [ 1 ] and [ 12 ] : we give a universal reconfiguration whose number total number of moves depends on the sum of input and target coordinates ( O(\sum_{\mathbf{m}\in C_{1}}\|\mathbf{m}\|_{1}+\sum_{\mathbf{m}\in C_{2}}\|\mathbf{m}\|_{1}) . Since configurations are connected, it is easy to see that this bound is in \Omega(n^{4/3})\cap O(n^{2}) (when all modules form a solid cube or when they form the 1-skeleton of a larger cube, respectively). Our main result is formally stated as follows. Theorem 1 Given two configurations C_{1} and C_{2} with n cube modules in 3 dimensions where all modules lie in the positive xyz orthant, there is an in-place reconfiguration between them that uses at most 18(\sum_{\mathbf{m}\in C_{1}}\|\mathbf{m}\|_{1}+\sum_{\mathbf{m}\in C_{2}}\|\mathbf{m}\|_{1})+120n+O(1) sliding moves where \|\mathbf{m}\|_{1} denotes the L_{1} norm of the position of a module \mathbf{m} . Such a reconfiguration can be computed in O(1) amortized time per sliding move. In our algorithm we use a constant number of auxiliary “helper” modules that will allow nearby modules to move. We follow existing literature [ 3 ] and refer to the auxiliary modules as musketeers . The multiplicative factor 120 may seem large, we note that our algorithm uses six musketeer modules, so this constant is better characterized by 20n moves per musketeer module. Further, since we reconfigure between C_{1} and C_{2} by reaching an intermediate configuration, this means that we actually need 10n moves per musketeer to transform any configuration of n modules into compact form. Although the main emphasis is in the total number of moves required, it is also interesting to bound the time needed to compute the sequence of moves needed to reconfigure between two configurations. Our algorithm can compute each move in O(1) amortized time. Although the computation time is not directly addressed in the previous papers, it is not hard to see that the algorithm of

Read the complete text