スライド式立方体ロボットのためのユニバーサルなその場再構成アルゴリズム
A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves
立方体モジュールロボットの任意の配置間をスライド移動のみでO(n^2)手数で再構成する初の汎用アルゴリズムを提案し、ほぼ1つのモジュールを除き開始・終了配置の境界内に留めるその場再構成版も示した。
著者: Zachary Abel, Hugo A. Akitaya, Scott Duke Kominers, Matias Korman, Frederick Stock
分類: cs.CG, cs.MA, cs.RO
原文アブストラクト
In the modular robot reconfiguration problem, we are given $n$ cube-shaped modules (or robots) as well as two configurations, i.e., placements of the $n$ modules so that their union is face-connected. The goal is to find a sequence of moves that reconfigures the modules from one configuration to the other using "sliding moves," in which a module slides over the face or edge of a neighboring module, maintaining connectivity of the configuration at all times. For many years it has been known that certain module configurations in this model require at least $\Omega(n^2)$ moves to reconfigure between them. In this paper, we introduce the first universal reconfiguration algorithm -- i.e., we show that any $n$-module configuration can reconfigure itself into any specified $n$-module configuration using just sliding moves. Our algorithm achieves reconfiguration in $O(n^2)$ moves, making it asymptotically tight. We also present a variation that reconfigures in-place, it ensures that throughout the reconfiguration process, all modules, except for one, will be contained in the union of the bounding boxes of the start and end configuration.
関連論文
- CuBot-STT:格子型モジュラー再構成ロボットの搬送と締結を同時に行う外部ロボットモジュラーロボット
- ロボットの出芽:物理的自己複製における均質なモジュールから多様な形態へモジュラーロボット
- 異種モジュラーロボットの形態形成アセンブリと適応制御モジュラーロボット
- 変形可能な四辺形モジュールロボットの自己再構成計画モジュラーロボット
- RhoMorph:安定かつ媒体非依存の再構成動作を実現する菱形変形モジュールロボットモジュラーロボット
- 格子型モジュラー・ロボットのための連続的雌雄同体結合機構モジュラーロボット
