We study a new model of 3-dimensional modular self-reconfigurable robots Rhombic Dodecahedral (RD). By extending results on the 2D analog of this model we characterize the free space requirements for a pivoting move and investigate the $\textit{reconfiguration problem}$, that is, given two configurations $s$ and $t$ is there a sequence of moves that transforms $s$ into $t$? We show reconfiguration is PSPACE-hard for RD modules in a restricted pivoting model. In a more general model, we show that RD configurations are not universally reconfigurable despite the fact that their 2D analog is [Akitaya et al., SoCG 2021]. Additionally, we present a new class of RD configurations that we call $\textit{super-rigid}$. Such a configuration remains rigid even as a subset of any larger configuration, which does not exist in the 2D setting.
翻译:我们研究了一种新型的三维模块化自重组机器人,即立方十二面体(Rhombic Dodecahedral, RD)。通过扩展该模型的二维类比,我们表征了一个扭转移动的自由空间需求,并研究了“重新配置问题”,即给定两个构型 $s$ 和 $t$,是否存在一系列移动将 $s$ 转化为 $t$。我们发现,在受限制的枢轴模型中,RD 模块的重新配置是 $PSPACE-hard$ 的。在更一般的模型中,尽管其二维类比具有通用重新配置能力[Akitaya et al。,SoCG 2021],我们也展示了 RD 构型并非普遍可重构。此外,我们提出了一类新的 RD 构型,称为“超刚性”。这种构型即使作为任何更大构型的子集也保持刚性,而在二维设置中不存在这种情况。