Universal Reconfiguration of Facet-Connected Modular Robots by Pivots:\n The $O(1)$ Musketeers

Abstract

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(n^2)$ 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