2026-07-22T13:00:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12236 2024-03-06T10:49:46Z ddc:004 open_access

Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition) Miltzow, Tillmann Parada, Irene Sonke, Willem Speckmann, Bettina Wulms, Jules Sliding cubes Reconfiguration Modular robots Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tillmann Miltzow and Irene Parada and Willem Sonke and Bettina Speckmann and Jules Wulms 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.78 urn:nbn:de:0030-drops-122363 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.78 eng https://creativecommons.org/licenses/by/3.0/legalcode