2019/08/21 by Hugo A. Akitaya, Esther M. Arkin, Akitaya, Hugo A. +19 · 1 citation
Computer Science · Engineering · #Advanced Materials and Mechanics #Cellular Automata and Applications #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1908.07880
openalex publication_date 2019/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present the first universal reconfiguration algorithm for transforming a\nmodular robot between any two facet-connected square-grid configurations using\npivot moves. More precisely, we show that five extra "helper" modules\n("musketeers") suffice to reconfigure the remaining n modules between any two\ngiven configurations. Our algorithm uses O(n2) pivot moves, which is\nworst-case optimal. Previous reconfiguration algorithms either require less\nrestrictive "sliding" moves, do not preserve facet-connectivity, or for the\nsetting we consider, could only handle a small subset of configurations defined\nby a local forbidden pattern. Configurations with the forbidden pattern do have\ndisconnected reconfiguration graphs (discrete configuration spaces), and indeed\nwe show that they can have an exponential number of connected components. But\nforbidding the local pattern throughout the configuration is far from\nnecessary, as we show that just a constant number of added modules (placed to\nbe freely reconfigurable) suffice for universal reconfigurability. We also\nclassify three different models of natural pivot moves that preserve\nfacet-connectivity, and show separations between these models.\n