2025/12/16 by Zachary Abel, Abel, Zachary, Hugo A. Akitaya +7
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #Modular Robots and Swarm Intelligence #Optimization and Search Problems
paper · pdf · doi:10.20382/jocg.v16i2a11
openalex publication_date 2025/12/16 · openalex created_date 2025/12/21 · openalex updated_date 2026/07/22
In the modular robot reconfiguration problem, we are given n cube-shaped modules (or robots) as well as two configurations, i.e., placements of the n modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves", in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least Ω(n2) moves to reconfigure between them, and works for any dimension d≥ 3. In this paper, we introduce the first universal reconfiguration algorithm—i.e., we show that any n-module configuration can reconfigure itself into any specified n-module configuration using just sliding moves. Our algorithm achieves reconfiguration in O(n2) moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.