Read and annotate "Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers"

[yzsshen]

https://arxiv.org/abs/1908.07880

We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses O(n^2) pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

[yzsshen]

Great paper, need to give it a more in-depth read if we decide to use this algorithm. Also need to adapt into 3D since 2D is used and expanding to 3D is a proposed open problem in this paper.

Essentially, we have worst-case optimal universal configuration--even with forbidden patterns--as long as we can use the "monkey" set of moves with the addition of 5 musketeer ("helper") modules. If we can expand this to 3D, that basically solves the problem of pivoting cube reconfiguration, right? Biggest issue here is how distributed can we make this process?

Should discuss this paper with the pivoting cube team.

[yzsshen]

See PO-SRPP: A Decentralized Pivoting Path Planning Method for Self-Reconfigurable Satellites (https://ieeexplore.ieee.org/abstract/document/10475566). Brought these paper to the attn of the pivoting cube team.