モジュラーピボットロボットの普遍的再構成可能性の解明
Characterizing Universal Reconfigurability of Modular Pivoting Robots
六角形モジュールのピボット動作による再構成問題を解析し、制限なし動作ではO(n^3)で任意の連結配置間を変換する初の普遍アルゴリズムを提示、制限動作のみではPSPACE完全となることを証明した。
著者: Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, Vera Sacristán
分類: cs.CG, cs.CC, cs.RO
原文アブストラクト
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using $O(n^3)$ monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.
関連論文
- CuBot-STT:格子型モジュラー再構成ロボットの搬送と締結を同時に行う外部ロボットモジュラーロボット
- ロボットの出芽:物理的自己複製における均質なモジュールから多様な形態へモジュラーロボット
- 異種モジュラーロボットの形態形成アセンブリと適応制御モジュラーロボット
- 変形可能な四辺形モジュールロボットの自己再構成計画モジュラーロボット
- RhoMorph:安定かつ媒体非依存の再構成動作を実現する菱形変形モジュールロボットモジュラーロボット
- 格子型モジュラー・ロボットのための連続的雌雄同体結合機構モジュラーロボット
